$t_{\mathrm{rel}}(G^\ast)\asymp t_{\mathrm{hit}}(G)$ for lamplighter chains

Let $(G_n)$ be any sequence of connected graphs with $|V_n|\to\infty$. Over each $G_n$ two chains are compared. The base walk is the lazy simple random walk on $G_n$ (hold with probability $\tfrac12$, else move to a uniform neighbour), with maximal hitting time $t_{\mathrm{hit}}(G_n)=\max_{x,y}\mathbb E_x(\tau_y)$, the worst expected time to reach one vertex from another (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 step of the base walk, and randomizes the lamp at the new position. Among the eigenvalues of a chain (real $\lambda$ with $Pf=\lambda f$, $f\ne0$), $\lambda_\star$ is the largest absolute value of an eigenvalue $\ne1$, and the relaxation time is $t_{\mathrm{rel}}=(1-\lambda_\star)^{-1}$ (Mission VII).

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

The lamplighter's slowest mode is governed by the base walk's worst hitting time: to decorrelate, the lamplighter must revisit far-away lamps. The lower bound tests the variational characterization of the gap (Mission VII) with an eigenfunction built from an unvisited-vertex indicator; the upper bound is a coupling-contraction estimate. Together with the companion theorem ($t_{\mathrm{mix}}\asymp t_{\mathrm{cov}}$), the lamplighter ties the hitting, cover, relaxation, and mixing parameters of the whole series into one family.