Uniform mixing time for random walk on lamplighter graphs

Komjáthy, Júlia, Miller, Jason, and Peres, Yuval. "Uniform mixing time for random walk on lamplighter graphs." Annales de l'I.H.P. Probabilités et statistiques 50.4 (2014): 1140-1160. <http://eudml.org/doc/272003>.

@article{Komjáthy2014,
abstract = {Suppose that $\mathcal \{G\} $ is a finite, connected graph and $X$ is a lazy random walk on $\mathcal \{G\} $. The lamplighter chain $X^\{\diamond \}$ associated with $X$ is the random walk on the wreath product $\mathcal \{G\} ^\{\diamond \}=\mathbf \{Z\} _\{2\}\wr \mathcal \{G\} $, the graph whose vertices consist of pairs $(\underline\{f\} ,x)$ where $f$ is a labeling of the vertices of $\mathcal \{G\} $ by elements of $\mathbf \{Z\} _\{2\}=\lbrace 0,1\rbrace $ and $x$ is a vertex in $\mathcal \{G\} $. There is an edge between $(\underline\{f\} ,x)$ and $(\underline\{g\} ,y)$ in $\mathcal \{G\} ^\{\diamond \}$ if and only if $x$ is adjacent to $y$ in $\mathcal \{G\} $ 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 $\mathbf \{Z\} _\{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 $\mathcal \{G\} $ satisfies mild hypotheses. In particular, when $\mathcal \{G\} $ is the hypercube $\mathbf \{Z\} _\{2\}^\{d\}$, we show that the uniform mixing time of $X^\{\diamond \}$ is $\varTheta (d2^\{d\})$. More generally, we show that when $\mathcal \{G\} $ is a torus $\mathbf \{Z\} _\{n\}^\{d\}$ for $d\ge 3$, the uniform mixing time of $X^\{\diamond \}$ is $\varTheta (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.},
author = {Komjáthy, Júlia, Miller, Jason, Peres, Yuval},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {random walk; uncovered set; lamplighter walk; mixing time; random walks; lamplighter graphs},
language = {eng},
number = {4},
pages = {1140-1160},
publisher = {Gauthier-Villars},
title = {Uniform mixing time for random walk on lamplighter graphs},
url = {http://eudml.org/doc/272003},
volume = {50},
year = {2014},
}

TY - JOUR
AU - Komjáthy, Júlia
AU - Miller, Jason
AU - Peres, Yuval
TI - Uniform mixing time for random walk on lamplighter graphs
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2014
PB - Gauthier-Villars
VL - 50
IS - 4
SP - 1140
EP - 1160
AB - Suppose that $\mathcal {G} $ is a finite, connected graph and $X$ is a lazy random walk on $\mathcal {G} $. The lamplighter chain $X^{\diamond }$ associated with $X$ is the random walk on the wreath product $\mathcal {G} ^{\diamond }=\mathbf {Z} _{2}\wr \mathcal {G} $, the graph whose vertices consist of pairs $(\underline{f} ,x)$ where $f$ is a labeling of the vertices of $\mathcal {G} $ by elements of $\mathbf {Z} _{2}=\lbrace 0,1\rbrace $ and $x$ is a vertex in $\mathcal {G} $. There is an edge between $(\underline{f} ,x)$ and $(\underline{g} ,y)$ in $\mathcal {G} ^{\diamond }$ if and only if $x$ is adjacent to $y$ in $\mathcal {G} $ 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 $\mathbf {Z} _{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 $\mathcal {G} $ satisfies mild hypotheses. In particular, when $\mathcal {G} $ is the hypercube $\mathbf {Z} _{2}^{d}$, we show that the uniform mixing time of $X^{\diamond }$ is $\varTheta (d2^{d})$. More generally, we show that when $\mathcal {G} $ is a torus $\mathbf {Z} _{n}^{d}$ for $d\ge 3$, the uniform mixing time of $X^{\diamond }$ is $\varTheta (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.
LA - eng
KW - random walk; uncovered set; lamplighter walk; mixing time; random walks; lamplighter graphs
UR - http://eudml.org/doc/272003
ER -