9.2 Martingale Differences and Hoeffding’s Inequality
Definition 9.2.1. The martingale differences of \(\{X_n\}\) are \[D_n = X_n - X_{n-1},\qquad n\geq 1,\] so that \(X_n = X_0 + \sum _{i=1}^{n}D_i\). The martingale property says exactly that \(E\left (D_{n+1}\mid Y_0,\dots ,Y_n\right )=0\): each increment is conditionally centred given the past.
Result 9.2.2. Martingale differences are uncorrelated, and if \(E\left (X_n^{2}\right )<\infty \) then \[\Var (X_n) = \Var (X_0) + \sum _{i=1}^{n}E\left (D_i^{2}\right ).\]
Proof. For \(i<j\), conditioning on the history up to \(j-1\) and using that \(D_i\) is determined by it, \[E\left (D_iD_j\right ) = E\left [D_i\,E\left (D_j\mid Y_0,\dots ,Y_{j-1}\right )\right ] = 0 .\] Uncorrelated terms have additive variances, which gives the display. □
Note. The variances add exactly as they would for independent summands, even though the differences need not be independent — only conditionally centred. This is the practical value of the martingale property: it buys the variance calculation without the much stronger assumption of independence, which is why martingales appear wherever dependence cannot be assumed away.
Theorem 9.2.3 (Azuma–Hoeffding inequality). Let \(\{X_n\}\) be a martingale whose differences are bounded, \(\left |D_i\right |\leq c_i\) almost surely. Then for every \(t>0\) \[P\left (\left |X_n - X_0\right | \geq t\right ) \;\leq \; 2\exp \left \{-\frac {t^{2}}{2\sum _{i=1}^{n}c_i^{2}}\right \}.\]
Remark. Compare this with Chebyshev’s inequality, which under the same variance would give a bound decaying like \(t^{-2}\). Azuma–Hoeffding decays like \(e^{-t^{2}}\) — incomparably faster — and the price is the assumption that the increments are bounded. It is the martingale generalisation of the Chernoff bounds met earlier in these notes, and it is proved the same way, by bounding the moment generating function of each increment and multiplying.
With all \(c_i=c\) the bound reads \(2\exp \left \{-t^{2}/2nc^{2}\right \}\), so deviations of order \(\sqrt {n}\) are the natural scale — which is the central limit theorem’s scale, arrived at here without any distributional assumption at all.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.