A semidefinite bound for mixing rates of Markov chains

DOI10.1007/3-540-61310-2_15MaRDI QIDQ4645923zbMATH OpenOpenAlexFDO

Authors Nabil Kahalé

Publication date 11 January 2019

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61310-2_15

zbMATH Keywords

exclusion processlarge eigenvaluelength functionMarkov chainsemidefinite program

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1097578
• Bounding fastest mixing
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• On the Convergence of Reversible Markov Chains
• Fastest Mixing Markov Chain on a Graph

Cites work

• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximating the Permanent
• Characterization of the subdifferential of some matrix norms
• Comparison theorems for reversible Markov chains
• Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
• Geometric bounds for eigenvalues of Markov chains
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1263187 (Why is no real title available?)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Non-negative matrices and Markov chains. 2nd ed
• Random walks in a convex body and an improved volume algorithm
• Semidefinite Programming
• The ellipsoid method and its consequences in combinatorial optimization
• The geometry of graphs and some of its algorithmic applications

Cited in

(9)

• Bounding fastest mixing
• scientific article; zbMATH DE number 4172979 (Why is no real title available?)
• Logarithmic Sobolev, isoperimetry and transport inequalities on graphs
• scientific article; zbMATH DE number 4216483 (Why is no real title available?)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• scientific article; zbMATH DE number 1097578 (Why is no real title available?)
• A Schur complement Cheeger inequality
• A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
• On Subexponential Mixing Rate for Markov Processes

This page was built for publication: A semidefinite bound for mixing rates of Markov chains

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