Hoeffding's inequality for supermartingales (Q449236): Difference between revisions

Let \((\xi_i)_{0\leq i\leq n}\) be a sequence of real valued random variables defined on a probability space \((\Omega,{\mathcal F},\operatorname{P})\) and adapted to a filtration \(({\mathcal F}_i)_{0\leq i\leq n}\) of sub-\(\sigma\)-fields of \({\mathcal F}\), where \(\xi_0=0\) and \({\mathcal F}_0=\{\emptyset,\Omega\}\). Assume that \(\operatorname{E}(\xi_i|{\mathcal F}_{i-1})\leq0\) for \(1\leq i\leq n\) so that \((\xi_i,{\mathcal F}_i)_{0\leq i\leq n}\) is a supermartingale difference sequence. Set \(X_0=0\) and \(X_k=\sum_{i=1}^k\xi_i,1\leq k\leq n,\) as well as \(\langle X\rangle_0=0\) and \(\langle X\rangle_k=\sum_{i=1}^k\operatorname{E}(\xi_k^2|{\mathcal F}_{i-1}),1\leq k\leq n,\) for the quadratic characteristic of the supermartingale \((X_k,{\mathcal F}_k)_{0\leq k\leq n}\). Under the assumption \(\xi_i\leq1\), for \(1\leq i\leq n\), a bound on \(\operatorname{P}(X_k\geq x\text{ and }\langle X\rangle_k\leq v^2 {\text{ for some }} k\in\{1,2,\dotsc,n\})\) is derived for any \(x\geq0\) and \(v>0\) which implies Hoeffding's classical exponential inequality for independent summands. A very detailed comparison of the result to numerous known exponential bounds on tail probabilities in the martingale case is provided so that the paper does not only contribute to this area but can also be recommended as a very informative introduction to the field for the non-expert.