### Mixing and relaxation time for random walk on wreath product graphs

**Júlia Komjáthy**

*(Budapest University of Technology and Economics)*

**Yuval Peres**

*(Microsoft Research)*

#### Abstract

Suppose that G and H are finite, connected graphs, G regular, X is a lazy random walk on G and Z is a reversible ergodic Markov chain on H. The generalized lamplighter chain X* associated with X and Z is the random walk on the wreath product H\wr G, the graph whose vertices consist of pairs (f,x) where f=(f_v)_{v\in V(G)} is a labeling of the vertices of G by elements of H and x is a vertex in G. In each step, X* moves from a configuration (f,x) by updating x to y using the transition rule of X and then independently updating both f_x and f_y according to the transition probabilities on H; f_z for z different of x,y remains unchanged. We estimate the mixing time of X* in terms of the parameters of H and G. Further, we show that the relaxation time of X* is the same order as the maximal expected hitting time of G plus |G| times the relaxation time of the chain on H.

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

Pages: 1-23

Publication Date: July 30, 2013

DOI: 10.1214/EJP.v18-2321

#### References

- Aldous, David; Diaconis, Persi. Shuffling cards and stopping times.
*Amer. Math. Monthly*93 (1986), no. 5, 333-348. MR0841111 - D. Aldous and J. A. Fill, Reversible Markov chains and random walks on graphs, University of California, Berkeley, 2002.
- Barlow, Martin T.; Ding, Jian; Nachmias, Asaf; Peres, Yuval. The evolution of the cover time.
*Combin. Probab. Comput.*20 (2011), no. 3, 331-345. MR2784631 - Brummelhuis, M. J. A. M.; Hilhorst, H. J. Covering of a finite lattice by a random walk.
*Phys. A*176 (1991), no. 3, 387-408. MR1130067 - Dembo, Amir; Peres, Yuval; Rosen, Jay; Zeitouni, Ofer. Cover times for Brownian motion and random walks in two
dimensions.
*Ann. of Math. (2)*160 (2004), no. 2, 433-464. MR2123929 - Dembo, Amir; Peres, Yuval; Rosen, Jay; Zeitouni, Ofer. Late points for random walks in two dimensions.
*Ann. Probab.*34 (2006), no. 1, 219-263. MR2206347 - Diaconis, Persi; Fill, James Allen. Strong stationary times via a new form of duality.
*Ann. Probab.*18 (1990), no. 4, 1483-1522. MR1071805 - Ding, Jian; Lee, James R.; Peres, Yuval. Cover times, blanket times, and majorizing measures.
*Ann. of Math. (2)*175 (2012), no. 3, 1409-1471. MR2912708 - Feige, Uriel. A tight lower bound on the cover time for random walks on graphs.
*Random Structures Algorithms*6 (1995), no. 4, 433-438. MR1368844 - Häggström, Olle; Jonasson, Johan. Rates of convergence for lamplighter processes.
*Stochastic Process. Appl.*67 (1997), no. 2, 227-249. MR1449833 - Hunter, Jeffrey J. Variances of first passage times in a Markov chain with applications to
mixing times.
*Linear Algebra Appl.*429 (2008), no. 5-6, 1135-1162. MR2433169 - J. Komjáthy, J. Miller, and Y. Peres, Uniform mixing time for random walk on lamplighter graphs, Ann. Inst. Henri Poincaré Probab. Stat. (2013).
- Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times.
With a chapter by James G. Propp and David B. Wilson.
*American Mathematical Society, Providence, RI,*2009. xviii+371 pp. ISBN: 978-0-8218-4739-8 MR2466937 - N. Levy, Mixing time for lamplighter graphs, Master's thesis, University of California, Berkeley, 2006.
- L. Lovász and P. Winkler, Efficient stopping rules for markov chains, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing (New York, NY, USA), STOC '95, ACM, 1995, pp. 76-82.
- Miller, Jason; Peres, Yuval. Uniformity of the uncovered set of random walk and cutoff for
lamplighter chains.
*Ann. Probab.*40 (2012), no. 2, 535-577. MR2952084 - Peres, Yuval; Revelle, David. Mixing times for random walks on finite lamplighter groups.
*Electron. J. Probab.*9 (2004), no. 26, 825-845. MR2110019 - Y. Peres and P. Sousi, Mixing times are hitting times of large sets, http://arxiv.org/abs/1108.0133.
- Winkler, Peter; Zuckerman, David. Multiple cover time.
*Random Structures Algorithms*9 (1996), no. 4, 403-411. MR1605407

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