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

Let \(G_n = (V_n, E_n)\) be a sequence of finite connected graphs with \(\lim_{n \to \infty} | V_n | = \infty\). Consider a lazy random walk (a discrete-time, simple symmetric random walk with holding) \(X\) on \(G_n\). Let \(T_{\mathrm{cov}} (G_n)\) denote the expected cover time of \(G_n\) by \(X\), that is, the expected first time at which \(X\) has visited every vertex in \(V_n\). For \(\alpha >0\), let \(\mathcal{R} ( \alpha; G_n )\) denote the random subset of \(V_n\) visited by \(X\) before time \(\alpha T_{\mathrm{cov}} (G_n)\). The authors study the extent to which \(\mathcal{R} ( \alpha; G_n )\) is ``uniformly random'' for families of graphs \(G_n\) satisfying certain conditions. The main result is stated in terms of the total variation distance between the uniform distribution on subsets of \(V_n\) and the probability measure \(\mu ( \, \cdot \,; \alpha , G_n)\) induced by independent Bernoulli thinning of the set \(\mathcal{R} ( \alpha; G_n )\). The authors give conditions on the graphs \(G_n\) under which a sharp threshold is observed at \(\alpha = 1/2\), in the sense that, for \(\alpha < 1/2\) (\(\alpha > 1/2\)), the limit, as \(n \to \infty\), of the distance of \(\mu\) from uniformity is \(1\) (\(0\)). The conditions imposed on \(G_n\) include a form of uniform local transience and a mild connectivity assumption. Examples of graphs presented for which the main result holds include the \(d\)-dimensional discrete torus \(\mathbb{Z}_n^d\), \(d \geq 3\); a growing section of the supercritical percolation cluster on \(\mathbb{Z}^d\), \(d\geq 3\); random \(d\)-regular graphs, \(d \geq 3\); the hypercube \(\mathbb{Z}_2^n\); and Cayley graphs (set as ``Caley graphs'' throughout the text) of the symmetric group on \(n\) elements generated by transpositions. Another consequence of the techniques is a sharp cutoff result for the total variation mixing time of the random walk on certain lamplighter graphs.