Uniform mixing time for random walk on lamplighter graphs
Annales de l'I.H.P. Probabilités et statistiques, Volume 50 (2014) no. 4, p. 1140-1160

Suppose that 𝒢 is a finite, connected graph and X is a lazy random walk on 𝒢. The lamplighter chain X associated with X is the random walk on the wreath product 𝒢 =𝐙 2 𝒢, the graph whose vertices consist of pairs (f ̲,x) where f is a labeling of the vertices of 𝒢 by elements of 𝐙 2 ={0,1} and x is a vertex in 𝒢. There is an edge between (f ̲,x) and (g ̲,y) in 𝒢 if and only if x is adjacent to y in 𝒢 and f z =g z for all zx,y. In each step, X moves from a configuration (f ̲,x) by updating x to y using the transition rule of X and then sampling both f x and f y according to the uniform distribution on 𝐙 2 ; f z for zx,y remains unchanged. We give matching upper and lower bounds on the uniform mixing time of X provided 𝒢 satisfies mild hypotheses. In particular, when 𝒢 is the hypercube 𝐙 2 d , we show that the uniform mixing time of X is 𝛩(d2 d ). More generally, we show that when 𝒢 is a torus 𝐙 n d for d3, the uniform mixing time of X is 𝛩(dn d ) uniformly in n and d. A critical ingredient for our proof is a concentration estimate for the local time of the random walk in a subset of vertices.

Soit 𝒢 un graphe connexe fini et X une marche aléatoire fainéante sur 𝒢. La chaîne de l’allumeur de réverbères X associée à X est la marche aléatoire sur le groupe produit 𝒢 =𝐙 2 𝒢, le graphe dont les sites sont des paires (f ̲,x)f est un label des sites de 𝒢 par des éléments de 𝐙 2 ={0,1} et x est un site de 𝒢. Il existe une arête entre (f ̲,x) et (g ̲,y) dans 𝒢 si et seulement si x est adjacent à y dans 𝒢 et f z =g z pour tout zx,y. A chaque pas, X se déplace d’une configuration (f ̲,x) en mettant à jour x vers y par la règle de translation de X et ensuite en mettant à jour à la fois f x et f y selon la distribution uniforme sur 𝐙 2 ; f z pour zx,y restant inchangé. Nous prouvons des bornes supérieures et inférieures équivalentes sur le temps de mélange uniforme de X sous des hypothèses faibles sur 𝒢. En particulier quand 𝒢 est l’hypercube 𝐙 2 d , nous montrons que le temps de mélange uniforme de X est 𝛩(d2 d ). Plus généralement, nous montrons que quand 𝒢 est le tore 𝐙 n d avec d3, le temps de mélange uniforme de X est 𝛩(dn d ) uniformément en n et d. Un ingrédient crucial de notre preuve est une estimation de concentration pour le temps local d’une marche aléatoire dans un sous ensemble de sites.

DOI : https://doi.org/10.1214/13-AIHP547
Classification:  60J10,  60D05,  37A25
Keywords: random walk, uncovered set, lamplighter walk, mixing time
@article{AIHPB_2014__50_4_1140_0,
     author = {Komj\'athy, J\'ulia and Miller, Jason and Peres, Yuval},
     title = {Uniform mixing time for random walk on lamplighter graphs},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {50},
     number = {4},
     year = {2014},
     pages = {1140-1160},
     doi = {10.1214/13-AIHP547},
     zbl = {06377548},
     mrnumber = {3269988},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2014__50_4_1140_0}
}
Komjáthy, Júlia; Miller, Jason; Peres, Yuval. Uniform mixing time for random walk on lamplighter graphs. Annales de l'I.H.P. Probabilités et statistiques, Volume 50 (2014) no. 4, pp. 1140-1160. doi : 10.1214/13-AIHP547. http://www.numdam.org/item/AIHPB_2014__50_4_1140_0/

[1] M. Brummelhuis and H. Hilhorst. Covering of a finite lattice by a random walk. Physica A 176 (1991) 387-408. | MR 1130067

[2] A. Dembo, Y. Peres, J. Rosen and O. Zeitouni. Cover times for Brownian motion and random walks in two dimensions. Ann. Math. 160 (2004) 433-464. | MR 2123929 | Zbl 1068.60018

[3] A. Dembo, Y. Peres, J. Rosen and O. Zeitouni. Late points for random walk in two dimensions. Ann. Probab. 34 (2006) 219-263. | MR 2206347 | Zbl 1100.60057

[4] P. Diaconis and L. Saloff-Coste. Comparison techniques for random walk on finite groups. Ann. Probab. 21 (1993) 2131-2156. | MR 1245303 | Zbl 0790.60011

[5] P. Diaconis and L. Saloff-Coste. Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 (1996) 695-750. | MR 1410112 | Zbl 0867.60043

[6] O. Häggström and J. Jonasson. Rates of convergence of lamplighter processes. Stochastic Process. Appl. 67 (1997) 227-249. | MR 1449833 | Zbl 0889.60074

[7] G. F. Lawler and V. Limic. Random Walk: A Modern Introduction. Cambridge Studies in Advanced Mathematics 123. Cambridge Univ. Press, Cambridge, 2010. | MR 2677157 | Zbl 1210.60002

[8] C. A. Leon and F. Perron. Optimal Hoeffding bounds for discrete reversible Markov chains. Ann. Appl. Probab. 14 (2004) 958-970. | MR 2052909 | Zbl 1056.60070

[9] D. Levin, Y. Peres and E. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, Providence, RI, 2008. | MR 2466937 | Zbl 1160.60001

[10] J. Miller and Y. Peres. Uniformity of the uncovered set of random walk and cutoff for lamplighter chains. Ann. Probab. 40 (2011) 535-577. | MR 2952084 | Zbl 1251.60058

[11] Y. Peres and D. Revelle. Mixing times for random walks on finite lamplighter groups. Electron. J. Probab. 9 (2004) 825-845. | MR 2110019 | Zbl 1064.60095