# Variant of the hypergeometric distribution: throwing balls back into the urn

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.

## 1 Answer

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.