Uniform mixing time for random walk on lamplighter graphs

Komjáthy, Júlia; Miller, Jason; Peres, Yuval

Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014) no. 4, pp. 1140-1160.

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 $(\underline{f},x)$ où $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 $(\underline{f},x)$ et $(\underline{g},y)$ 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 $(\underline{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 $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.

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 $(\underline{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 $(\underline{f},x)$ and $(\underline{g},y)$ 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 $(\underline{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 $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.

Classification : 60J10, 60D05, 37A25
Mots clés : random walk, uncovered set, lamplighter walk, mixing time

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

[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 | Zbl

[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 | Zbl

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

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

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

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

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

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

[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 | Zbl

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