The ACO Seminar (2012-2013)

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