Optimal Hoeffding bounds for discrete reversible Markov chains. (Q1879898)

Let \(\{X_k:k\geq 1\}\) be an ergodic and reversible Markov chain with finite state space \(E\), transition probability matrix \(P\) and stationary distribution \(\pi\). Consider the map \(f:E\to [0,1]\) and let \(\mu=E_\pi f\). Further let \(\lambda\) be the second largest eigenvalue of \(P\) and \(\lambda_0= \max\{\lambda,0\}\). The main result of the paper consists in obtaining an optimal exponential bound for \(P(S_n\geq n(\mu+ \varepsilon))\) in terms of \(\mu,n, \varepsilon\), and \(\lambda_0\), where \(S_n=(1/n) \sum^n_{j=1} f(X_j)\). This bound improves on others previously obtained, in particular that by \textit{P. Lezaud} [Ann. Appl. Probab. 8, No. 3, 849--867 (1998; Zbl 0938.60027)].