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\neq 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\neq 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 \(\Theta (d2_d)\). More generally, we show that when \(\CG\) is a torus \(\Z_n^d\) for \(d\geq 3\), the uniform mixing time of \(X_⋄\) is \(\Theta (dn_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.