1
$\begingroup$

Hypergeometric distribution describes the probability of k successes in n draws from population of N with K successes. But what if I want expected number of draws until k successes are drawn from the same population?

$\endgroup$
29
  • $\begingroup$ Wider question: in a population of N is 1 ill person. At each moment of time, two people meet. If one of them is ill and the other healthy, the healthy gets ill. What is the expected time count until at least n people are ill? $\endgroup$ Jan 7 '18 at 11:32
  • $\begingroup$ So, in you case you need to apply the following trick: you keep drawing until $k$ successes, you last draw (the $k$-th one) is a success, the remaining $k-1$ are scattered across $n-1$ draws. Or $P(n \text{ draws until }k\text{ successes})=P(\text{last draw is success})\cdot P(n-1 \text{ draws have }k-1\text{ successes})$ $\endgroup$
    – rtybase
    Jan 7 '18 at 11:43
  • 1
    $\begingroup$ okay but the expected value of the second factor is still dependent on n, specifically it is (n-1)K/N $\endgroup$ Jan 7 '18 at 11:59
  • 1
    $\begingroup$ As per my comment $$P(n \text{ draws until }k\text{ successes})=P(\text{last draw is success})\cdot P(n-1 \text{ draws have }k-1\text{ successes})$$ $P(n-1 \text{ draws have }k-1\text{ successes})$ is the standard hyper geometric probability $$P(n-1 \text{ draws have }k-1\text{ successes})=\frac{\binom{K}{k-1}\binom{N-K}{n-k+1}}{\binom{N}{n-1}}$$ and (everything is without replacement) $$P(\text{last draw is success})=\frac{1}{K-k+1}$$ And $$E[X]=\sum\limits_{n\geq k}nP(n \text{ draws until }k\text{ successes})$$ $\endgroup$
    – rtybase
    Jan 7 '18 at 12:03
  • $\begingroup$ ah! you can use the infinite sum to get the expected value, thanks! if you submit this as an aswer, I will gladly accept it. $\endgroup$ Jan 7 '18 at 12:07
0
$\begingroup$

As per my comments $$P(n \text{ draws until }k\text{ successes})=P(\text{last draw is success})\cdot P(n-1 \text{ draws have }k-1\text{ successes})$$

$P(n-1 \text{ draws have }k-1\text{ successes})$ is the standard hyper geometric probability $$P(n-1 \text{ draws have }k-1\text{ successes})=\frac{\binom{K}{k-1}\binom{N-K}{n-1-k+1}}{\binom{N}{n-1}}=\frac{\binom{K}{k-1}\binom{N-K}{n-k}}{\binom{N}{n-1}}$$ and (everything is without replacement) $$P(\text{last draw is success})=\frac{K-k+1}{N-n+1}$$ $E[X]$ is a function of $k$, also considering $\binom{n}{k}=\binom{n}{n-k}$ $$\color{red}{E[X]=}\sum\limits_{n\geq k}nP(n \text{ draws until }k\text{ successes})=\sum\limits_{n\geq k}n\frac{\binom{K}{k-1}\binom{N-K}{n-k}}{\binom{N}{n-1}}\frac{K-k+1}{N-n+1}=\\ \sum\limits_{n\geq k}n\frac{\binom{K}{K-k+1}\binom{N-K}{n-k}}{\binom{N}{N-n+1}}\frac{K-k+1}{N-n+1}=\\ \binom{K}{K-k+1}(K-k+1)\sum\limits_{n\geq k}n\frac{\binom{N-K}{n-k}}{\binom{N}{N-n+1}(N-n+1)}=\\ \frac{K!}{(K-k+1)!(k-1)!}(K-k+1)\sum\limits_{n\geq k}n\frac{\binom{N-K}{n-k}}{\frac{N!}{(N-n+1)!(n-1)!}(N-n+1)}=\\ \frac{K!}{(K-k)!(k-1)!}\sum\limits_{n\geq k}n\frac{\binom{N-K}{n-k}}{\frac{N!}{(N-n)!(n-1)!}}=\\ k\frac{K!}{(K-k)!k!}\sum\limits_{n\geq k}\frac{\binom{N-K}{n-k}}{\frac{N!}{(N-n)!n!}}= \color{red}{k\binom{K}{k}\sum\limits_{n\geq k}\frac{\binom{N-K}{n-k}}{\binom{N}{n}}}$$

I have tried the following Python $3$ code

from scipy.special import comb
from decimal import *

N = 10000
K = 1000

k = 1000

res = Decimal(k * comb(K, k, exact=True))
sum = Decimal('0.0')
one = Decimal('1.0')

def combinations(b, a):
    if (b >= a):
        return comb(b, a, exact=True)
    else:
        return 0

for n in range(k, N - K + k + 1):
    sum = sum + (Decimal(combinations(N-K, n-k)) * one) / Decimal(combinations(N, n))

res = res * sum
print(res)

producing

k=1     E[X]=9.991008991008991008991008979
k=10    E[X]=99.91008991008991008991008991
k=100   E[X]=999.1008991008991008991008979
k=1000  E[X]=9991.008991008991008991008992

all within 8 minutes (altogether, so $\approx 2$ minutes per run) on my MacBook Pro. And

N = 10000 K=5000 k=3000 E[X]=5999.400119976004799040191959

took less than $2$ minutes. Larger values of $N$ take longer to compute (E.g. $N=100000$ I had to stop the program after 1 hour).

Although, it looks like empirically $$E[X]\approx k\cdot \frac{N}{K}$$

$\endgroup$
2
  • $\begingroup$ yes, I had a very similar code, although my CPU isn't as powerful. Considering I would have to evaluate E[X] for all K in 1...1000, it would take hours, but the principle works. $\endgroup$ Jan 9 '18 at 20:02
  • $\begingroup$ I think, it is worth focusing on proving the empirical result. $\endgroup$
    – rtybase
    Jan 9 '18 at 20:11

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.