0
$\begingroup$

PREMISE

Suppose we have an urn with $N$ balls, with $m$ white balls and $N-m$ black balls. At every iteration, a ball is chosen at random. If a white ball is chosen, we add an extra white ball and remove a black ball, so that there are always $N$ balls. If a black ball is chosen, then we simply put it back in the urn. The process terminates when $m=N$, since it can no longer continue with the same rules.

QUESTIONS

  1. What is the expected value of the number of white balls after $k$ iterations? Alternatively, how many iterations does it take on average to reach $m=N$?
  2. Is this a well known probability distribution? Maybe a variant of the hypergeometric distribution?

WHAT I KNOW

In a particular simulation, if we have $s$ successes out of $k$ iterations, then the probability of this event is $$Pr(S=s) = \frac{(m+s)!/(m-1)!}{N^k} \times Pr(k-s \ \text{failures})$$

always. The term in the expression representing the probability of successes is always the same/independent of the order of successes and failures.

The probability of having a failure at any iteration is only dependent on the number of previous successes; order matters here.

$\endgroup$
1
  • 1
    $\begingroup$ I suspect this can been seen as a kind of coupon collector's problem run backwards in time, particularly if $m=1$. To actually solve it, you want to sum the expected numbers of draws until you draw the next white ball (which in each case has a geometric distribution with a parameter depending on $N$ and $m$). The sum, i.e. the answer to question 1, will be $N$ times a harmonic number. $\endgroup$
    – Henry
    Commented Dec 7, 2022 at 1:21

1 Answer 1

1
$\begingroup$

As @Henry noted, the number of draws at each $m$ is geometrically distributed:

$$P(X = x)=\frac{m}{N}\Big(1-\frac{m}{N}\Big)^{x-1}$$

which has a mean of $\frac{N}{m}$

The expected number of draws until $m=N$ is

$$\sum_{i=m_0}^{N-1}\frac{N}{i}=N\cdot(H_{N-1}-H_{m_0-1})$$

where $m_0$ is the initial number of white balls, $H_n$ is the $n^{th}$ harmonic number, and $H_0=0$.

This is the same as the expected number of draws for the coupon collector's problem for collecting the second through the $(N-m+1)^{th}$ coupon out of $N$ coupons.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.