A Hoeffding inequality for Markov chains

DOI10.1214/19-ECP219MaRDI QIDQ2631808zbMATHFDO

Authors 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

Markov chainrandom matricesgeneric chainingHoeffding bound

Mathematics Subject Classification ID

Large deviations (60F10)

Abstract: We prove deviation bounds for the random variable $su{m}_{i=1}^n{f}_i(Y_i)$ in which ${Y_i}_{i=1}^{infty}$ is a Markov chain with stationary distribution and state space $[N]$, and $f_i:[N]ightarrow[-a_i,a_i]$. Our bound improves upon previously known bounds in that the dependence is on $sqrt{a}_1^2+cdots+a_n^2$ rather than $ma{x}_i{a}_{i}sqrtn.$ We also prove deviation bounds for certain types of sums of vector--valued random variables obtained from a Markov chain in a similar manner. One application includes bounding the expected value of the Schatten $infty$-norm of a random matrix whose entries are obtained from a Markov chain.

Recommendations

• Hoeffding's inequality for uniformly ergodic Markov chains
• Chernoff-Hoeffding bounds for Markov chains: generalized and simplified
• Hoeffding's inequalities for geometrically ergodic Markov chains on general state space
• Sharp bounds for the tails of functionals of Markov chains
• Concentration of Markov chains with bounded moments

Cites work

• scientific article; zbMATH DE number 6677410 (Why is no real title available?)
• scientific article; zbMATH DE number 1022519 (Why is no real title available?)
• scientific article; zbMATH DE number 7415082 (Why is no real title available?)
• A Chernoff Bound for Random Walks on Expander Graphs
• A matrix expander Chernoff bound
• A probability inequality for the occupation measure of a reversible Markov chain
• An introduction to matrix concentration inequalities
• Chernoff-Hoeffding bounds for Markov chains: generalized and simplified
• Chernoff-type bound for finite Markov chains
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• Concentration of Markov chains with bounded moments
• Large Deviation Bounds for Markov Chains
• On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon-Roichman graphs
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• Probability Inequalities for Sums of Bounded Random Variables
• Randomness-efficient sampling within NC\(^{1}\)
• Regularity of Gaussian processes
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Strong converse for identification via quantum channels
• Tail Estimates for Sums of Variables Sampled by a Random Walk
• Upper and lower bounds for stochastic processes. Modern methods and classical problems

Cited in

(14)

• A Hoeffding inequality for Markov chains using a generalized inverse
• Chernoff-Hoeffding bounds for Markov chains: generalized and simplified
• \(L^1\)-Poincaré inequality for discrete time Markov chains
• Hoeffding's inequalities for geometrically ergodic Markov chains on general state space
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• Hoeffding's inequality for non-irreducible Markov models
• Concentration of Markov chains with bounded moments
• Une variante de l'inégalité de Cheeger pour les chaînes de Markov finies
• An H–theorem for a class of Markov processes
• scientific article; zbMATH DE number 5946288 (Why is no real title available?)
• Sharp bounds for the tails of functionals of Markov chains
• An inequality for the coupling moment in the case of two inhomogeneous Markov chains
• Hoeffding's inequality for uniformly ergodic Markov chains
• On sufficient conditions for spanning structures in dense graphs

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

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