Uniform mixing time for Random Walk on Lamplighter Graphs

Suppose that $\text{CG}$ is a finite, connected graph and $X$ is a lazy random walk on $\text{CG}$. The lamplighter chain $X^{\diamond }$ associated with $X$ is the random walk on the wreath product ${\text{CG}}^{\diamond }={\mathbb{Z}}_2\wr \text{CG}$, the graph whose vertices consist of pairs $(f,x)$ where $f$ is a labeling of the vertices of $\text{CG}$ by elements of ${\mathbb{Z}}_2$ and $x$ is a vertex in $\text{CG}$. There is an edge between $(f,x)$ and $(g,y)$ in ${\text{CG}}^{\diamond }$ if and only if $x$ is adjacent to $y$ in $\text{CG}$ and $f(z)=g(z)$ for all $z\mathrm{\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\mathrm{\ne }x,y$ remains unchanged. We give matching upper and lower bounds on the uniform mixing time of $X^{\diamond }$ provided $\text{CG}$ satisfies mild hypotheses. In particular, when $\text{CG}$ is the hypercube ${\mathbb{Z}}_2^d$, we show that the uniform mixing time of $X^{\diamond }$ is $\mathrm{\Theta }(d{2}^d)$. More generally, we show that when $\text{CG}$ is a torus ${\mathbb{Z}}_n^d$ for $d\ge 3$, the uniform mixing time of $X^{\diamond }$ is $\mathrm{\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.