Uniform mixing time for random walk on lamplighter graphs

Suppose that G is a finite, connected graph and X is a lazy random walk on G . The lamplighter chain X ¿ associated with X is the random walk on the wreath product G ¿ =Z 2 ¿G , the graph whose vertices consist of pairs (f - ,x) where f is a labeling of the vertices of G by elements of Z 2 ={0,1} and x is a vertex in G . There is an edge between (f - ,x) and (g - ,y) in G ¿ if and only if x is adjacent to y in G 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 G satisfies mild hypotheses. In particular, when G is the hypercube Z d 2 , we show that the uniform mixing time of X ¿ is T(d2 d ) . More generally, we show that when G is a torus Z d n for d=3 , the uniform mixing time of X ¿ is T(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.