Premium
Vertex and edge expansion properties for rapid mixing
Author(s) -
Montenegro Ravi
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20045
Subject(s) - isoperimetric inequality , vertex (graph theory) , mathematics , mixing (physics) , spectral gap , combinatorics , mathematical proof , markov chain , random walk , struct , range (aeronautics) , square tiling , grid , discrete mathematics , statistical physics , graph , physics , mathematical analysis , geometry , computer science , quantum mechanics , materials science , statistics , composite material , programming language
We 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 ). © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005