A Hoeffding inequality for Markov chains

DOI10.1214/19-ECP219zbMath1412.60049arXiv1806.11519MaRDI QIDQ2631808

Shravas Rao

Publication date: 16 May 2019

Published in: Electronic Communications in Probability (Search for Journal in Brave)

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

zbMATH Keywords

random matricesMarkov chaingeneric chainingHoeffding bound

Mathematics Subject Classification ID

Large deviations (60F10)

Related Items (3)

On sufficient conditions for spanning structures in dense graphs ⋮ Hoeffding's inequality for non-irreducible Markov models ⋮ Concentration of Markov chains with bounded moments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Regularity of Gaussian processes
• Randomness-efficient sampling within NC\(^{1}\)
• Chernoff-type bound for finite Markov chains
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• A probability inequality for the occupation measure of a reversible Markov chain
• Concentration of Markov chains with bounded moments
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified
• On the Banach-Space-Valued Azuma Inequality and Small-Set Isoperimetry of Alon–Roichman Graphs
• Tail Estimates for Sums of Variables Sampled by a Random Walk
• A Chernoff Bound for Random Walks on Expander Graphs
• Large Deviation Bounds for Markov Chains
• Strong converse for identification via quantum channels
• A matrix expander Chernoff bound
• Probability Inequalities for Sums of Bounded Random Variables
• Upper and Lower Bounds for Stochastic Processes
• An Introduction to Matrix Concentration Inequalities

This page was built for publication: A Hoeffding inequality for Markov chains