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}^{\diamond }$ associated with $X$ is the random walk on the wreath product ${𝒢}^{\diamond }={𝐙}_{2}\wr 𝒢$, the graph whose vertices consist of pairs $\left(\underline{f},x\right)$ where $f$ is a labeling of the vertices of $𝒢$ by elements of ${𝐙}_{2}=\left\{0,1\right\}$ and $x$ is a vertex in $𝒢$. There is an edge between $\left(\underline{f},x\right)$ and $\left(\underline{g},y\right)$ in ${𝒢}^{\diamond }$ if and only if $x$ is adjacent to $y$ in $𝒢$ and ${f}_{z}={g}_{z}$ for all $z\ne x,y$. In each step, ${X}^{\diamond }$ moves from a configuration $\left(\underline{f},x\right)$ 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 $z\ne x,y$ remains unchanged. We give matching upper and lower bounds on the uniform mixing time of ${X}^{\diamond }$ provided $𝒢$ satisfies mild hypotheses. In particular, when $𝒢$ is the hypercube ${𝐙}_{2}^{d}$, we show that the uniform mixing time of ${X}^{\diamond }$ is $𝛩\left(d{2}^{d}\right)$. More generally, we show that when $𝒢$ is a torus ${𝐙}_{n}^{d}$ for $d\ge 3$, the uniform mixing time of ${X}^{\diamond }$ is $𝛩\left(d{n}^{d}\right)$ 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}^{\diamond }$ associée à $X$ est la marche aléatoire sur le groupe produit ${𝒢}^{\diamond }={𝐙}_{2}\wr 𝒢$, le graphe dont les sites sont des paires $\left(\underline{f},x\right)$$f$ est un label des sites de $𝒢$ par des éléments de ${𝐙}_{2}=\left\{0,1\right\}$ et $x$ est un site de $𝒢$. Il existe une arête entre $\left(\underline{f},x\right)$ et $\left(\underline{g},y\right)$ dans ${𝒢}^{\diamond }$ si et seulement si $x$ est adjacent à $y$ dans $𝒢$ et ${f}_{z}={g}_{z}$ pour tout $z\ne x,y$. A chaque pas, ${X}^{\diamond }$ se déplace d’une configuration $\left(\underline{f},x\right)$ 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 $z\ne x,y$ restant inchangé. Nous prouvons des bornes supérieures et inférieures équivalentes sur le temps de mélange uniforme de ${X}^{\diamond }$ 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}^{\diamond }$ est $𝛩\left(d{2}^{d}\right)$. Plus généralement, nous montrons que quand $𝒢$ est le tore ${𝐙}_{n}^{d}$ avec $d\ge 3$, le temps de mélange uniforme de ${X}^{\diamond }$ est $𝛩\left(d{n}^{d}\right)$ 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