Chernoff-type bound for finite Markov chains (Q1296608): Difference between revisions

Let \((X_n)\) be an irreducible Markov chain on a finite set \(G\) with transition matrix \(P\) and stationary distribution \(\pi\). Then, for any function \(f\) and for any initial distribution \(q\) the empirical mean \(n^{-1}\sum^n_{i= 1}f(X_i)\) converges in probability to \(\pi f= \sum_y \pi(y)f(y)\). The paper gives exponential bounds for \(P_q\left\{ n^{-1}\sum^n_{i= 1} f(X_i)-\pi f\geq \gamma\right\}\). These bounds involve spectral gap of \(P\).