Uniform mixing time for Random Walk on Lamplighter Graphs

Abstract

Suppose that $\CG$ is a finite, connected graph and $X$ is a lazy random walk on $\CG$. The lamplighter chain $X^{\diamond }$ associated with $X$ is the random walk on the wreath product $\CG^\diamond = \Z_2 \wr \CG$, the graph whose vertices consist of pairs $(f,x)$ where $f$ is a labeling of the vertices of $\CG$ by elements of ${\mathbb{Z}}_2$ and $x$ is a vertex in $\CG$. There is an edge between $(f,x)$ and $(g,y)$ in $\CG^\diamond$ if and only if $x$ is adjacent to $y$ in $\CG$ and $f(z)=g(z)$ for all $z\ne x,y$. In each step, $X^{\diamond }$ moves from a configuration $(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 ${\mathbb{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 $\CG$ satisfies mild hypotheses. In particular, when $\CG$ is the hypercube ${\mathbb{Z}}_2^d$, we show that the uniform mixing time of $X^{\diamond }$ is $\Theta (d{2}^d)$. More generally, we show that when $\CG$ is a torus ${\mathbb{Z}}_n^d$ for $d\ge 3$, the uniform mixing time of $X^{\diamond }$ is $\Theta (d{n}^d)$ uniformly in $n$ and $d$. A critical ingredient for our proof is a concentration estimate for the local time of random walk in a subset of vertices.

2 figures, 27 pages. We added a new section containing a detailed proof of that our conditions hold for the torii $Z_n^d$, uniformly in $n$ and $d$

References in corpus (3)

• Late points for random walks in two dimensions
• Optimal Hoeffding bounds for discrete reversible Markov chains
• Uniformity of the uncovered set of random walk and cutoff for lamplighter chains

Cited by in corpus (1)

• Mixing and relaxation time for Random Walk on Wreath Product Graphs