Faster mixing and small bottlenecks

DOI10.1007/S00440-006-0003-8MaRDI QIDQ863483zbMATH OpenOpenAlexFDO

Authors Nikolaos Fountoulakis, Bruce Reed

Publication date 26 January 2007

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

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

zbMATH Keywords

Markov chainmixing timestationary distributionconductance

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 18982
• Vertex and edge expansion properties for rapid mixing
• The rapid mixing of random walks defined by an \(n\)-cube
• scientific article; zbMATH DE number 1195779
• Evolving sets, mixing and heat kernel bounds

Cites work

• scientific article; zbMATH DE number 1263183 (Why is no real title available?)
• scientific article; zbMATH DE number 1305538 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• Blocking Conductance and Mixing in Random Walks
• Equation of state calculations by fast computing machines
• Faster mixing via average conductance
• Mixing times for uniformly ergodic Markov chains
• On the mixing time of a simple random walk on the super critical percolation cluster
• Polynomial-Time Approximation Algorithms for the Ising Model
• Random walks and anO*(n5) volume algorithm for convex bodies
• Random walks in a convex body and an improved volume algorithm
• Some Inequalities for Reversible Markov Chains
• The random-cluster model on the complete graph
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs

Cited in

(21)

• Expansion in supercritical random subgraphs of expanders and its consequences
• Smoothed Analysis on Connected Graphs
• Random walks on the random graph
• Evolving sets, mixing and heat kernel bounds
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• 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
• Mixing time of near-critical random graphs
• The Mixing Time of the Newman-Watts Small-World Model
• Cutoff for random walk on dynamical Erdős-Rényi graph
• Mixing time bounds via bottleneck sequences
• Geometric bounds on the fastest mixing Markov chain
• Markov chain mixing time on cycles
• The mixing advantage is less than 2
• Sensitivity of mixing times of Cayley graphs
• Intersection conductance and canonical alternating paths: methods for general finite Markov chains
• Speeding up random walk mixing by starting from a uniform vertex
• Sensitivity of mixing times
• On sensitivity of mixing times and cutoff
• scientific article; zbMATH DE number 18982 (Why is no real title available?)
• The mixing time of the giant component of a random graph

This page was built for publication: Faster mixing and small bottlenecks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q863483)