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.

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|improve this question
    
At least twice or exactly twice? –  GMB Jan 1 '13 at 20:13
    
Thanks for that catch; at least twice. Edited into the question. –  Sir Sharkington Jan 1 '13 at 20:17
1  
This looks a lot like homework, and if so, please add the homework tag. But, even if not, what are your thoughts on the matter? Can you write an expression for the probability of exactly $k$ trials? Substitute $\lceil 2np\rceil$ for $k$ in the expression? Try again with $\lceil 2np\rceil+1$? Lather, rinse, repeat ... and remember that for mutually exclusive events $A$ and $B$, $P(A\cup B) = P(A)+P(B)$ –  Dilip Sarwate Jan 1 '13 at 20:22
    
Not homework in probability; I'm trying to get a randomized algorithm to behave nicely, and as such I want to bound the cases before I implement. Probability was many years ago unfortunately, and I kinda sucked at it back then. –  Sir Sharkington Jan 1 '13 at 20:25
    
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

3 Answers 3

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