Another version of Chernoff's bound and a Mathematica package for it


Chernoff's bound is a group of quite well-known concentration-inequalities. I though I know it but last week my collage Gabriel Berzunza Ojeda taught me another version of it. Let \(X\) be a binomial \((n,p)\) random variable. Then

$$ \mathbb P \left(X \ge (1+\delta) n p + \epsilon \right) \le (\delta +1)^{-\epsilon } \left(e^{\delta } (\delta +1)^{-\delta -1}\right)^{n p} $$

and

$$ \mathbb P \left(X \le (1-\delta) n p - \epsilon \right) \le (1-\delta )^{\epsilon } \left(e^{-\delta } (1-\delta )^{\delta -1}\right)^{n p} $$

A simpler version is

$$ \mathbb P \left(X \ge (1+\delta) n p + \epsilon \right) \le (\delta +1)^{-\epsilon } e^{\frac{1}{2} (\delta -1) \delta ^2 n p} $$

and

$$ \mathbb P \left(X \le (1-\delta) n p - \epsilon \right) \le (1-\delta )^{\epsilon } e^{\frac{1}{2} \delta ^3 n p-\frac{1}{2} \delta ^2 n p} $$

An even simpler version is

$$ \mathbb P \left(X \ge (1+\delta) n p + \epsilon \right) \le (\delta +1)^{-\epsilon } e^{-\frac{1}{3} a^2 n p} $$

and

$$ \mathbb P \left(X \le (1-\delta) n p - \epsilon \right) \le (1-\delta )^{\epsilon } e^{-\frac{1}{3} a^2 n p} $$

These inequalities can be handy if you are deal with a \(\epsilon\) which is \(o(n p)\) and \(\delta\) is a constant. The proof simply follows a small modification of this proof on Wikipedia.

Anyway, as a practice for programming in Mathematica, I created a Mathematica package to collect the forms of Chernoff's bound that now I know. You can find the package here. I put it on GitHub and you can find it here.