Mixing Times for Random Walks on Finite Lamplighter Groups
David Revelle (University of California)
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.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 825-845
Publication Date: November 17, 2004
DOI: 10.1214/EJP.v9-198
References
- 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
- 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
- David Aldous, Threshold limits for cover times, J. Theoret. Probab. 4 (1991), no. 1, 197--211. Math. Review 91m:60123
- 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
- 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
- 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
- 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
- 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
- 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
- Peter Matthews, Covering problems for Brownian motion on spheres, Ann. Probab. 16 (1988), no. 1, 189--199. Math. Review 89a:60190
- 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
- P. Révész, Clusters of a random walk on the plane, Ann. Probab. 21 (1993), no. 1, 318--328. Math. Review 94f:60047
- J.C. Reyes, Random walk, semi-direct products, and card shuffling, Ph.D. thesis, Stanford University, 2002, pp. x+163.
- Clyde H. Schoolfield, Jr., Random walks on wreath products of groups, J. Theoret. Probab. 15 (2002), no. 3, 667--693. Math. Review 2003f:60018
- 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}
This work is licensed under a Creative Commons Attribution 3.0 License.