@article{EJP198,
author = {Yuval Peres and David Revelle},
title = {Mixing Times for Random Walks on Finite Lamplighter Groups},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {9},
year = {2004},
keywords = {random walks; lamplighter group; mixing time; cover time},
abstract = {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 $d\geq 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.},
pages = {no. 26, 825-845},
issn = {1083-6489},
doi = {10.1214/EJP.v9-198},
url = {http://ejp.ejpecp.org/article/view/198}}