Following the notation from WP:hypergeometric distribution.

We have an urn with $K$ red and $N-K$ white balls. When we find a red ball, we keep it, removing it from the population. But when we find a white ball, we throw it back. Given a certain number of trials ($n$), how many red balls / successes ($k$) are we likely to find?

What's this distribution called? We can find at most $\min(K, n)$ red balls but are allowed to continue sampling forever.

I can find the probability mass function (in exponential time) and simulate draws from it quite easily but couldn't come up with a closed form.


What you probably need is called Coupon Collector's Problem. You count the number of 'failures' (sampled white balls) until the first success (sample red ball) with corresponding probabilities $p_{1F}$ and $1-p_{1F}$. After the first success the probability changes (because the proportion of red to white balls changes and becomes $p_{2F}$ and $1-p_{2F}$ and so on. Each of these rvs is Geometric with parameter $p_{1-kF}, \ k$ is the current number of red balls, so these Geometric rvs are independent, but not identically distributed. Mean time till you have sampled all red balls (in your case) is $$ \mathbf{E}T=\frac{n}{k}+\frac{n}{k-1}+\ldots +\frac{n}{1}=nH_n=O(n \log n) $$ This is due to the mean of each Geometric rv equal to $\frac{1}{1-p_{kF}}$, $H_n$ is n-th harmonic number. This is essentially runtime of the Randomized local search (RLS) algorithm on problem like OneMax.


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.