A Tight Bound for the Lamplighter Problem

Authors Murali K. Ganapathy, Prasad Tetali

Publication date 10 October 2006

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Continuous-time Markov processes on discrete state spaces (60J27) Randomized algorithms (68W20)

Abstract: We settle an open problem, raised by Y. Peres and D. Revelle, concerning the

L^{2}

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.

This page was built for publication: A Tight Bound for the Lamplighter Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6478012)