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

Abstract

Given a finite, connected graph $G$, the lamplighter chain on $G$ is the lazy random walk $X^{\diamond }$ on the associated lamplighter graph $G^{\diamond }={\mathbf{Z}}_2\wr G$. The mixing time of the lamplighter chain on the torus ${\mathbf{Z}}_n^d$ is known to have a cutoff at a time asymptotic to the cover time of ${\mathbf{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 $G_n(a)={\mathbf{Z}}_n^2\times {\mathbf{Z}}_{a\log n}$ has a cutoff at $\psi (a)$ times the cover time of $G_n(a)$ 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 ${\mathbf{Z}}_n^2$ and ${\mathbf{Z}}_n^3$. Perhaps surprisingly, we find a phase transition (non-smoothness of $\psi$) at the point $a_{\ast }=\pi r_3(1+\sqrt{2})$, where high dimensional behavior ($\psi (a)=1/2$ for all $a\ge a_{\ast }$) commences. Here $r_3$ is the effective resistance from $0$ to $\infty$ in ${\mathbf{Z}}^3$.

40 pages and 5 figures