Uniform mixing time for random walk on lamplighter graphs

作者：Komjathya Julia^*; Miller Jason; Peres Yuval

来源：Annales de l Institut Henri Poincare-Probabilites et Statistiques, 2014, 50(4): 1140-1160.

DOI：10.1214/13-AIHP547

• Random walk
• Uncovered set
• Lamplighter walk
• Mixing time

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) 2 G, the graph whose vertices consist of pairs ((f) under bar, 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) under bar, x) and ((g) under bar, y) in G if and only if x is adjacent to y in G and f(z) = g(z) for all z not equal x, y. In each step, X moves from a configuration ((f) under bar, 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 not equal 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(2)(d), we show that the uniform mixing time of X is Theta(d2(d)). More generally, we show that when G is a torus Z(n)(d) for d %26gt;= 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 the random walk in a subset of vertices.

• 出版日期2014-11
• 单位Microsoft