Blocking Conductance and Mixing in Random Walks

DOI10.1017/S0963548306007504zbMath1132.60039MaRDI QIDQ5295401

Ravi Montenegro, László Lovász, Ravindran Kannan

Publication date: 30 July 2007

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

convex bodiessampling algorithmsrapid mixingbull walkcontinuous state Markov chains

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Discrete-time Markov processes on general state spaces (60J05) Continuous-time Markov processes on discrete state spaces (60J27)

Related Items

Faster mixing and small bottlenecks, Unnamed Item, Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile, A sharp isoperimetric bound for convex bodies, Unnamed Item, The simple random walk and max-degree walk on a directed graph, Intersection Conductance and Canonical Alternating Paths: Methods for General Finite Markov Chains