Cut-off for lamplighter chains on tori: dimension interpolation and phase transition

Abstract

Given a finite, connected graph $\SG$, the lamplighter chain on $\SG$ is the lazy random walk $X^\diamond$ on the associated lamplighter graph $\SG^\diamond=\Z_2 \wr \SG$. The mixing time of the lamplighter chain on the torus $\Z_n^d$ is known to have a cutoff at a time asymptotic to the cover time of $\Z_n^d$ if $d=2$, and to half the cover time if $d \ge 3$. We show that the mixing time of the lamplighter chain on $\ttorus=\Z_n^2 \times \Z_{a \log n}$ has a cutoff at $\psi(a)$ times the cover time of $\ttorus$ as $n \to \infty$, where $\psi$ is an explicit weakly decreasing map from $(0,\infty)$ onto $[1/2,1)$. In particular, as $a > 0$ varies, the threshold continuously interpolates between the known thresholds for $\Z_n^2$ and $\Z_n^3$. Perhaps surprisingly, we find a phase transition (non-smoothness of $\psi$) at the point $a_=\pi r_3 (1+\sqrt{2})$, where high dimensional behavior ($\psi(a)=1/2$ for all $a \ge a_$) commences. Here $r_3$ is the effective resistance from $0$ to $\infty$ in $\Z^3$.