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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
    
The exact probability for a given n has no simple closed form (and is not very interesting). Its asymptotics when $n$ grows large are well known and can be described neatly using a large deviations principle. Which one interests you? – Did Jan 1 '13 at 20:39
    
Asymptotics are exactly what I could use; I will look up the large deviations principle. Thank you very much. – Sir Sharkington Jan 1 '13 at 20:46
    
$2np$ is above the expected value $np$ by $\frac{np}{\sqrt{npq}}=\sqrt{\frac{np}{q}}$ standard deviations. – Hagen von Eitzen Jan 1 '13 at 20:57
    
@user54893 See answer below. (Unrelated: please use @ to signal your comments.) – Did Jan 1 '13 at 23:45

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.

share|cite|improve this answer

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

share|cite|improve this answer

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!$

share|cite|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.