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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom