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

  • $\begingroup$ 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. $\endgroup$
    – Oliver
    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*}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.