A Hoeffding inequality for Markov chains using a generalized inverse (Q1012112)

Consider a measurable space \(\left( X,\mathcal{X}\right) \) and let \( (X_{n})_{n\geq 0}\) be an \(X\)-valued \(\psi \)-irreducible aperiodic Markov process with transition kernel \(P\). Put \(S_{n}\left( g\right) =\sum_{i=0}^{n-1}g\left( X_{i}\right) ,\;n\geq 1\), for any \(\mathcal{X}\) -measurable function \(g:X\rightarrow \mathbb{R}\). Let \(E_{x}\left( E_{p}\right) \) denote the mean value operator conditioned upon \(X_{0}=x\) (under a probability distribution \(p\) of \(X_{0}\)). Assume there exists a bounded \(\mathcal{X}\)-measurable function \(V:X\rightarrow \mathbb{R}\) such that \[ E_{x}\left[ V\left( X_{k}\right) \right] \leq V\left( x\right) -1+bI_{C}\left( x\right) ,\;x\in X,\leqno\left( \ast \right) \] for some \(b<\infty \), an integer \(k<\infty ,\) and a petite set \(C\). This condition implies that the Drazin inverse \(Q^{\#}\) of \(Q:=I-P\) exists and is unique. It is proved that if \(\left( \ast \right) \) holds and \(g\) is a function with \(\left| g\right| \leq V,\) then \[ \sup_{x\in X}P_{x}\left( S_{n}\left( g\right) -E_{\pi }\left[ S_{n}\left( g\right) \right] \geq n\varepsilon \right) \leq \exp \left\{ \frac{-\left( n\varepsilon -2\left\| g\right\| \left\| Q^{\#}\right\| \right) ^{2}}{2n\left\| g\right\| ^{2}\left\| Q^{\#}\right\| ^{2}} \right\} \] for \(\varepsilon >0,\;n>2\left\| g\right\| \left\| Q^{\#}\right\| /\varepsilon ,~\)where \(\left\| g\right\| =\sup_{x\in X}\left| g\left( x\right) \right| ,\left\| Q^{\#}\right\| \) is the operator norm of \(Q^{\#}\,\;\) induced by \(\left\| \cdot \right\|\), and \(\pi \) is the unique stationary distribution of \((X_{n})_{n\geq 0}.\)