The Ross-Littlewood Urn, math that surprises you lesson

An urn starts empty. At every stage ten new numbered balls go in and one ball comes out, so after each stage the urn holds nine more balls than before. Fit infinitely many stages into one minute and ask what is in the urn when the minute is over. Following the balls one at a time suggests a startling answer, nothing at all, even though the counts grow without bound. This page states the rules exactly, says what the contents at the end have to mean before the question has an answer, and shows that the answer depends on which balls are taken out and not only on how many.

Key terms

Ross-Littlewood paradox

Definition Balls numbered $1, 2, 3, \dots$ are available, one ball for each number, and an urn starts empty. Stage $n$ , for $n = 1, 2, 3, \dots$ , has two steps. First the ten balls numbered $10n - 9$ through $10n$ go into the urn. Then the ball with the lowest number in the urn is taken out, and a ball that has been taken out never goes back. Stage $n$ happens at

t_n = 60\left(1 - \frac{1}{2^n}\right)

seconds, which gives $30$ , $45$ , $52.5$ and so on. Every stage happens before the $60$ second mark, and there is no last stage. The ball taken out at stage $n$ is ball $n$ , so right after stage $n$ the urn holds exactly the balls

S_n = \{n + 1, \dots, 10n\},

which are $9n$ balls. The paradox asks how an urn that gains nine balls at every stage can be empty at the end, as it seems to be, since ball $k$ is taken out at stage $k$ and never returns.

The resolution has two parts. First, the rules describe only the stages, and no stage happens at the $60$ second mark, so the rules alone do not fix the contents at that moment. They must be defined. The standard definition is the set-theoretic limit, which puts a ball into the final collection exactly when it stays in the urn after every stage from some stage on. Second, with that definition the final collection is empty while the counts $9n$ grow without bound. Both facts are true at once, because the number of elements of the limit set and the limit of the numbers of elements are different things. Nothing goes missing at any single stage, where exactly ten balls go in and one comes out, and there is no final moment at which many balls vanish together. If instead stage $n$ takes out ball $10n$ , the highest ball of the new batch, the counts are again $9n$ , but every ball whose number is not a multiple of $10$ stays forever, and the limit is infinite. The story is a mathematical model of a sequence of sets. It is not a procedure that a real urn could carry out, and saying what a physical urn would contain at the $60$ second mark needs further physical assumptions that the rules do not supply.

In plain words Every ball you can name leaves the urn at a definite stage and stays out. The urn keeps getting fuller only because new balls keep arriving, and each of those leaves later too. How many balls the urn holds after each stage and which balls stay for good are different questions, and here they have very different answers.

Example Stage $1$ puts in balls $1$ to $10$ and takes out ball $1$ , leaving balls $2$ to $10$ . Stage $2$ puts in balls $11$ to $20$ and takes out ball $2$ , leaving balls $3$ to $20$ , and stage $3$ puts in balls $21$ to $30$ and takes out ball $3$ , leaving balls $4$ to $30$ . The counts are $9$ , $18$ and $27$ . The pattern continues because, if the urn holds balls $n$ to $10(n - 1)$ after stage $n - 1$ , then stage $n$ adds balls $10n - 9$ to $10n$ , the lowest ball present is ball $n$ , and taking it out leaves $S_n$ . Ball $1000$ arrives at stage $100$ , in the batch of balls $991$ to $1000$ . It is in the urn after stages $100$ through $999$ , which are $900$ stages, and it leaves at stage $1000$ , after which the urn holds the $9000$ balls numbered $1001$ to $10000$ . From then on ball $1000$ is absent after every stage.

Supertask

Definition A supertask is a process of infinitely many steps, carried out one after another within a finite span of time. Usually step $n$ happens at a time $t_n$ , with $t_1 < t_2 < t_3 < \cdots$ and all the times less than a time $T$ that they approach, so there is no last step before $T$ . The steps determine the state right after each step, and so at every moment before $T$ , if nothing happens between steps. No step happens at $T$ itself, so the steps alone do not determine the state at $T$ . A statement about the state at $T$ needs an extra rule, such as a mathematical definition of the limit or a physical assumption about how things behave at $T$ .

