Uniform mixing time for random walk on lamplighter graphs
Suppose that is a finite, connected graph and is a lazy random walk on . The lamplighter chain associated with is the random walk on the wreath product , the graph whose vertices consist of pairs where is a labeling of the vertices of by elements of and is a vertex in . There is an edge between and in if and only if is adjacent to in and for all . In each step, moves from a configuration by updating to using the transition rule of and then sampling both...