A Tight Bound for the Lamplighter Problem

2006/10/10 by Murali K. Ganapathy, Ganapathy, Murali K., Prasad Tetali +1
Engineering · Mathematics · #60J10 (Primary) #60J27 #68W20 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Packing Problems #Probability (math.PR) #math.CO #math.PR #msc:60J10 #msc:60J27 #msc:68W20

paper · pdf · doi:10.48550/arxiv.math/0610345

12 Pages

arxiv created 2006/10/10 · openalex publication_date 2006/10/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We settle an open problem, raised by Y. Peres and D. Revelle, concerning the L² mixing time of the random walk on the lamplighter graph. We also provide general bounds relating the entropy decay of a Markov chain to the separation distance of the chain, and show that the lamplighter graphs once again provide examples of tightness of our results.

Related

• Mixing times for random walks on finite lamplighter groups
• Cutoff for lamplighter chains on fractals
• Lamplighter Random Walks and Entropy-Sensitivity of Languages
• A note on mixing times of planar random walks
• Lamplighter random walks on fractals