A Hoeffding inequality for Markov chains

Shravas Rao

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]$,…