A Tight Bound for the Lamplighter Problem

Simple item page
dc.creatorGanapathy, Murali K.
dc.creatorTetali, Prasad
dc.date2006-10-10
dc.date.accessioned2026-07-07T07:28:56Z
dc.date.available2026-07-07T07:28:56Z
dc.descriptionWe 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.
dc.description12 Pages
dc.identifierhttps://arxiv.org/abs/math/0610345
dc.identifierhttp://arxiv.org/abs/math/0610345
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/117914
dc.subjectProbability
dc.subjectCombinatorics
dc.subject60J10 (Primary) ; 60J27; 68W20 (Secondary)
dc.titleA Tight Bound for the Lamplighter Problem
dc.typetext

Files

Collections

arXiv