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

DOI10.1214/10-AOP624zbMATH Open1251.60058arXiv0912.5523WikidataQ101584061 ScholiaQ101584061MaRDI QIDQ414277

Author name not available (Why is that?)

Publication date: 11 May 2012

Published in: (Search for Journal in Brave)

Abstract: We show that the measure on markings of

m a t h b f Z_{n}^{d}

,

d g e q 3

, with elements of

0, 1

given by i.i.d. fair coin flips on the range

m a t h c a l 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 / 2 T_{m a t h r m c o v} (m a t h b f 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

m a t h b f Z_{2} w r m a t h b f Z_{n}^{d}

,

d g e q 3

, has a cutoff with threshold

1 / 2 T_{m a t h r m c o v} (m a t h b f 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.

Full work available at URL: https://arxiv.org/abs/0912.5523

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Uniformity of the uncovered set of random walk and cutoff for lamplighter chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414277)