Uniformity of the Uncovered Set of Random Walk and Cutoff for Lamplighter Chains
Preprint
Abstract
We show that the measure on markings of $\Z_n^d$, $d \geq 3$, with elements of $\{0,1\}$ given by iid fair coin flips on the range $\CR$ 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 = \tfrac{1}{2}T_\cov(\Z_n^d)$. As a consequence of our methods, we show that the total variation mixing time of the random walk on the lamplighter graph $\Z_2 \wr \Z_n^d$, $d \geq 3$, has a cutoff with threshold $\tfrac{1}{2} T_\cov(\Z_n^d)$. 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 14 references indexed in Scilit:
- Late points for random walks in two dimensionsThe Annals of Probability, 2006
- Random walks on supercritical percolation clustersThe Annals of Probability, 2004
- On the mixing time of a simple random walk on the super critical percolation clusterProbability Theory and Related Fields, 2003
- Brownian Motion on Compact Manifolds: Cover Time and Late PointsElectronic Journal of Probability, 2003
- Kac’s moment formula and the Feynman–Kac formula for additive functionals of a Markov processStochastic Processes and their Applications, 1999
- Covering of a finite lattice by a random walkPhysica A: Statistical Mechanics and its Applications, 1991
- Asymptotic analysis of a random walk on a hypercube with many dimensionsRandom Structures & Algorithms, 1990
- Covering Problems for Markov ChainsThe Annals of Probability, 1988
- Random walks on finite groups and rapidly mixing markov chains1983
- Generating a random permutation with random transpositionsProbability Theory and Related Fields, 1981