# Which versions of Chernoff bound are applied to Binomial distribution in these examples?

There are several versions of Chernoff bounds. I was wodering which versions are applied to computing the probabilities of a Binomial distribution in the following two examples, but couldn't. I have tried to find them out but not succeeded.

1. From Wikipedia

The cumulative distribution function can be expressed as: $$F(x;n,p) = \Pr(X \le x) = \sum_{i=0}^{\lfloor x \rfloor} {n\choose i}p^i(1-p)^{n-i}$$ For $k ≤ np$, Chernoff's inequality can be used to derive the bound $$F(k;n,p) \leq \exp\left(-\frac{1}{2\,p} \frac{(np-k)^2}{n}\right). \!$$

2. From Wikipedia

Let $X_1, \dots, X_n$ be independent Bernoulli random variables, each having probability $p > 1/2$. Then the probability of simultaneous occurrence of more than n/2 of the events $\{X_k = 1\}$ has an exact value $S$, where $$S=\sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i} .$$ The Chernoff bound shows that $S$ has the following lower bound: $$S \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} .$$

The second one, if I understand correctly, is equivalent to $$F(n/2;n,p) \leq \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2}.$$

I don't think part 2 can be derived from part 1. Granted that part 1 is correct based on some unknown result, then since $n/2 < np$, $$F(n/2;n,p) \leq \mathrm{e}^{- \left( {np - \frac{n}{2}} \right)^2 / (2np)} = \mathrm{e}^{- n \left( {p - \frac{1}{2}} \right)^2 / (2p)}$$ The RHS is $\leq \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2}$ if and only if $p \leq 1/4$ which is contrary to $p >1/2$.

Thanks!

-

Your first question is just applying the Chernoff bound and making some smart transformations. One way to do it is the following:

$$\mathrm{Pr}[X \leq k] = \mathrm{Pr}\left[X \leq \left(1-\left(1-\frac{k}{\mu}\right)\right)\mu\right]$$

Observe that $\delta := 1-(k/\mu)$ in the Chernoff bound. Since $k < np = \mu$, we have that $k/\mu$ is smaller than $1$, which is needed to apply the bound. Now,

\begin{align*} \mathrm{Pr}[X \leq k] &\leq \exp\left( -\delta^2 \mu / 2 \right) \\ &= \exp\left( -\frac{\mu}{2} \left(1- 2\frac{k}{\mu}+\frac{k^2}{\mu^2}\right)\right) \\ &= \exp\left( -\frac{1}{2\mu} \left(\mu^2- 2k\mu+{k^2}\right)\right) \\ &= \exp\left( -\frac{1}{2np} (np-k)^2 \right), \\ \end{align*}

where in the last step we used the 2nd binomial formula.

For your second question, you are right, and it appears to me, that by now the wikipedia page has been fixed. You can obtain a better bound though (the one in your question) by using Azuma-Hoeffdings inequality.

-