1

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.

shg
  • 193
  • 1
    $$\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} $$

     – Dhruv Kohli Oct 21 '17 at 16:58
  • Will add as answer once verified. – Dhruv Kohli Oct 21 '17 at 17:00
  • 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? – shg Oct 21 '17 at 17:36
  • 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. – shg Oct 21 '17 at 17:45

2 Answers2

2

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

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

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.

shg
  • 193