Hoeffding's inequality

SSU

Upper bound for probability of sample mean deviation from true mean. $P(|\mu -{\hat{\mu }}_n|\ge \epsilon )\le 2e^{-\frac{2n{\epsilon }^2}{(b-a{)}^2}}$

Proof

TODO Uses Markov’s Inequality

Implementation

hoeffding_bound(n, thresh, upper_bound, lower_bound):
	return 2 * math.exp(- 2*n*thresh**2 / (upper_bound-lower_bound)**2)