hoeffding's inequality

We have \(n\) i.i.d random variables \(X_1,...X_n\) such that \(X_i\) is bounded \(X_i \in [a,b]\). Let \(\mu = \mathbb{E}[X]\).

We want to bound the probability that the average \(\bar{X}_n\) of the r.v.'s is \(\epsilon\) away from \(\mu\). It turns out that this probability falls off exponentially as a function of \(\epsilon\): falling off faster for larger \(n\).

\(\mathbb{P}\left[ |\hat{X} - \mu| \geq \epsilon \right] \leq 2\exp\left(-\frac{2n\epsilon^2}{(b-a)^2}\right)\)

The central limit theorem tells us that the \(\bar{X}_n\) converges in distribution to a gaussian distribution as \(n\rightarrow \infty\). But what if we don't have very large \(n\)? Then, we can't use \(\Phi(x)\) to approximate the CDF of \(\bar{X}_n\). However, we can use Hoeffding's inequality, since it holds true for all \(n\).

• Chernoff bound – which can be used to bound the probability that the sum of bernoulli r.v.'s deviates from mean by factor of \((1+\delta)\)