$t_{\mathrm{mix}}(G^\ast)\asymp t_{\mathrm{cov}}(G)$ for lamplighter chains

Let $(G_n)$ be any sequence of connected graphs with $|V_n|\to\infty$. The base walk on $G_n$ is the lazy simple random walk (hold with probability $\tfrac12$, else move to a uniform neighbour); its cover time $t_{\mathrm{cov}}(G_n)$ is the worst, over starting vertices, expected time to have visited every vertex (Mission VI). The lamplighter chain $G_n^\ast$ has states (lamp configuration in $\{0,1\}^{V_n}$, lamplighter position); one step randomizes the lamp at the current position, moves the lamplighter one base-walk step, and randomizes the lamp at the new position; its stationary distribution is uniform lamps times the base walk's stationary distribution. The mixing time $t_{\mathrm{mix}}(G_n^\ast)$ is the first $t$ at which the worst-case total variation distance $\max_s\|P^t(s,\cdot)-\pi\|_{TV}$ drops to $1/4$, with $\|\mu-\nu\|_{TV}=\max_A|\mu(A)-\nu(A)|$.

The theorem (Theorem 19.2 of Levin–Peres–Wilmer) asserts: there are constants $c_1,c_2>0$ such that for all sufficiently large $n$,

The lamp configuration looks uniform only once (essentially) every lamp has been touched, so the lamplighter mixes exactly when the base walk has covered the graph — the cleanest theorem converting cover times into mixing times. The upper bound couples two lamplighters after a cover-time's worth of steps; the lower bound shows that before a constant fraction of the cover time, the set of unvisited lamps betrays the starting configuration (via the separation–total-variation relation of this mission).