Mixing times for uniformly ergodic Markov chains

DOI10.1016/S0304-4149(97)00037-9zbMath0941.60080OpenAlexW2028548064MaRDI QIDQ1965874

László Lovász, Peter M. Winkler, David J. Aldous

Publication date: 1 March 2000

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-4149(97)00037-9

zbMATH Keywords

stopping timeMarkov chainrandomized algorithmmixing timeminorization

Mathematics Subject Classification ID

Discrete-time Markov processes on general state spaces (60J05)

Related Items

Tight inequalities among set hitting times in Markov chains, Faster mixing and small bottlenecks, Exact mixing times for random walks on trees, Weak Convergence Rates of Population Versus Single-Chain Stochastic Approximation MCMC Algorithms, Nonlinear stochastic operators and associated inhomogeneous entangled quantum Markov chains, On a \(\psi\)-mixing property for entangled Markov chains, Mixing time of near-critical random graphs, A Hitting Time Formula for the Discrete Green's Function, Asymptotic fitness distribution in the Bak-Sneppen model of biological evolution with four species, Quantum mixing of Markov chains for special distributions, The best mixing time for random walks on trees, On the Markov Transition Kernels for First Passage Percolation on the Ladder, On the maximal value of spectral gap for some birth and death processes, Exit Frequency Matrices for Finite Markov Chains, Learning from uniformly ergodic Markov chains, Nonstationary Markovian queues, On the Hill relation and the mean reaction time for metastable processes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nash inequalities for finite Markov chains
• Markov chains and stochastic stability
• Strong stationary times via a new form of duality
• Trailing the dovetail shuffle to its lair
• Stopping times for recurrent Markov processes
• Remarks on the filling scheme for recurrent Markov chains
• Sampling from log-concave distributions
• Walks on generating sets of Abelian groups
• The stopping distributions of a Markov process
• Approximating the Permanent
• General Irreducible Markov Chains and Non-Negative Operators
• Some Inequalities for Reversible Markov Chains
• A simple coupling of renewal processes
• Occupation measures for Markov chains
• Maximal coupling
• Random walks in a convex body and an improved volume algorithm
• Random walks and anO*(n5) volume algorithm for convex bodies
• Stratified random walks on then-cube
• The cutoff phenomenon in finite Markov chains.