Mixing times for uniformly ergodic Markov chains

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

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 (17)

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

• 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.
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Mixing times for uniformly ergodic Markov chains