Jan 17, 3:30pm, Wean 8220

Jason Miller, MIT

Uniformity of the Uncovered Set of Random Walk and Cutoff for Lamplighter Chains

Jason Miller, MIT

Uniformity of the Uncovered Set of Random Walk and Cutoff for Lamplighter Chains

Abstract:

We show that the threshold for a subset sampled uniformly from the
range of a random walk on Z_n^d, d >= 3, to become
indistinguishable from a uniformly chosen subset of Z_n^d is half
the cover time. 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 >= 3, has a cutoff with threshold at half the cover
time. We given a general criterion under which both of these results
hold; other examples for which this applies include bounded degree
expander families, 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.

This is joint work with Yuval Peres