2004/10/26 by Ravi Montenegro · 3 citations
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Combinatorics #Computer science #Discrete mathematics #Geometry #Graph #Grid #Isoperimetric inequality #Markov Chains and Monte Carlo Methods #Markov chain #Materials science #Mathematical analysis #Mathematical proof #Mathematics #Mixing (physics) #Physics #Quantum mechanics #Random walk #Range (aeronautics) #Spectral gap #Square tiling #Statistical physics #Statistics #Stochastic processes and statistical mechanics #Vertex (graph theory) #math.PR #msc:60J10 #struct
paper · pdf · doi:10.1002/rsa.20045
published in Random Structures and Algorithms 26(1-2), 52-68 (Wiley)
arxiv created 2004/10/26 · openalex publication_date 2004/11/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Abstract 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