The urn problem is equivalent to a continuous-time process where the balls behave independently.

Balls can be either Black, White, or Gone. For each ball, there's an independent Poission process of events at some fixed rate (say, $\lambda = 1$). An event turns a Black ball into a White ball, and turns a White ball into a Gone ball (and turns a Gone ball into a Gone ball). Given an initial configuration of $a$ White and $b$ Black balls, what's the probability $f(a, b)$ that the balls are all White (or Gone) before they are all Black (or Gone)?

For each ball $i$, its history is characterized by the interval of time $(X_i, Y_i)$ that it spends in the White state. It is Black before that, and Gone afterwards. The times at which all balls are Black or Gone are the times outside the union of these intervals $(X_i, Y_i)$. They're all Gone at times that are *after* the union of these intervals. So an equivalent formulation of the question is:

**Q:** What's the probability $f(a,b)$ that the union of the intervals $(X_i, Y_i)$ is contiguous?

This formulation mostly agrees with the original one, except that it gives a different value for the case $a=0$. Because we said "contiguous" rather than "contiguous and includes 0", we have $f(0, b) = f(1, b-1)$ rather than $f(0, b) = 0$. So in this formulation we're interested in showing that $f(0, b) \to 1$ as $b \to \infty$.

We might hope that there are values $\varepsilon, M$ depending on $b$ for which, with high probability:

- (A) Each $(X_i, Y_i)$ intersects $(\varepsilon, M)$.
- (B) The union of $(X_i, Y_i)$ covers $(\varepsilon, M)$.

Roughly, for (A) we need $\varepsilon = b^{1/2} o(1)$, and $M > \log b + \omega(1)$. Guaranteeing (B) is a bit tricky. One might hope some interval just covers $(\varepsilon, M)$ with high probability, but AFAIK that's too ambitious. What we can do instead is find a third parameter $C$ for which, with high probability

- (A) Each $(X_i, Y_i)$ intersects $(\varepsilon, M)$.
- (B1) Some $(X_i, Y_i)$ covers $(\varepsilon, C)$, and
- (B2) Some $(X_i, Y_i)$ covers $(C, M)$.

A bit of experimentation gives values that work:

\begin{align*}
\varepsilon &= b^{-(1/2+\alpha)}
\\
C &= \log(b^{1/2 - \alpha - \gamma}) = (1/2 - \alpha - \gamma) \log b
\\
M &= \log(b \sqrt{\log b}) = \log b + 1/2 \log \log b,
\end{align*}

where $\alpha > 0$, $\gamma > 0$, and $\alpha + \gamma < 1/2.$

At this point it's a computation.

**(A) holds with high probability:**

Note that $X_i$ and $Z_i = Y_i - X_i$ are independent and exponentially distributed, so the joint distribution of $(X_i, Y_i)$ has density
$$\phi(x,y) = \exp(-x)\exp(-(y-x)) \mathbf1_{0 < x < y} = \exp(-y) \mathbf1_{0 < x < y}.$$

The probability that some $(X_i, Y_i)$ lies entirely to the left of $(\varepsilon, M)$ is at most

$$
b \,\mathbf P(Y_i <\varepsilon) = b \int_0^\varepsilon \int_x^\varepsilon \exp(-y)\ dy\ dx = b O(\epsilon^2) = O(b^{-2\alpha}) = o(1).
$$

The probability that some $(X_i, Y_i)$ lies entirely to the right of $(\varepsilon, M)$ is at most

$$
b \,\mathbf P(X_i < M) = b \int_M^\infty \int_x^\infty \exp(-y) \ dy\ dx = b \exp(-M) = 1/\sqrt{\log b} = o(1).
$$

So each $(X_i, Y_i)$ intersects $(\varepsilon, M)$ with probability $1 - o(1).$

**(B2) holds with high probability:**

For a fixed $i$, the probability that $(X_i,Y_i)$ covers $(C, M)$ is

$$
p = \mathbf P(X_i < C, Y_i > M) = \int_0^C\int_M^\infty \exp(-y) \ dy\ dx = C\exp(-M)
$$

Plugging in our values, this is

\begin{align*}
p =
C\exp(-M)
&= (1/2 - \alpha - \gamma) (\log b) b^{-1} (\log b)^{-1/2}
\\
&= b^{-1}(1/2 - \alpha - \gamma) \sqrt{\log b}
\\
&= b^{-1} \omega(1)
\end{align*}

(Here $\omega(1)$ denotes a term that goes to infinity as $b \to \infty$.) So the probability that **none** of the $(X_i, Y_i)$ cover $(C, M)$ is

$$
(1-p)^b = (1-\omega(1)/b)^b < \exp(-\omega(1)) = o(1),
$$

so one of those intervals covers $(C, M)$ with probability $1 - o(1)$.

**(B1) holds with high probability:**

As above, for a fixed $i$, the probability that $(X_i,Y_i)$ covers $(\varepsilon, C)$ is

\begin{align*}
\varepsilon \exp(-C)
&=
b^{-(1/2+\alpha)} b^{-1/2+\alpha+\gamma}
= b^{-1} b^{\gamma} = b^{-1} \omega(1)
\end{align*}

So one of those intervals covers $(\varepsilon, C)$ with probability $1-o(1)$.

In other words, with high probability:

- No ball turns White and disappears before $\varepsilon$
- Some ball turns White by time $\varepsilon$ and survives until time $C$.
- Some ball turns White by time $C$ and and survives until time $M$.
- No ball turns White after time $M$ (i.e. no balls are Black at time $M$.)

It follows that with high probability, there is no point after the first ball turns White that all the surviving balls are Black.

Amer. Math. Monthly121 (2014), 299-317. $\endgroup$8more comments