Result of Bernoulli trials being twice the expectancy?

Question

Given a probability $0 < p < 0.5$ for success per trial with $n$ Bernoulli trials, what are the odds for having succeeded in at least $2np$ experiments?

Answer 1

The large deviations principle alluded to in the comments is as follows. Consider the number $S_n=X_1+\cdots+X_n$ of successes during the $n$ first trials. Then $(X_n)_{n\geqslant1}$ is i.i.d. with Bernoulli distribution with parameter $p$, in particular, for every $t$, $\mathbb E(\mathrm e^{tX_k})=p\mathrm e^t+1-p$.

Let $x\gt p$ and $A_n(x)=[S_n\geqslant nx]$. Then, almost surely, $\mathrm e^{tnx}\mathbf 1_{A_n(x)}\leqslant\mathrm e^{tS_n}$ for every $t\geqslant0$, hence, integrating both sides of this inequality, one sees that $$ \mathbb P(A_n(x))\leqslant\mathrm e^{-tnx}\mathbb E(\mathrm e^{tS_n})=\mathrm e^{-tnx}\mathbb E(\mathrm e^{tX_1})^n=\mathrm e^{-n\Lambda(t,x)},$$ with $$ \Lambda(t,x)=tx-\log\mathbb E(\mathrm e^{tX_1})=tx-\log(p\mathrm e^t+1-p). $$ The most interesting upper bound this technique can yield is the one such that $\Lambda(t,x)$ is maximal, that is, when $t=t(x)$ with $\mathrm e^{t(x)}=(1-p)x/(p(1-x))$. When $p\lt x\lt1$, $t(x)$ is finite and positive and $\Lambda(t(x),x)=\Lambda(x)$ with $$ \Lambda(x)=x\log\left(\frac{x}p\right)+(1-x)\log\left(\frac{1-x}{1-p}\right). $$ It happens that, for each $p\lt x\lt1$, $\Lambda(x)$ indicates the exact order of exponential convergence of $\mathbb P(A_n(x))$ when $n\to\infty$, that is, $$ \lim\limits_{n\to\infty}\frac1n\log\mathbb P(S_n\geqslant nx)=-\Lambda(x). $$ In your case, $0\lt p\lt\frac12$ and $x=2p$ hence, for every $n$, $$ \mathbb P(S_n\geqslant 2np)\leqslant\exp\left(-n\left(2p\log2+(1-2p)\log\left(\frac{1-2p}{1-p}\right)\right)\right), $$ and, when $n\to\infty$, $$ \mathbb P(S_n\geqslant 2np)=\exp\left(-n\left(2p\log2+(1-2p)\log\left(\frac{1-2p}{1-p}\right)\right)+o(n)\right). $$ The argument briefly sketched above is due to Harald Cramér and can be adapted to incredibly more general situations.

Answer 2

Appendix A of the text Error-Correcting Codes by W. W. Peterson and E. J. Weldon, Jr. (2nd edition, MIT Press, 1972) credits the following to notes transcribed from the lectures of Claude Shannon at a MIT seminar.

If $\lambda > p$, then $$\binom{n}{\lambda n}p^{\lambda n}(1-p)^{(1-\lambda)n} < \sum_{i=\lambda n}^n \binom{n}{i}p^i(1-p)^{n-i} < \frac{\lambda(1-p)}{\lambda - p}\binom{n}{\lambda n}p^{\lambda n}(1-p)^{(1-\lambda) n},$$ and $$\sum_{i=\lambda n}^n \binom{n}{i}p^i(1-p)^{n-i} \leq \left(\frac{p}{\lambda}\right)^{\lambda n}\left(\frac{1-p}{1-\lambda}\right)^{(1-\lambda)n}$$

Here, $\lambda = 2p > p$, and so we have

$$\begin{align*} \sum_{i=2pn}^n \binom{n}{i}p^i(1-p)^{n-i} &\leq 2^{-2np}\left(\frac{1-p}{1-2p}\right)^{(1-2p)n}\\ &= \exp\left(-n\left(2p\ln 2+(1-2p)\ln\left(\frac{1-2p}{1-p}\right)\right)\right) \end{align*}$$ which is essentially the result already given by @did (except without the $o(n)$ term since the above is an upper bound). The proof of these inequalities uses the upper bound $$\binom{n}{\lambda n} < \frac{1}{\sqrt{2\pi n \lambda(1-\lambda)}} \lambda^{-\lambda n}(1-\lambda)^{-(1-\lambda)n}$$ which is itself proved using Stirling's approximation for $n!$

Answer 3

You have a variable following the binomial distribution $B(n, p)$, with $E[X] = np$ and $Var[X] = np(1-p)$. Generally speaking, the probability that $X \geq 2np$ is small (actually very small).

By Markov's inequality, let $t = 2np$, $$P[X\geq t] \leq \frac{E[X]}{t} = \frac{np}{2np} = 0.5.$$ But this bound is not good.

By Chebyshev's inequality, let $t = np$, $$ P[|X-E[X]|\geq t] \leq \frac{Var[X]}{t^2} = \frac{np(1-p)}{(np)^2} = \frac{1-p}{np}.$$

By Hoeffding's inequality, let $\epsilon = p$, $$P[X \geq (p+\epsilon)n] \leq \exp(-2\epsilon^2n) = \exp(-2p^2 n).$$

Hoeffding's inequality gives the best bound: the probability goes down exponentially as the number of trials grows. I believe the Chernoff bound gives similar result.

http://en.wikipedia.org/wiki/Concentration_inequality http://en.wikipedia.org/wiki/Hoeffding%27s_inequality