Solved – Is Hoeffding’s bound tight in any way

probabilityprobability-inequalitiesrandom variable

The inequality:

$$\Pr(\overline X – \mathrm{E}[\overline X] \geq t) \leq \exp \left( – \frac{2n^2t^2}{\sum_{i=1}^n (b_i – a_i)^2} \right)$$

Is this bound (or any other form of hoeffding) tight in any sense? e.g. does there exist a distribution for which the bound is no more than a constant multiple of the true probability for every n?

Best Answer

A trivial example would be if $X_i$ is deterministic (say always equal to 0). The right hand side would then be the dirac mass at 0 (as seen in the proof of Hoeffding's inequality).

There can't be any other example as that would contradict the hypothesis that $\bar{X}$ is bounded, since

$$ 0 < C \exp\left( -\frac{2n^2 t^2}{\sum_{i=1}^n (b_i-a_i)}\right) \leq P( \bar{X} \geq E[\bar{X}] + t) \qquad \forall t \geq 0 $$

Related Question