# Binomial distribution and upper bound

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.

-

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

-
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