Given a finite, connected graph @math , the lamplighter chain on @math is the lazy random walk @math on the associated lamplighter graph @math . The mixing time of the lamplighter chain on the torus @math is known to have a cutoff at a time asymptotic to the cover time of @math if @math , and to half the cover time if @math . We show that the mixing time of the lamplighter chain on @math has a cutoff at @math times the cover time of @math as @math , where @math is an explicit weakly decreasing map from @math onto @math . In particular, as @math varies, the threshold continuously interpolates between the known thresholds for @math and @math . Perhaps surprisingly, we find a phase transition (non-smoothness of @math ) at the point @math , where high dimensional behavior ( @math for all @math ) commences. Here @math is the effective resistance from @math to @math in @math .
The mixing time of @math was first studied by H "aggstr "om and Jonasson in @cite_12 in the case of the complete graph @math and the one-dimensional cycle @math . Their work implies a total variation cutoff with threshold @math in the former case and that there is no cutoff in the latter. The connection between @math and @math is explored further in @cite_4 (see also the account given in [Chapter 19] LPW ), in addition to developing the relationship between @math and the relaxation time (i.e. inverse spectral gap) of @math , and the relationship between exponential moments of the size of the uncovered set @math of @math at time @math and the uniform, i.e. @math -mixing time of @math . In particular, it is shown in [Theorem 1.3] PR that if @math is a sequence of graphs with @math and @math then Related bounds on the order of magnitude of the uniform mixing time and the relaxation with generalized lamps were obtained respectively in @cite_8 and @cite_2 .
@cite_2 @cite_4 @cite_12 @cite_8
2055134178 2021912525 2046434141 2117320315
Suppose that G and H are finite, connected graphs, G regular, X is a lazy random walk on G and Z is a reversible ergodic Markov chain on H. The generalized lamplighter chain X* associated with X and Z is the random walk on the wreath product H G, the graph whose vertices consist of pairs (f,x) where f=(f_v)_ v V(G) is a labeling of the vertices of G by elements of H and x is a vertex in G. In each step, X* moves from a configuration (f,x) by updating x to y using the transition rule of X and then independently updating both f_x and f_y according to the transition probabilities on H; f_z for z different of x,y remains unchanged. We estimate the mixing time of X* in terms of the parameters of H and G. Further, we show that the relaxation time of X* is the same order as the maximal expected hitting time of G plus |G| times the relaxation time of the chain on H. Given a finite graph @math , a vertex of the lamplighter graph @math consists of a zero-one labeling of the vertices of @math , and a marked vertex of @math . For transitive @math we show that, up to constants, the relaxation time for simple random walk in @math is the maximal hitting time for simple random walk in @math , while the mixing time in total variation on @math is the expected cover time on @math . The mixing time in the uniform metric on @math admits a sharp threshold, and equals @math multiplied by the relaxation time on @math , up to a factor of @math . For @math , the lamplighter group over the discrete two dimensional torus, the relaxation time is of order @math , the total variation mixing time is of order @math , and the uniform mixing time is of order @math . For @math when @math , the relaxation time is of order @math , the total variation mixing time is of order @math , and the uniform mixing time is of order @math . In particular, these three quantities are of different orders of magnitude. Consider a graph, G, for which the vertices can have two modes, 0 or 1. Suppose that a particle moves around on G according to a discrete time Markov chain with the following rules. With (strictly positive) probabilities pm, pc and pr it moves to a randomly chosen neighbour, changes the mode of the vertex it is at or just stands still, respectively. We call such a random process a (pm, pc, pr)-lamplighter process on G. Assume that the process starts with the particle in a fixed position and with all vertices having mode 0. The convergence rate to stationarity in terms of the total variation norm is studied for the special cases with G = KN, the complete graph with N vertices, and when G = mod N. In the former case we prove that as N --> [infinity], ((2pc + pm) 4pcpm)N log N is a threshold for the convergence rate. In the latter case we show that the convergence rate is asymptotically determined by the cover time CN in that the total variation norm after aN2 steps is given by P(CN > aN2). The limit of this probability can in turn be calculated by considering a Brownian motion with two absorbing barriers. In particular, this means that there is no threshold for this case. 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.