0.1 Hoeffding’s Inequality
Hoeffding’s inequality is a result considering Martingale Differences which gives the bound on the degree of fluctuation of a martingale.
Let \((X_{n}, \mathcal{F}_{n})\) be a martingale, and suppose that there exists a sequence \(\{ K_{n} \}\) of real numbers such that \(\mathbb{P}(\lvert X_{n}-X_{n-1} \rvert\leq K_{n})=1\) for all \(n\). Then for \(x>0\) \[ \mathbb{P}(\lvert X_{n}-X_{0} \rvert \geq x)\leq 2\exp\left( - \frac{1}{2}x^2 \Big/ \sum_{i=1}^n K_{i}^2 \right). \]
We interpret this result to read that if the martingale differences are bounded almost surely, then there is a small change of a large deviation of \(X_{n}\) from its initial value \(X_{0}\).