The Monkey and the Balls

I heard this story here at Mittag-Leffler institute from someone who heard it from someone else, who probably also heard it from someone else. (And so on.) What is the probability that I heard it from someone else? Just kidding.

Imagine a monkey with a basket and a scientist. Suppose that the scientist has infinitely many billiard balls labeled by natural numbers. (So we have to assume various things which are physically impossible, but never mind.) The scientist gives the balls labeled 1 and 2 to the monkey. The monkey puts them into the basket and then throws the ball number 1 away. Then the scientists gives the balls 3 and 4 to the monkey. Monkey puts them into the basket and throws 3 away. And so on. The scientist gives her the balls 2n-1 and 2n and the monkey always puts the ball 2n into the basket and throws the other one away.

How many balls are there in the basket after all the balls are gone through?

Correct, all even-labeled balls are there in the basket, hence infinitely many.

Imagine now they start over again and the scientist gives the monkey the balls 2n-1 and 2n. The monkey puts both of them into the basket. Then she picks the ball with the smallest label from the basket and throws it away. That is, on the first move scientist gives 1 and 2 and she throws 1 away; then the scientist gives 3 and 4 and she throws 2 away; then he gives 5, 6 and she throws 3 away, and so forth.

How many balls are there in the basket after all the balls are gone through?

Correct, no balls are there!

Suppose that we are looking at the scientist and the monkey from a distance. We cannot see the labels. Can we distinguish between the two different situations above? No. In both cases the scientist gives the monkey two balls and she throws one away and they keep repeating this. Just another paradox which follows from the concept of the infine.

Imagine now that the balls are not labeled. The scientist gives two balls to the monkey, she puts both of them to the basket, then she picks a random ball from the basket and throws it away. We can ask:

What is the probability that the basket is empty in the end?

The answer after Read More.

The probability that the basket will be empty is 1.

In fact this is quite simple once one knows how to handle probabilities. Suppose the balls are labeled, but the monkey just cannot read the labels, so the probability does not change. Let us calculate the probability P(k,n) that the ball number 2k is not thrown away before the (k+n):th round. It is the same as the probability that the ball number 2k-1 is not thrown on the (k+n):th round, since both balls are exposed to the monkey on the k:th round.

After the (k-1):st round there are (k-1) balls in the basket. The scientist gives two new balls, labeled 2k and 2k-1. The monkey does not throw the ball 2k away with probability [tex]\frac{k}{k+1}[/tex]. Thus

[tex]\displaystyle P(k,1)=\frac{k}{k+1}.[/tex]

The probability P(k,2) is the probability P(k,1) times the probability that the ball 2k is not thrown away on the next round as well. There are k+2 balls on the next round, so the probability is [tex]\frac{k+1}{k+2}[/tex]. So

[tex]\displaystyle P(k,2)=\frac{k}{k+1}\cdot\frac{k+1}{k+2}.[/tex]

By induction

[tex]\displaystyle P(k,n)=\frac{k}{k+1}\cdot\frac{k+1}{k+2}\cdots \frac{k+n-1}{k+n}.[/tex]

Note that the consequetive numerators and denominators cancel each other, so we get

[tex]\displaystyle P(k,n)=\frac{k}{k+n}.[/tex]

This approaches zero as n approaches infinity. Hence the probability that the ball number 2k is never thrown away is 0. That applies to all balls similarly, so each ball is thrown away at some point with probability 1. One can make this rigorous by considering the set of all monkey’s choice functions (a function which tells the monkey which ball to choose). Such a function is onto iff the basket is empty in the end. We just showed that the complement, i.e. the set of functions which are not onto has measure zero. (The measure is just the Lebesgue measure on the reals, see my earlier post for the connection between reals and the functions [tex]\mathbb{N}\to\mathbb{N}[/tex])

This is not surprising in the following sense. Suppose you have the functions of the form

[tex]f\colon\mathbb{N}\to \{0,1,2\}[/tex]

Each such function corresponds to a real number represented in the trinary system. It is a well known fact the the Cantor set is precisely the set of those real numbers whose trinary representation does not contain 1. Also the corresponding sets for 0 and 2 will be versions of the Cantor set and these correspond to the non-onto functions. But the Cantor set has measure zero, so the set of non-onto functions has measure zero.