Hoeffding inequality

SSU

Let there be a series of $n$ i.i.d. samples generated from a random variable with distribution $q(z)$. Let the sampled values all be in an interval $[a,b]$. For every $\epsilon >0$ holds an inequality $\mathbb{P}(|\mu -{\hat{\mu }}_n|\ge \epsilon )\le 2\exp (-\frac{2n{\epsilon }^2}{(b-a{)}^2}),$ where $\mu$ is the Expected value of $z$ and ${\hat{\mu }}_n$ sample mean.

Properties

• holds for any bounded i.i.d. samples
• goes to 0 as n approaches infinity
• easy to compute
• not tight