Uniform Mixing Time For Random Walk On Lamplighter Graphs

Suppose that $\CG$ is a finite, connected graph and X is a lazy random walk on $\CG$. The lamplighter chain X⋄ 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 $\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≠x,y. In each step, X⋄ 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 $\Z_2$; f(z) for z≠x,y remains unchanged. We give matching upper and lower bounds on the uniform mixing time of X⋄ provided $\CG$ satisfies mild hypotheses. In particular, when $\CG$ is the hypercube $\Z_2^d$, we show that the uniform mixing time of X⋄ is Θ(d2d). More generally, we show that when $\CG$ is a torus $\Z_n^d$ for d≥3, the uniform mixing time of X⋄ is Θ(dnd) 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.