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 -
