Binomial distribution: upper bound and lower bound

This question is discussed in Feller's Introduction to Probability Theory and Its Applications and i am relatively new in probability theory, so this theme is incomprehensible for me:

The probability at least $$r$$ successes is: $$P(S_n \ge r)=\sum_{v=0}^\infty b(r+v;n,p).$$

The formula for upper bound is: $$P(S_n \ge r)≤\frac{rq}{(r-np)^2} : \quad r≥np$$

the formula for lower bound is: $$P(S_n \le r)≤ \frac{(n-r)p}{(np - r)^2} : \quad r≤np$$

But i don't understand how the author derived such formulas. So, if it's possible, can you please explain the meaning and derivation of formulas in a simple(not complicated) way? Thank you

• Hi! Where are the results above listed in the book? I couldn't find it... However, I was able to find on Page 140 where he provides a bound on the cdf using the pdf. May 29 '17 at 20:21

To fill in some details, we have (from Feller, pg. 151):

\begin{eqnarray*} && S_n \sim B(n,p) \\ && q = 1-p \\ && b(k;n,p) := P(S_n=k). \end{eqnarray*}

I'll try to flesh out Feller's argument. Firstly, for $r\gt np,\;$ we look at ratios of probabilities:

\begin{eqnarray*} \dfrac{P(S_n=r+1)}{P(S_n=r)} &=& \dfrac{\binom{n}{r+1}p^{r+1}q^{n-r-1}}{\binom{n}{r}p^{r}q^{n-r}} \\ && \\ &=& \dfrac{\dfrac{n!}{(r+1)!(n-r-1)!}p^{r+1}q^{n-r-1}}{\dfrac{n!}{r!(n-r)!}p^{r}q^{n-r}} \\ && \\ &=& \dfrac{(n-r)p}{(r+1)q} \\ && \\ &\leq& \dfrac{(n-r)p}{rq} \\ && \\ &=& 1 - \dfrac{rp-np+rq}{rq} \\ && \\ &=& 1 - \dfrac{r-np}{rq}\qquad\qquad\qquad\qquad\qquad\text{(1)} \\ &\lt& 1\qquad\text{since } r\gt np. \end{eqnarray*}

So if $k\gt r$, then

\begin{eqnarray*} P(S_n=k) &=& \dfrac{P(S_n=k)}{P(S_n=k-1)} \dfrac{P(S_n=k-1)}{P(S_n=k-2)} \cdots \dfrac{P(S_n=r+1)}{P(S_n=r)}P(S_n=r) \\ && \\ &\leq& P(S_n=r)\left(1 - \dfrac{r-np}{rq} \right)^{k-r} \qquad\qquad\qquad\text{using (1)}. && \\ \therefore\quad P(S_n\geq r) &=& \sum_{k=r}^{\infty} P(S_n=k) \\ && \\ &\leq& \sum_{k=r}^{\infty} P(S_n=r) \left(1 - \dfrac{r-np}{rq} \right)^{k-r} \\ && \\ &=& P(S_n=r) \sum_{k=0}^{\infty} \left(1 - \dfrac{r-np}{rq} \right)^{k} \\ && \\ &=& P(S_n=r) \dfrac{1}{1 - \left(1 - \dfrac{r-np}{rq} \right)} \qquad\text{using $\sum_{m=0}^\infty x^m=\dfrac{1}{1-x}$ if $0\lt m\lt 1$} \\ && \\ &=& P(S_n=r)\dfrac{rq}{r-np}.\qquad\qquad\qquad\qquad\qquad\text{(2)} \end{eqnarray*}

We now find an upper bound for $P(S_n=r)$. From $(1)$ we know that if $np\leq k\leq r$, then $P(S_n=k) \geq P(S_n=r)$.

So there are at least $r-np$ such numbers. (Note: $np$ may not be an integer.) Therefore,

$$1\geq \sum_{np\leq k\leq r} P(S_n=k) \geq \sum_{np\leq k\leq r} P(S_n=r) \geq (r-np)P(S_n=r).$$

Therefore, $P(S_n=r) \leq \dfrac{1}{r-np}$. Substituting this into $(2)$, we arrive at

$$P(S_n \geq r) \leq \dfrac{rq}{(r-np)^2}.$$

The second result derives directly from this by mapping:

\begin{eqnarray*} p &\mapsto& q \\ q &\mapsto& p \\ r &\mapsto& n-r. \end{eqnarray*}