Uniformity of the uncovered set of random walk and cutoff for lamplighter chains
Authors:
- Jason MillerJMJason Miller
- Yuval PeresYPYuval Peres
Open Access
- 1 March 2012
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Probability
- Vol. 40 (2) , 535-577
Abstract
We show that the measure on markings of Znd, d ≥ 3, with elements of {0, 1} given by i.i.d. fair coin flips on the range of a random walk X run until time T and 0 otherwise becomes indistinguishable from the uniform measure on such markings at the threshold T = ½Tcov(Znd). As a consequence of our methods, we show that the total variation mixing time of the random walk on the lamplighter graph Z2 ≀ Znd, d ≥ 3, has a cutoff with threshold ½Tcov(Znd). We give a general criterion under which both of these results hold; other examples for which this applies include bounded degree expander families, the intersection of an infinite supercritical percolation cluster with an increasing family of balls, the hypercube and the Caley graph of the symmetric group generated by transpositions. The proof also yields precise asymptotics for the decay of correlation in the uncovered set.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Late points for random walks in two dimensionsThe Annals of Probability, 2006
- Cover times for Brownian motion and random walks in two dimensionsAnnals of Mathematics, 2004
- On the mixing time of a simple random walk on the super critical percolation clusterProbability Theory and Related Fields, 2003
- Parabolic Harnack inequality and estimates of Markov chains on graphsRevista Matemática Iberoamericana, 1999
- Surface order large deviations for high-density percolationProbability Theory and Related Fields, 1996
- Surface order large deviations for Ising, Potts and percolation modelsProbability Theory and Related Fields, 1996
- Threshold limits for cover timesJournal of Theoretical Probability, 1991
- Covering Problems for Markov ChainsThe Annals of Probability, 1988
- Shuffling Cards and Stopping TimesThe American Mathematical Monthly, 1986
- Random walks on finite groups and rapidly mixing markov chains1983