Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.