Mathematics – Probability
Scientific paper
2009-12-30
Annals of Probability 2012, Vol. 40, No. 2, 535-577
Mathematics
Probability
Published in at http://dx.doi.org/10.1214/10-AOP624 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of
Scientific paper
10.1214/10-AOP624
We show that the measure on markings of $\mathbf {Z}_n^d$, $d\geq3$, with elements of ${0,1}$ given by i.i.d. fair coin flips on the range $\mathcal {R}$ 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=1/2T_{{\mathrm {cov}}}(\mathbf {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 $\mathbf {Z}_2\wr \mathbf {Z}_n^d$, $d\geq3$, has a cutoff with threshold $1/2T_{{\mathrm {cov}}}(\mathbf {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.
Miller Jason J.
Peres Yuval
No associations
LandOfFree
Uniformity of the uncovered set of random walk and cutoff for lamplighter chains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Uniformity of the uncovered set of random walk and cutoff for lamplighter chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uniformity of the uncovered set of random walk and cutoff for lamplighter chains will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-34448