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

This is from Feller's Introduction to Probability Theory and Its Applications. In the context of Bernoulli trials, we define:

$$b(k;n,p) = \binom{n}{k}p^kq^{n-k},$$ $$P\{S_n \ge r\} = \sum_{v=0}^{\infty}b(r+v;n,p).$$

The latter being the probability of having at least $r$ successes. Now, supposing $r \gt np$ and knowing that

$$\frac{b(k; n,p)}{b(k-1;n,p)}=\frac{(n-k+1)p}{kq}=1+\frac{(n+1)p-k}{kq},$$

show that

$$P\{S_n \ge r\} \le b(r;n,p)\frac{rq}{r-np}.$$

According to Feller, it follows from the obvious fact that the terms of the series decrease faster than the terms of a geometric series with ratio $1-\frac{r-np}{rq}$. However, it's not obvious for me and I don't see how the upper bound follows.

share|cite|improve this question
up vote 5 down vote accepted

First notice that

For $k > r$ we have that

$\frac{(n-k+1)p}{kq} <\frac{(n-k+1)p}{rq}$ (as $n \ge k-1$)

Now $\frac{(n-k+1)p}{rq} \leq \frac{(n-(r+1)+1)p}{rq} = \frac{(n-r)p}{rq}$ as the numerator is the largest when $k = r+1$

Now $1 - \frac{(n-r)p}{rq} = \frac{rq - np + rp}{rq} = \frac{r -np}{rq}$ (as $p+q=1$).

share|cite|improve this answer
Thank you. I guess the upper bound follows from $$P\{S_n \ge r\} \le \sum_{i=0}^{n-r} b(r;n,p)m^i$$ with $m = \frac{(n-r)p}{rq}$. Thus, $$P\{S_n \ge r\} \le b(r;n,p)\frac{1-m^{n-r+1}}{1-m} \le b(r;n,p)\frac{1}{1-m} = b(r;n,p)\frac{rq}{r-np}.$$ – user519 Aug 23 '10 at 11:10
@AR. Yes, you got it right. – Aryabhata Aug 23 '10 at 16:10

Your Answer


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