A Hoeffding inequality for Markov chains

DOI10.1214/19-ECP219zbMATH Open1412.60049arXiv1806.11519MaRDI QIDQ2631808FDOQ2631808

Authors: Shravas Rao 

Publication date: 16 May 2019

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

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.

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

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

zbMATH Keywords

Markov chainrandom matricesgeneric chainingHoeffding bound

Mathematics Subject Classification ID

Large deviations (60F10)

Cites Work

• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• An introduction to matrix concentration inequalities
• Upper and lower bounds for stochastic processes. Modern methods and classical problems
• Regularity of Gaussian processes
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• Strong converse for identification via quantum channels
• Chernoff-type bound for finite Markov chains
• A Chernoff Bound for Random Walks on Expander Graphs
• Title not available (Why is that?)
• Concentration of Markov chains with bounded moments
• Randomness-efficient sampling within NC\(^{1}\)
• Title not available (Why is that?)
• A matrix expander Chernoff bound
• A probability inequality for the occupation measure of a reversible Markov chain
• Chernoff-Hoeffding bounds for Markov chains: generalized and simplified
• Large Deviation Bounds for Markov Chains
• 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

Cited In (13)

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

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)