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
2021912525 2889042315 2807635458 2087384099
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. Oliveira conjectured that the order of the mixing time of the exclusion process with @math -particles on an arbitrary @math -vertex graph is at most that of the mixing-time of @math independent particles. We verify this up to a constant factor for @math -regular graphs when each edge rings at rate @math in various cases: (1) when @math or (2) when @math the spectral-gap of a single walk is @math and @math or (3) when @math for some constant @math . In these cases our analysis yields a probabilistic proof of a weaker version of Aldous' famous spectral-gap conjecture (resolved by ). We also prove a general bound which is at worst @math , which is within a @math factor from Oliveira's conjecture when @math . As applications we get new mixing bounds: (a) @math for expanders, (b) order @math for the hypercube @math and (c) order @math for vertex-transitive graphs of moderate growth and for supercritical percolation on a fixed dimensional torus. We consider the simple exclusion process with @math particles on a segment of length @math performing random walks with transition @math to the right and @math to the left. We focus on the case where the asymmetry in the jump rates @math vanishes in the limit when @math and @math tend to infinity, and obtain sharp asymptotics for the mixing times of this sequence of Markov chains in the two cases where the asymmetry is either much larger or much smaller than @math . We show that in the former case ( @math ), the mixing time corresponds to the time needed to reach macroscopic equilibrium, like for the strongly asymmetric (i.e. constant @math ) case studied in [LL18], while the latter case ( @math ) macroscopic equilibrium is not sufficient for mixing and one must wait till local fluctuations equilibrate, similarly to what happens in the symmetric case worked out in [Lac16b]. In both cases, convergence to equilibrium is abrupt: we have a cutoff phenomenon for the total-variation distance. We present a conjecture for the remaining regime when the asymmetry is of order @math . Let @math be the largest component of the Erdős–Renyi random graph @math . The mixing time of random walk on @math in the strictly supercritical regime, p = c n with fixed c > 1, was shown to have order log2n by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In the critical window, p = (1 + e) n where λ = e3n is bounded, Nachmias and Peres proved that the mixing time on @math is of order n. However, it was unclear how to interpolate between these results, and estimate the mixing time as the giant component emerges from the critical window. Indeed, even the asymptotics of the diameter of @math in this regime were only recently obtained by Riordan and Wormald, as well as the present authors and Kim. In this paper, we show that for p = (1 + e) n with λ = e3n → ∞ and λ = o(n), the mixing time on @math is with high probability of order (n λ)log2λ. In addition, we show that this is the order of the largest mixing time over all components, both in the slightly supercritical and in the slightly subcritical regime [i.e., p = (1 − e) n with λ as above].