1
$\begingroup$

The binomial PMF (probability of exactly k successes in n trials with probability p)

$$f\left( {k,n,p} \right) = {{n!} \over {k!\left( {n - k} \right)!}}{p^k}{\left( {1 - p} \right)^{n - k}}$$

And the recurrence relation for an additional success is

$$f\left( {k + 1,n,p} \right) = {{n - k} \over {k + 1}}\;{p \over {1 - p}}f\left( {k,n,p} \right)$$

The CDF (probability of at most k successes) is

$$F\left( {k,n,p} \right) = \sum\limits_{i = 0}^k {{{n!} \over {i!\left( {n - i} \right)!}}{p^i}{{\left( {1 - p} \right)}^{n - i}}} $$

My question is, is there a similarly simple recurrence relation for the CDF for an additional trial?

$$F\left( {k,n + 1,p} \right) = ??$$

Thank you.

$\endgroup$
  • 1
    $\begingroup$ $$\binom{n+1}{i} = \binom{n}{i} + \binom{n}{i-1}$$ $$ \begin{align} F(k,n+1,p) &= \sum_{i=0}^{k}\binom{n+1}{i}p^{i}(1-p)^{n+1-i}\\ &= \sum_{i=0}^{k}\binom{n}{i}p^{i}(1-p)^{n+1-i} + \sum_{i=1}^{k}\binom{n}{i-1}p^{i}(1-p)^{n+1-i}\\ &= (1-p)F(k,n,p) + p\sum_{j=0}^{k-1}\binom{n}{j}p^j(1-p)^{n-j}\\ &= (1-p)F(k,n,p) + pF(k-1,n,p) \end{align} $$ $\endgroup$ – Dhruv Kohli - expiTTp1z0 Oct 21 '17 at 16:58
  • $\begingroup$ Will add as answer once verified. $\endgroup$ – Dhruv Kohli - expiTTp1z0 Oct 21 '17 at 17:00
  • $\begingroup$ I've verified that with several numerical examples, thank you. I'm trying to write a simple loop that tests for the CDF to descend below a threshold value starting from F(k,n,p)=1 for k=n. Is there a way to express F(k-1,n,p) in terms of previously calculated values? $\endgroup$ – shg Oct 21 '17 at 17:36
  • $\begingroup$ Maybe I can say that more clearly: Start with n=k, F(k,n,p)=1. Increase n until F descends below a specified threshold. $\endgroup$ – shg Oct 21 '17 at 17:45
2
$\begingroup$

$$\binom{n+1}{i} = \binom{n}{i} + \binom{n}{i-1}$$

$$ \begin{align} F(k,n+1,p) &= \sum_{i=0}^{k}\binom{n+1}{i}p^{i}(1-p)^{n+1-i}\\ &= \sum_{i=0}^{k}\binom{n}{i}p^{i}(1-p)^{n+1-i} + \sum_{i=1}^{k}\binom{n}{i-1}p^{i}(1-p)^{n+1-i}\\ &= (1-p)F(k,n,p) + p\sum_{j=0}^{k-1}\binom{n}{j}p^j(1-p)^{n-j}\\ &= (1-p)F(k,n,p) + pF(k-1,n,p) \end{align} $$

I think you also need this, $$F(k-1,n,p) + \binom{n}{k}p^k(1-p)^{n-k} = F(k,n,p)$$

$\endgroup$
  • $\begingroup$ I was trying to avoid having to calculate f(k,n,p), but that's certainly faster than what I had, thank you. $\endgroup$ – shg Oct 21 '17 at 18:02
0
$\begingroup$

Just to wrap that in a bow,

$$\eqalign{ F\left( {k,n + 1,p} \right) = & \left( {1 - p} \right)F\left( {k,n,p} \right) + pF\left( {k - 1,n,p} \right) \cr = & \left( {1 - p} \right)F\left( {k,n,p} \right) + p\left( {F\left( {k,n,p} \right) - f\left( {k,n,p} \right)} \right) \cr = & F\left( {k,n,p} \right) - pf\left( {k,n,p} \right) \cr} $$

Thank you again.

$\endgroup$

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.