2013/12/16 by Amir Dembo, Jian Ding, Dembo, Amir +5
Mathematics · Physics and Astronomy · #60G50 #60J10 #82C41 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #math.PR #msc:60G50 #msc:60J10 #msc:82C41
paper · pdf · doi:10.48550/arxiv.1312.4522
40 pages and 5 figures
openalex publication_date 2013/12/16 · arxiv created 2018/08/14 · arxiv updated 2018/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Z2 \wr G. The mixing time of the lamplighter chain on the torus \mathbf Znd is known to have a cutoff at a time asymptotic to the cover time of \mathbf Znd if d=2, and to half the cover time if d ≥ 3. We show that the mixing time of the lamplighter chain on Gn(a)=\mathbf Zn2 × \mathbf Za log n has a cutoff at ψ(a) times the cover time of Gn(a) as n → ∞, where ψ is an explicit weakly decreasing map from (0,∞) onto [1/2,1). In particular, as a > 0 varies, the threshold continuously interpolates between the known thresholds for \mathbf Zn2 and \mathbf Zn3. Perhaps surprisingly, we find a phase transition (non-smoothness of ψ) at the point a_*=πr3 (1+√(2)), where high dimensional behavior (ψ(a)=1/2 for all a ≥ a_*) commences. Here r3 is the effective resistance from 0 to ∞ in \mathbf Z3.