Simple bounds on the convergence rate of an ergodic Markov chain

DOI10.1016/0020-0190(93)90220-4MaRDI QIDQ1209327zbMATH OpenOpenAlexWikidataFDO

Authors Slawomir Pilarski, Tiko Kameda

Publication date 16 May 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90220-4

zbMATH Keywords

analysis of algorithmsconvergence rate of an ergodic Markov chaintransition probability matrix

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Recommendations

• On improved bounds and conditions for the convergence of Markov chains
• Renewal theory and computable convergence rates for geometrically erdgodic Markov chains
• Computable convergence rates for sub-geometric ergodic Markov chains
• Computable bounds for geometric convergence rates of Markov chains
• Explicit bounds for geometric convergence of Markov chains

Cites work

• Approximate counting, uniform generation and rapidly mixing Markov chains
• Eigenvalues and expanders
• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• scientific article; zbMATH DE number 46732 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3437326 (Why is no real title available?)
• Shuffling Cards and Stopping Times
• Time bounds for selection

Cited in

(4)

• Renewal theory and computable convergence rates for geometrically erdgodic Markov chains
• Spectral and graph-theoretic bounds on steady-state-probability estimation performance for an ergodic Markov chain
• scientific article; zbMATH DE number 2051872 (Why is no real title available?)
• Tight space-noise tradeoffs in computing the ergodic measure

This page was built for publication: Simple bounds on the convergence rate of an ergodic Markov chain

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