In plain words If each step takes half as long as the one before, infinitely many steps fit into a finite time, the same way Achilles in Zeno’s Achilles and the Tortoise runs infinitely many stretches in a finite time. The steps tell you everything up to the deadline and nothing at the deadline itself.

Example In the urn the waits before the stages are $30$ seconds, $15$ seconds, $7.5$ seconds and so on, each half the one before, and they add up to the whole minute as a geometric series,

\begin{aligned} &30 + 15 + 7.5 + \cdots \\[0.4em] &\quad = \sum_{n=1}^{\infty} \frac{60}{2^n} = 60. \end{aligned}

After stage $n$ the time left is $60/2^n$ seconds, which is $0.05859375$ seconds after stage $10$ and about $4.7 \times 10^{-29}$ seconds after stage $100$ . Any moment before the $60$ second mark comes after only finitely many stages. A real urn would need hands that work faster and faster without any limit, and nothing in the mathematics says such a device can exist. The mathematical model uses only the order of the stages, not their times.

Set-theoretic limit

Definition Let $S_1, S_2, S_3, \dots$ be a sequence of sets. An element $x$ is eventually in the sets if there is a stage $m$ such that $x$ belongs to $S_n$ for every $n \ge m$ , and eventually out if there is a stage $m$ such that $x$ belongs to no $S_n$ with $n \ge m$ . The sequence has a set-theoretic limit when every element is either eventually in or eventually out, and then the limit is the set of elements that are eventually in. In symbols, the elements that are eventually in form the lower limit, and the elements that belong to infinitely many of the sets form the upper limit,

\begin{aligned} \liminf_{n \to \infty} S_n &= \bigcup_{m=1}^{\infty} \bigcap_{n=m}^{\infty} S_n, \\[0.4em] \limsup_{n \to \infty} S_n &= \bigcap_{m=1}^{\infty} \bigcup_{n=m}^{\infty} S_n, \end{aligned}

where a union collects the elements that belong to at least one of the sets and an intersection keeps the elements that belong to all of them. The lower limit is always contained in the upper limit, and the set-theoretic limit exists exactly when the two are equal.

In plain words Decide ball by ball. A ball belongs to the limit if, from some stage on, it is always in the urn, and it stays out of the limit if, from some stage on, it is never in the urn. How many balls the sets contain plays no part in this decision.

Example In the urn, ball $k$ belongs to $S_n$ exactly when $n + 1 \le k \le 10n$ , that is, when

\frac{k}{10} \le n \le k - 1.

So ball $k$ is missing from $S_n$ for every $n \ge k$ . Every ball is eventually out, no ball is eventually in, and

\lim_{n \to \infty} S_n = \varnothing,

the empty set. Ball $1$ is not in the urn after any stage, since it leaves at the stage where it arrives. For a sequence without a limit, take $S_n = \{1\}$ for odd $n$ and $S_n = \varnothing$ for even $n$ . The element $1$ belongs to infinitely many of the sets and is missing from infinitely many, so the upper limit is $\{1\}$ , the lower limit is empty, and there is no set-theoretic limit.

Divergent sequence

Definition A sequence of real numbers $a_1, a_2, a_3, \dots$ converges to a real number $L$ if its terms eventually stay as close to $L$ as we like, which means that for every $\varepsilon > 0$ there is a stage $N$ with $\lvert a_n - L \rvert < \varepsilon$ for all $n \ge N$ . A sequence that converges to no real number is divergent. One way to diverge is to grow without bound, written $a_n \to \infty$ , which means that for every number $M$ there is a stage $N$ with $a_n > M$ for all $n \ge N$ . Another is to keep jumping between values, like $1, 0, 1, 0, \dots$ .

In plain words A convergent sequence settles down near one number. A divergent one never does, either because it runs off to infinity or because it keeps moving around.

