Uniform mixing time for random walk on lamplighter graphs

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

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

Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014), p. 1140-1160 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé
Abstract

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 $(\underset{̲}{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 $(\underset{̲}{f}, x)$ et $(\underset{̲}{g}, y)$ dans $𝒢^{⋄}$ si et seulement si $x$ est adjacent à $y$ dans $𝒢$ et $f_{z} = g_{z}$ pour tout $z \neq x, y$ . A chaque pas, $X^{⋄}$ se déplace d’une configuration $(\underset{̲}{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 \neq x, 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 $𝛩 (d 2^{d})$ . Plus généralement, nous montrons que quand $𝒢$ est le tore $𝐙_{n}^{d}$ avec $d \geq 3$ , le temps de mélange uniforme de $X^{⋄}$ est $𝛩 (d n^{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.

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 $(\underset{̲}{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 $(\underset{̲}{f}, x)$ and $(\underset{̲}{g}, y)$ in $𝒢^{⋄}$ if and only if $x$ is adjacent to $y$ in $𝒢$ and $f_{z} = g_{z}$ for all $z \neq x, y$ . In each step, $X^{⋄}$ moves from a configuration $(\underset{̲}{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 \neq x, 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 $𝛩 (d 2^{d})$ . More generally, we show that when $𝒢$ is a torus $𝐙_{n}^{d}$ for $d \geq 3$ , the uniform mixing time of $X^{⋄}$ is $𝛩 (d n^{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.

Publié le : 2014-01-01

MR 3269988 | Zbl 06377548

DOI : https://doi.org/10.1214/13-AIHP547
Classification: 60J10, 60D05, 37A25

@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},
     volume = {50},
     year = {2014},
     pages = {1140-1160},
     doi = {10.1214/13-AIHP547},
     mrnumber = {3269988},
     zbl = {06377548},
     language = {en},
     url = {http://dml.mathdoc.fr/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, Tome 50 (2014) pp. 1140-1160. doi : 10.1214/13-AIHP547. http://gdmltest.u-ga.fr/item/AIHPB_2014__50_4_1140_0/

Bibliographie

[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