Mixing Times for Random Walks on Finite Lamplighter Groups

摘要

Given a finite graph $G$, a vertex of the lamplighter graph $G^diamondsuit=mathbb {Z}_2 wr G$ consists of a zero-one labeling of the vertices of $G$, and a marked vertex of $G$. For transitive $G$ we show that, up to constants, the relaxation time for simple random walk in $G^diamondsuit$ is the maximal hitting time for simple random walk in $G$, while the mixing time in total variation on $G^diamondsuit$ is the expected cover time on $G$. The mixing time in the uniform metric on $G^diamondsuit$ admits a sharp threshold, and equals $|G|$ multiplied by the relaxation time on $G$, up to a factor of $log |G|$. For $mathbb {Z}_2 wr mathbb {Z}_n^2$, the lamplighter group over the discrete two dimensional torus, the relaxation time is of order $n^2 log n$, the total variation mixing time is of order $n^2 log^2 n$, and the uniform mixing time is of order $n^4$. For $mathbb {Z}_2 wr mathbb {Z}_n^d$ when $dgeq 3$, the relaxation time is of order $n^d$, the total variation mixing time is of order $n^d log n$, and the uniform mixing time is of order $n^{d+2}$. In particular, these three quantities are of different orders of magnitude.