Mixing Times for Random Walks on Finite Lamplighter Groups

Yuval Peres (University of California)
David Revelle (University of California)


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.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 825-845

Publication Date: November 17, 2004

DOI: 10.1214/EJP.v9-198


  1. David Aldous and Persi Diaconis, Strong uniform times and finite random walks, Adv. in Appl. Math. 8 (1987), no. 1, 69--97. Math. Review 88d:60175
  2. David Aldous and James Allen Fill, Reversible markov chains and random walks on graphs, Available at http://www.stat.berkeley.edu/~aldous/RWG/book.html
  3. David Aldous, Threshold limits for cover times, J. Theoret. Probab. 4 (1991), no. 1, 197--211. Math. Review 91m:60123
  4. Noam Berger, Claire Kenyon, Elchanan Mossel, and Yuval Peres, Glauber Dynamics on Trees and Hyperbolic Graphs, Extended abstract by Kenyon, Mossel, and Peres appeared in 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001) arXiv:math.PR/0308284
  5. Andrei Z. Broder and Anna R. Karlin, Bounds on the cover time, J. Theoret. Probab. 2 (1989), no. 1, 101--120. Math. Review 90b:60079
  6. Mu-Fa Chen, Trilogy of couplings and general formulas for lower bound of spectral gap, Probability towards 2000 (New York, 1995), Lecture Notes in Statist. , vol. 128, Springer, New York, 1998, pp. 123--136. Math. Review 99h:60130
  7. Amir Dembo, Yuval Peres, Jay Rosen, and Ofer Zeitouni, Cover times for brownian motion and random walks in two dimensions, Ann. Math. (to appear) , arXiv:math.PR/0107191
  8. James Allen Fill and Clyde H. Schoolfield, Jr., Mixing times for Markov chains on wreath products and related homogeneous spaces, Electron. J. Probab. 6 (2001), no. 11, 22 pp. (electronic). Math. Review 2002b:60121
  9. Olle Häggström and Johan Jonasson, Rates of convergence for lamplighter processes, Stochastic Process. Appl. 67 (1997), no. 2, 227--249. Math. Review 98j:60097
  10. Peter Matthews, Covering problems for Brownian motion on spheres, Ann. Probab. 16 (1988), no. 1, 189--199. Math. Review 89a:60190
  11. Christophe Pittet and Laurent Saloff-Coste, Amenable groups, isoperimetric profiles and random walks, Geometric group theory down under (Canberra, 1996) , de Gruyter, Berlin, 1999, pp. 293--316. Math. Review 2001d:20041
  12. P. Révész, Clusters of a random walk on the plane, Ann. Probab. 21 (1993), no. 1, 318--328. Math. Review 94f:60047
  13. J.C. Reyes, Random walk, semi-direct products, and card shuffling, Ph.D. thesis, Stanford University, 2002, pp. x+163.
  14. Clyde H. Schoolfield, Jr., Random walks on wreath products of groups, J. Theoret. Probab. 15 (2002), no. 3, 667--693. Math. Review 2003f:60018
  15. Frank Spitzer, Principles of random walks, second ed., Springer-Verlag, New York, 1976, Graduate Texts in Mathematics, Vol. 34. Math. Review 52 #9383 \MR{52 #9383}

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.