Vertex and edge expansion properties for rapid mixing

Simple item page
dc.creatorMontenegro, Ravi
dc.date2004-10-26
dc.date.accessioned2026-07-07T12:59:44Z
dc.date.available2026-07-07T12:59:44Z
dc.descriptionWe show a strict hierarchy among various edge and vertex expansion properties of Markov chains. This gives easy proofs of a range of bounds, both classical and new, on chi-square distance, spectral gap and mixing time. The 2-gradient is then used to give an isoperimetric proof that a random walk on the grid [k]^n mixes in time O*(k^2 n).
dc.identifierhttps://arxiv.org/abs/math/0410545
dc.identifierhttp://arxiv.org/abs/math/0410545
dc.identifierRandom Structures & Algorithms, volume 26:1-2, pp. 52-68, 2005
dc.identifierdoi:10.1002/rsa.20045
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/225661
dc.subjectProbability
dc.subject60J10
dc.titleVertex and edge expansion properties for rapid mixing
dc.typetext

Files

Collections

arXiv