Cutoff for lamplighter chains on fractals

2017/11/08 by Amir Dembo, Takashi Kumagai, Dembo, Amir +3
Mathematics · Physics and Astronomy · #28A80 #35K08 #60J10 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #math.PR #msc:28A80 #msc:35K08 #msc:60J10

paper · pdf · doi:10.48550/arxiv.1711.02788

19 pages, 9 figures

openalex publication_date 2017/11/08 · arxiv created 2018/07/15 · arxiv updated 2018/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the total-variation mixing time of the lamplighter random walk on fractal graphs exhibit sharp cutoff when the underlying graph is transient (namely of spectral dimension greater than two). In contrast, we show that such cutoff can not occur for strongly recurrent underlying graphs (i.e. of spectral dimension less than two).

Related

• Mixing times for random walks on finite lamplighter groups
• Cut-off for lamplighter chains on tori: dimension interpolation and phase transition
• A Tight Bound for the Lamplighter Problem
• Lamplighter random walks on fractals
• Cutoff for random walks on graphs with bottlenecks