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.
-
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). \! $$ -
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!
Best Answer
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.