A Tight Bound for the Lamplighter Problem

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
12 Pages

Keywords

Probability, Combinatorics, 60J10 (Primary) ; 60J27; 68W20 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/117914

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0610345
 http://arxiv.org/abs/math/0610345

Collections

arXiv