A Hoeffding inequality for Markov chains

Abstract

We prove deviation bounds for the random variable ${\sum }_{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]\to [-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 ${\max }_i\{a_i\}\sqrt{n}.$ 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.

11 pages