[Math] Which versions of Chernoff bound are applied to Binomial distribution in these examples

probability

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!

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.

Related Question