Faster mixing and small bottlenecks

DOI10.1007/s00440-006-0003-8zbMath1113.60073OpenAlexW2013770427MaRDI QIDQ863483

Bruce A. Reed, Nikolaos Fountoulakis

Publication date: 26 January 2007

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00440-006-0003-8

zbMATH Keywords

Markov chainstationary distributionmixing timeconductance

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Related Items

The mixing time of the giant component of a random graph, Smoothed Analysis on Connected Graphs, Speeding up random walk mixing by starting from a uniform vertex, Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point, Mixing time of near-critical random graphs, Random walks on the random graph, On sensitivity of mixing times and cutoff, Mixing time bounds via bottleneck sequences, Cutoff for random walk on dynamical Erdős-Rényi graph, Does adding more agents make a difference? A case study of cover time for the rotor-router, The Mixing Time of the Newman-Watts Small-World Model, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On the mixing time of a simple random walk on the super critical percolation cluster
• The random-cluster model on the complete graph
• Mixing times for uniformly ergodic Markov chains
• Faster mixing via average conductance
• Polynomial-Time Approximation Algorithms for the Ising Model
• Some Inequalities for Reversible Markov Chains
• Random walks in a convex body and an improved volume algorithm
• Random walks and anO*(n5) volume algorithm for convex bodies
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
• A critical point for random graphs with a given degree sequence
• Equation of State Calculations by Fast Computing Machines
• Blocking Conductance and Mixing in Random Walks