# “Practical forms” of Chernoff bound for inequality in expectation

From Wikipedia:

The above formula is often unwieldy in practice, so the following looser but more convenient bounds are often used:

(i) $Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}, 0<\delta<1$

(ii) $Pr(X\leq (1-\delta)\mu)\leq e^{-\frac{\delta^2\mu}{2}}, 0<\delta<1$

The assumption they use is $E[X]=\mu$.

Would (i) still hold if we only assume $E[X]\leq \mu$? Would (ii) still hold if we only assume $E[X]\geq\mu$?

If not, what "practical forms" do we have in these cases?

It is more practical just because it has

the advantage of being easier to state and compute with in many situations (quoted from ).

I am not sure whether (i) still holds for $\mu' = E[X] \le \mu$. At least, we cannot obtain that directly from the following computation:

$$Pr[X \ge (1 + \delta) \mu] \le Pr[X \ge (1 + \delta) \mu'] \le e^{-\frac{\delta^2 \mu'}{3}} \ge e^{-\frac{\delta^2 \mu}{3}}$$

 Mitzenmacher, Michael and Upfal, Eli (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 0-521-83540-2.

• You can check what happens in some case where the large deviation behavior is known exactly, say the binomial distribution. – Yuval Filmus Apr 26 '15 at 6:53