A Hoeffding inequality for Markov chains using a generalized inverse
type: Item
instance of: scholarly article
title: A Hoeffding inequality for Markov chains using a generalized inverse
zbMATH Open document ID: 1170.60025
author: Thomas R. Boucher
published in: Statistics \& Probability Letters
publication date: 2009-04-14T00:00:00Z
review text: 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}.\)
reviewed by: Marius Iosifescu
Mathematics Subject Classification ID: 60J05
Mathematics Subject Classification ID: 60F10
Mathematics Subject Classification ID: 60G42
zbMATH DE Number: 5543795
zbMATH Keywords: Markov chain
zbMATH Keywords: Hoeffding inequality
zbMATH Keywords: generalized inverse
zbMATH Keywords: martingale difference
MaRDI profile type: Publication
full work available at URL: j.spl.2008.12.018
OpenAlex ID: W2009290156
cites work: On Hoeffding's inequalities.
cites work: Q3207128
cites work: Q4881152
cites work: Hoeffding's inequality for uniformly ergodic Markov chains
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Markov chains and stochastic stability
cites work: Asymptotic variance of functionals of discrete-time Markov chains via the Drazin inverse.
cites work: The missing factor in Hoeffding's inequalities
DOI: 10.1016/J.SPL.2008.12.018
Recommended article: A Hoeffding inequality for Markov chains
Recommended article: Applications of generalized inverses to Markov chains
Recommended article: Hoeffding's inequality for uniformly ergodic Markov chains
Recommended article: Q5159407
Recommended article: Generalization of a Markov inequality
Recommended article: A generalization of Markov's inequality
Recommended article: Hoeffding's inequality for non-irreducible Markov models
description: scientific article; zbMATH DE number 5543795