A Tight Bound for the Lamplighter Problem
arXiv:math/0610345
Abstract
We settle an open problem, raised by Y. Peres and D. Revelle, concerning the 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.
12 Pages