A semidefinite bound for mixing rates of Markov chains

DOI10.1007/3-540-61310-2_15zbMath1414.60059OpenAlexW1486311690MaRDI QIDQ4645923

Nabil Kahale

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

Markov chainexclusion processlength functionsemidefinite programlarge eigenvalue

Mathematics Subject Classification ID

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

Related Items (2)

Logarithmic Sobolev, isoperimetry and transport inequalities on graphs ⋮ Unnamed Item

Cites Work

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

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