Optimal Hoeffding bounds for discrete reversible Markov chains.

DOI10.1214/105051604000000170zbMath1056.60070arXivmath/0405296OpenAlexW3101473884MaRDI QIDQ1879898

Carlos Antonio León, François Perron

Publication date: 15 September 2004

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0405296

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Numerical analysis or methods applied to Markov chains (65C40)

Related Items (20)

A Hoeffding inequality for Markov chains ⋮ Adaptive Huber regression on Markov-dependent data ⋮ Hypothesis testing for Markov chain Monte Carlo ⋮ Transport-information inequalities for Markov chains ⋮ Mixing of the upper triangular matrix walk ⋮ Rigorous confidence bounds for MCMC under a geometric drift condition ⋮ A martingale minimax exponential inequality for Markov chains ⋮ Hoeffding's inequality for non-irreducible Markov models ⋮ Tail Estimates for Sums of Variables Sampled by a Random Walk ⋮ Nonasymptotic bounds on the estimation error of MCMC algorithms ⋮ Hoeffding's inequalities for geometrically ergodic Markov chains on general state space ⋮ Function-specific mixing times and concentration away from equilibrium ⋮ Uniform mixing time for random walk on lamplighter graphs ⋮ Concentration of Markov chains with bounded moments ⋮ Fast Low-Cost Estimation of Network Properties Using Random Walks ⋮ Large deviations and full Edgeworth expansions for finite Markov chains with applications to the analysis of genomic sequences ⋮ The Littlewood-Offord problem for Markov chains ⋮ Mixing time estimation in reversible Markov chains from a single sample path ⋮ Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes ⋮ Unnamed Item

Cites Work

• Chernoff-type bound for finite Markov chains
• A probability inequality for the occupation measure of a reversible Markov chain
• Optimum Monte-Carlo sampling using Markov chains
• A Chernoff Bound for Random Walks on Expander Graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Inequalities: theory of majorization and its applications
• Unnamed Item
• Unnamed Item

This page was built for publication: Optimal Hoeffding bounds for discrete reversible Markov chains.