Balls and Urn Paradox

So, I came across the following paradox:

At $1$ minute before noon, put in balls $1 \sim 10$ and take out ball number $1$. At $1/2$ minute before noon, put in balls $11\sim20$ and take out ball number $2$ and so on. How many balls are there at noon?

None.

At $1$ minute before noon, put in balls $1 \sim 10$ and randomly take out a ball. At $1/2$ minute before noon, put in balls $11\sim20$ and randomly take out another ball and so on. How many balls are there at noon?

None.

Okay, so I understand the first paradox because one can describe the exact moment each ball was taken out. But, you can't apply a similar argument to the second paradox because we randomly take out a ball. I feel as if it's like infinitely summing $\frac{1}{n}$ and eventually there would be too many balls.

Can someone explain to me mathematically why this is the case?

• For the second case, it depends greatly what you mean by "randomly". If it just means that you pick one ball at random from the balls that are present, then there is no way to prove that the urn will be empty, and actually any subset of the balls might remain at the end. – Carl Mummert Jun 8 '16 at 0:58
• For a previous discussion of the first version of the "paradox", see this earlier Question. – hardmath Jun 8 '16 at 1:27

Let $n \in \mathbb{N}$

Let the ball labelled $n$ be placed in the urn on step $i_0$.

The probability of removing the ball labelled $n$ at step $i$ is $\dfrac {1} {9i+1}$.

The probability of it never being removed is therefore

$$\prod_{i=i_0}^{\infty} 1 - \dfrac {1} {9i+1}$$

Which diverges to $0$ since the sum

$$\sum_{i=i_0}^{\infty} -\dfrac {1} {9i+1}$$

diverges to $-\infty$.

So all balls will be removed at some point with probability $1$.

Okay, at each tick you are adding nine distinct balls by adding 10 enumerated balls and removing one ~ either in enumeration order or randomly.   The ticks occur at times in the infinite sequence $\{-1, -\tfrac 12, -\tfrac 14, ..., -2^{1-k}, ...\}$ in units of "minutes before noon".   (Assuming that you can insert and extract these balls actual-instantly, and you have an unlimited amount of balls.)

The paradox is the claim that because every ball labelled with any positive integer is extracted on some tick in the sequence, then all of the (infinite many) balls that are inserted will have been extracted by the after noon.   IE: There is a bijection between the countable sequence of ticks and the countable enumeration of balls.

In the first case this is easy to see, because for all $n\in\Bbb N^+$, ball $\#n$ will be extracted on index $\#n$ which is time $-2^{1-n}$ minutes before noon.   In the second case it is harder to see simply because you can not determine exactly when the ball will be extracted.   However, given enough ticks, then every ball will have been extracted some when along the way.

Now, just to melt your brain, ...

Consider this case: On each tick you insert $10$ balls numbered $10k-9$ to $10k$ but extract ball numbered $10k-9$.   Here you are inserting and removing exactly the same counts of balls on each and every tick, however, you are explicitly not removing all of the balls.   That is why ${\small 10}\infty{-}\infty$ is indefinite.

• It is not necessarily the case that ball #$k$ will ever actually be removed from the urn. It is possible at each tick that one of the other available balls is chosen by the random selection (provided at least one of the other balls has probability of being chosen>0). The map from the countable tick-set to the countable ball set need not be surjective, but must be injective; which is possible despite the two sets having identical cardinalities precisely because the cardinal in question is infinite. – Justin Benfield Jun 8 '16 at 5:04

The answer for the second paradox is that you cannot tell (in general) how many balls will be in the urn.

The explanation for the first paradox is that given any ball $k$ (k being its number), you know that it was removed on the $k$-th tick (time noon minus $\frac{1}{2^{k-1}}$ minutes). Hence every ball eventually ends up out of the urn.

The random case is very different because you no longer have any guarantee that a given ball $k$ has ever been removed from the urn. (This question is actually very delicate because it depends in a very essential way on what the probability distribution over the balls in the urn is each time a ball is removed). If the aforementioned probability distribution is known, then one may be able to compute the probability that a given ball has been removed or not (it may lie anywhere in $[0,1]$ depending on the distribution(s) used).