Example The counts $9, 18, 27, \dots$ of the urn diverge to infinity. For $M = 1{,}000{,}000$ take $N = 111{,}112$ , since $9 \cdot 111{,}112 = 1{,}000{,}008$ is more than a million and every later count is larger still. For a fixed ball $k$ , the sequence that records $1$ when the ball is in the urn after stage $n$ and $0$ when it is not converges to $0$ , because it is $0$ from stage $k$ on. Writing $\lvert S \rvert$ for the number of elements of a set $S$ , the urn has

\begin{gathered} \lim_{n \to \infty} \lvert S_n \rvert = \infty, \\[0.4em] \Bigl\lvert \lim_{n \to \infty} S_n \Bigr\rvert = 0. \end{gathered}

Counting first and then taking the limit gives a different answer from taking the limit first and then counting. A divergent sequence of counts therefore says nothing by itself about which elements are in the limit set.

Check yourself

In the original urn, at which stage does ball $537$ go in, at which stage does it come out, and how many balls are in the urn right after it comes out?

Show the answer

Stage $n$ puts in balls $10n - 9$ to $10n$ , so ball $537$ arrives with balls $531$ to $540$ , at stage $54$ . Ball $n$ is taken out at stage $n$ , so ball $537$ leaves at stage $537$ . Right after that stage the urn holds

S_{537} = \{538, \dots, 5370\},

which is $9 \cdot 537 = 4833$ balls. Ball $537$ was in the urn after stages $54$ through $536$ , so after $483$ stages, and it is absent after every later stage.

Change the rule. Each stage still puts in the ten balls $10n - 9$ to $10n$ , but now it takes out ball $2n$ . How many balls are in the urn after stage $n$ , and what is the set-theoretic limit?

Show the answer

First check that the rule can always be followed. Once stage $n$ has put in its batch, the balls $1$ to $10n$ have all arrived, ball $2n$ among them, and the balls taken out before stage $n$ are $2, 4, \dots, 2n - 2$ , so ball $2n$ is in the urn when stage $n$ wants to take it out. After stage $n$ the urn holds balls $1$ to $10n$ except $2, 4, \dots, 2n$ , which is $10n - n = 9n$ balls, exactly the counts of the original urn. After stage $3$ , for example, it holds balls $1, 3, 5, 7$ and $8$ to $30$ , which are $27$ balls.

The limit is very different. Ball $2m$ leaves at stage $m$ and never returns, so every even ball is eventually out. No odd ball is ever taken out, so every odd ball is eventually in. The set-theoretic limit is the infinite set $\{1, 3, 5, 7, \dots\}$ of odd numbers. The two urns have the same counts after every stage and completely different limits, so the counts alone cannot decide what is in the limit.

Keep ten balls in and one ball out at every stage, with no ball ever going back. Can you choose which ball to take out at each stage so that the set-theoretic limit is exactly $\{1, 2, 3, 4, 5\}$ ?

Show the answer

Yes. At each stage take out the lowest-numbered ball greater than $5$ . Stage $1$ puts in balls $1$ to $10$ and takes out ball $6$ , stage $2$ takes out ball $7$ , and in general stage $n$ takes out ball $n + 5$ . After stage $n$ the urn holds

\{1, \dots, 5\} \cup \{n + 6, \dots, 10n\},

which is $5 + (10n - n - 5) = 9n$ balls, the same counts once more. Balls $1$ to $5$ never leave, and every ball $k > 5$ leaves at stage $k - 5$ , so the limit is $\{1, 2, 3, 4, 5\}$ .

The same rule with $5$ replaced by any $m$ from $0$ to $9$ leaves exactly balls $1$ to $m$ , and $m = 0$ is the original urn. For $m \ge 10$ it fails at stage $1$ , where no ball above $m$ is present. Keeping the balls $10, 20, \dots, 10m$ instead and always taking out the lowest-numbered other ball works for every $m$ . Each batch contains at most one kept ball, so there is always another ball to take out, and each of the other balls has only finitely many lower-numbered balls ahead of it, so it leaves at some finite stage. So with the same counts $9n$ , the limit can have no balls, any finite number of balls or infinitely many.

The Ross-Littlewood Urn

Video 1, chapter 22

Key terms

Ross-Littlewood paradox

Supertask

Set-theoretic limit

Divergent sequence

Check yourself