Uniformity of the uncovered set of random walk and cutoff for lamplighter chains

preprint2012arXivOpen access

Abstract

We show that the measure on markings of Znd\mathbf {Z}_n^d, d≥3d\geq3, with elements of 0,1{0,1} given by i.i.d. fair coin flips on the range R\mathcal {R} of a random walk XX run until time TT and 0 otherwise becomes indistinguishable from the uniform measure on such markings at the threshold T=1/2Tcov(Znd)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 Z2≀Znd\mathbf {Z}_2\wr \mathbf {Z}_n^d, d≥3d\geq3, has a cutoff with threshold 1/2Tcov(Znd)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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.