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?


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 $$

  • $\begingroup$ The bound is undefined in that case. $\endgroup$ – whuber Jul 12 '17 at 20:36
  • $\begingroup$ @whuber The rhs is $e^{-\infty} = 0$ for $t \neq 0$. But the chernoff bound would still be tight. $\endgroup$ – Miheer Jul 12 '17 at 21:09
  • 1
    $\begingroup$ That intuitively appealing idea unfortunately is mathematical nonsense. To make it rigorous I suppose you might try to take a limit as $b\to a$ from above, but that would require some careful explaining. It would be of much greater interest to consider non-trivial cases. $\endgroup$ – whuber Jul 12 '17 at 21:13

I'm not sure if you can say something for every $n$ (and all distributions) for Hoeffding precisely. For Chernoff you can say that the moment bound is tighter than the Chernoff bound. In the linked paper the author also notes (but defers the proof to the citation, that for large $t$, if $C(t)$ is the Chernoff bound then,

$$\Pr(X>t) \leq C(t)exp(-\mathcal{o}(t)) $$

where $\mathcal{o}(t)$ is the usual 'little oh' notation (value going to 0 as $t \to \infty$) implying that $\Pr(X>t) \leq C(t)$ for large $t$. The proof method in the linked Philips and Nelson paper would apply for the Hoeffding case as well.

The reference cited in the paper for this proof is is the Large Deviations books by Bucklew,

here is a link to the google books page for the book. If you want the proof hopefully you can find a copy via your local university library.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.