| HPS 0628 | Paradox | |
Back to doc list
The Probabilistic Urn Supertask
John D. Norton
Department of History and Philosophy of Science
University of Pittsburgh
http://www.pitt.edu/~jdnorton
The Ross-Littlewood urn paradox recalled earlier was distinctive for combining two of the major themes of these chapters:
• A supertask requiring the completion of an
infinity of actions; and
• the curious results recovered when we subtract one infinity from
another.
When Ross wrote about the supertask, he included a further detail that connects with another theme of these chapters:
• Chance systems do not always behave as we expect.
That is, instead of assuredly removing the lowest numbered ball at each stage, the ball to be removed is chosen randomly from those in the urn.
We then ask the same question: how many balls are in the urn at the end of the supertask?
It is not immediately obvious how to answer the question. There is no longer an assurance of any particular schedule of removals from the urn. In one schedule, we might remove the smallest numbered ball; then the largest; then some other; and so on. Another schedule might look rather different. Chance will decide which schedule is realized. We shall see below there are schedules of removals that can lead to any number of balls in the urn at the completion of the supertask--from none to infinity and every number in between. Thus, we might reasonably expect that all these different possible numbers in the urn arise with some varying range of probabilities.
The chances, however, do not behave in accord with these expectations. What Ross showed--and what we shall see in greater detail below--is that the result of an empty urn turns out to be the outcome with probability one. The urn empties with the highest probability. It is possible that things could be otherwise, that the urn may have one or more balls in it at the end of the supertask. All these alternative possibilities taken together arise only with probability zero. That is, they have the lowest chance that probability theory can assign.
Here is the text describing the Ross-Littlewood urn supertask from the earlier chapter:
We are to imagine a countable infinity of balls numbered 1, 2, 3, ... and an urn of limitless capacity. In the span of time from one minute to midnight (time "-1") to midnight (time "0") we undertake the following supertask:
At time -1, we place balls 1 to 10 in the urn and remove ball 1.
At time -1/2, we place balls 11 to 20 in the urn and remove ball 2.
At time -1/3, we place balls 21 to 30 in the urn and remove ball 3.
At time -1/4, we place balls 31 to 40 in the urn and remove ball 4.
and so on until time 0.
The question is: How many balls are in the
urn at midnight?
...
At time -1, ball 1 was removed.
At time -1/2, ball 2 was removed.
At time -1/3, ball 3 was removed.
At time -1/4, ball 4 was removed.
and so on for all balls.
Thus, at midnight, there can be no numbered ball in the urn. Since every ball has a number, it follows that there can be no balls in the urn.
The initial configuration looks like this:
The balls numbered 1 to 10 are moved into the urn:
Then ball number 1 is removed:
The task continues with the next set of ten balls, and the next, and so on infinitely.
Littlewood's version of the supertask ran as above. (See his original text here.) Ross' later account added the extra piece of interest to us. (See his original text here.) Instead of always removing the lowest numbered ball in the urn, a ball is chosen at random for removal; that is, each ball in the urn has an equal probability of removal, when a removal is to happen.
In the first stage, any of these removals can happen, and with equal probability:
To get a sense of how random removal can affect things, it is helpful to see how different non-random removal schedules can lead to almost any desired content for the urn at the end of the supertask. Here are a few sample schemes:
| Removal scheme | Final content of urn |
| Remove lowest numbered ball | Empty |
| Remove highest numbered ball | Infinity of balls; all numbers, excepting 10, 20, 30, ... |
| Remove lowest even numbered ball | All odd numbered balls. |
| Removes lowest odd numbered ball | All even numbered balls |
| Remove highest numbered ball until there are at least 127 balls in the urn; then always remove 128th smallest | 127 balls |
| Remove highest numbered ball until there are at least [your preferred number] balls in the urn; then always remove [your preferred number + 1]th smallest | [your preferred number] balls |
This table shows that, once we allow different schemes for removal, we can end up with any number of balls in the urn, from zero to infinity. If we select balls randomly, then any one of these schemes might be realized. That is, we might end up with any number of balls in the urn from zero to infinity.
The catch, of course, is that many of these scheme will be so improbable that they happen with zero probability. For example, the first scheme requires the lowest numbered ball to be selected each time. In this case, at each stage, there are ten or more balls in the urn. So the probability of the smallest ball being chosen is 1/10 or less. That means the probability of the smallest ball being chosen at every stage is less than:
(1/10) x (1/10) x (1/10) x ... infinitely... = 0
That is, the probability of this first scheme arising is zero.
More generally, similar calculations show that each specific scheme in the table above has a probability zero of arising if the selection is random.
What we need to determine, however, is not just the probability of one specific scheme. To answer the original question, we need to know the probability not of a single scheme, but of all the schemes together that might lead some specified outcome:
• What is the probability of any scheme that leads
to an urn filled with infinitely many balls?
• What is the probability of any scheme that leads to an urn filed with
exactly 127 balls?
• What is the probability of any scheme that leads to an
empty urn?
What Ross was able to show in a calculation in his text is that, with probability one, the effect of the random selections will lead to an empty urn at the conclusion of the supertask. That is, with the highest probability, the urn will be empty at the end of the supertask.
Ross' calculation is straightforward but complicated and sufficiently so that it is hard to see easily why, with probability one, there will be no balls in the urn at the end of the supertask. Here is a greatly simplified version of the supertask whose behavior is much easier to compute.
First, here is the non-probabilistic version of the supertask. As before, we have an infinity of balls numbered 1, 2, 3, ... The task proceeds through an infinity of stages 0, 1, 2, 3, ... completed at times -1, -1/2, -1/3, ... as in the original supertask.
Stage 0. Ball 1 is placed in the
run.
Stages 1, 2, 3, ... The next numbered ball is placed in the urn;
and then one ball is removed.
We can imagine many different schedules of removals. Since one ball is added and one removed in each stage, at the end of each of the finite stages, there will be exactly one ball in the urn. The number of that ball will vary according to schedule of removals implemented.
That there is always one ball exactly in the urn at the end of all finite stages, does not ensure that there will a ball in the urn at the end of the supertask. If the schedule of removals is like that of the original Ross-Littlewood supertask, the smaller numbered ball is removed at each stage. Then, when the supertask is completed, there will be no ball in the urn. For:
Ball 1 is removed in stage 1.
Ball 2 is removed in stage 2.
Ball 3 is removed in stage 3.
and so on.
For each ball has a number and this schedule has each ball removed in some stage prior to the completion of the supertask.
We can ask after the consistency of this analysis (and indeed that of the original Ross-Littlewood urn supertask). Might we simply be at an intermediate stage of the analysis? Might the conclusion of an empty urn at the end of the supertask merely be one half of the derivation of a contradiction? Might a second inference lead to the conclusion that there has to be a ball in the urn at the conclusion of the supertask? Then the whole analysis would be defeated. We would simply have found that our initial suppositions in setting up the supertask involved a contradiction.
While an absolute proof of consistency is beyond us, we can as before offer a relative consistency proof, such as those offered earlier. The most pressing worry is that the continuity in space of the existence of the balls might somehow lead to the necessity of a ball in the urn at the end of the supertask.
This continuity of the balls can be represented by the continuity of the trajectories in space and time in a geometric plotting of the motion of the balls. Here is a plot in space and time of the motions of the balls.
Each ball approaches the urn at very high speed (so
that its trajectory is near horizontal in the figure). Each ball then
resides in the urn, moving more slowly (so that its trajectory is more
vertical). Then each ball leaves the urn at
high speed prior to the end of all the stages of the supertask. That is:
ball 1 leaves in stage 1;
ball 2 leaves in stage 2;
ball 3 leaves in stage 3;
and so on.
The continuous existence in space of each ball is preserved since the
trajectories of each ball does not make jumps or disappear in the urn.
We can also see in the plot that, in alternating times, the urn contains one ball and then two balls and then one ball and so on. This alternation continues up the very moment of the end of the supertask. The shaded bands in the figure below show the times in which the urn contains just one ball:
The shaded bands in the next figure below show the times in which the urn contains two balls:
The lines in these plots, considered simply as lines in a geometric figure, have properties that mirror those of the motions of the balls in the urn supertask. It follows that if the geometry of these lines is consistenty implemented, then so are the motions of the supertask. That is, if it is impossible to deduce a contraction concerning the geometry of the lines, then it is also impossible to deduce a contradiction for the motion of the balls in the supertask.
This completes the demonstration of relative consistency.
To arrive at the probabilistic version of this simplified supertask, we add probabilistic choices in the schedule of removals.
The new schedule is:
Stage 0. Ball 1 is placed in the
urn.
Stage 1. Ball 2 is added to the urn; and one ball is removed.
Each ball has a probability 1/2 of removal.
Stage 2. Ball 3 is added to the urn; and one ball is removed.
Each ball has a probability 1/2 of removal.
Stage 3. Ball 4 is added to the urn; and one ball is removed.
Each ball has a probability 1/2 of removal.
and so on
As in the non-probabilistic case, since each stage involves the addition and removal of just one ball, there is always exactly one ball left in the urn at the end of each finite stage. Just which numbered ball remains, however, will depend on the specific schedule of removals.
To proceed, we need to find a compact way to represent the different schedules of removal. Since each removal has to choose between two balls only, the schedule is much simpler than in the original supertask:
Either the larger numbered ball is removed
(action L);
or the smaller numbered ball is removed (action S).
What results is the branching structure shown here for the content of the urn through the stages:
We will represent a schedule of removals as a list of S and L. For example
SLSLSLSLSLSLSLSLS...
represents an indefinite alternation between the removal of the smaller numbered ball and the removal of the larger numbered ball.
With this simplified supertask, it is easy to specify all those schedules of removals that will leave a ball in the urn at the end of the supertask.
The general formula is:
Sequence of removals that leaves a ball in the
urn at the end of the supertask:
[any combinations of S's and L's]LLLLLLLLLLLLLLL....
The infinity of L's at the end is a "tail" of L's. For example, the simplest case is just:
LLLLLLLLLLLLLLLL...
We can represent the
urn with one or two balls by a grey rectangle with one or two numbers
that are the numbers of the balls in the urn. Then the sequence of
additions (e.g. "+2" means "add ball number 2") and removals proceeds as
follows:
1
+2 →1,2
L→1
+3 →1,3
L→1
+4 →1,4
...→1→
...→1→
...→1→...
etc.
At the end of the supertask, ball 1 remains in the urn.
Another sequence with the same infinite tail of L's is
SSLLLLLLLLLLLLLL...
1
+2 →1,2
S→2
+3 →2,3S→3
+4 →3,4
L→3
+5 →3,5L→3
...→3→
...→3→
...→3→...
etc.
At the end of the supertask, it will leave ball 3 is the urn.
The simplest case that leaves no ball in the urn at the end of the supertask is:
SSSSSSSSSSSSSSS...
Each S just removes the smaller numbered ball, so the ball number in the vase keeps increasing by one number with each stage.
1
+2 →1,2
L→2
+3 →2,3
L→3
+4 →3,4
...→4→
...→5→
...→6→...
etc.
With this scheme there will be no balls in the urn at the end of the supertask, since each ball numbered 1, 2, 3, ... is removed at some stage of the supertask.
More generally, following through this reasoning, we find:
Sequence of removals that leaves no ball in
the urn at the end of the supertask: any sequence that has an infinity of
S's in it.
It doesn't matter to this condition how many L's are interleaved between the S's. All the following schedules leave no balls in the urn at the of the supertask:
SLSLSLSLSLSLSLSLSLSLSL...
LLSLLSLLSLLSLLSLLSLLSLLS...
LLLLSLLLLSLLLLSLLLLSLLLLS...
As the infinity of S removals are implemented, they will eliminate the smallest numbered balls, one by one, until none are left.
Let us now compute how probable it is that there is a ball remaining in the urn at the end of the supertask. We know from above that this outcome will arise only if the sequence of removals has an infinite tail LLLLLLLLLLLLLL... Since each L has a probability of (1/2), the probability of the tail is
(1/2) x (1/2) x (1/2) x ... infinitely... = 0
Since there are a countable infinity of sequences with tails, we conclude:
Probability a ball remains
in the urn
at the end of the supertask
= Probability (set of all sequences with infinite tail LLLL...)
= 0 + 0 + 0 + ...for the countable infinity...
= 0
There are only two possibilities: a ball remains at the end of the supertask or the urn is empty. Since the two probabilities sum to one, we conclude:
Probability that the urn is empty at the end of the supertask = 1
The
calculation above has been given in abbreviated form. Here it is in great
detail for those who want it. Each of the L tailed
sequences has the form:
[finite head]LLLLLLLLLLLLLL...
where "finite head" = some finite initial sequence of L's
and S's.
The probability of the head is just some finite probability greater than
zero. If the head has, say, four removals in it, such as LSLS:
Probability(LSLS) = (1/2) x (1/2) x (1/2) x (1/2) = 1/16
The probability of the tail is:
Probability (LLLLLLLLLLLLLL...)
= (1/2) x (1/2) x (1/2) x ...
infinitely = 0
Combining we have:
Probability ([finite head]LLLLLLLLLLLLLL...)
= probability finite head x 0 = 0
We can see that there is a countable infinity of these L
tailed schedules.
There is one with a head of length 0:
LLLLLLLLLLLLL...
There is one with a head of length 1:
SLLLLLLLLLLL...
There are two with a head of length 2:
SSLLLLLLLLLL...
LSLLLLLLLLLL...
There are four with a head length of 3:
SSSLLLLLLLLL...
LSSLLLLLLLLL...
SLSLLLLLLLLL...
LLSLLLLLLLLL...
Continuing in this vein, we find that for each head length, there are
finitely many schedules with an infinite tail LLLLLLL...
There is a countable infinity of head lengths, 0, 1, 2, 3, ... Hence the
total number of tailed schedules is the infinite sum of all these finite
numbers, which is itself a countable infinity.
Just as in the case of the non-probabilistic supertask, this is an unexpected result. At all stages of the task, there is exactly one ball in the urn. It seems so natural to expect that state to persist through to the end of the supertask. But it does not. There is one ball in the urn at every moment prior to midnight. But at the moment the supertask completes, suddenly, at midnight, there is no ball in the urn.
This sudden emptying is hard to avoid. What drives it is that schedules of removals with infinitely many S's are most probable. We might try to prevent this sudden emptying by shifting the probabilities to favor L's. For example, this probability assignment strongly favors L:
P(S) = 0.001 P(L) = 0.999
Even this favoring with probability 0.999 is insufficient to prevent the emptying of the urn at the end of the supertask.
If we examine a typical schedule compatible with these probabilities, we would find on average 999 L's and just one S per thousand. Even though the presence of the S's is quite sparse, even one in a thousand is not sparse enough. For after this first thousand, there is a second thousand, and then a third thousand, as so on infinitely. Each thousand will on average host one S, so that we have in the total schedule an infinity of S's. That infinity is enough to ensure that each ball is removed at some stage.
To preclude this infinity of S's, we still need a schedule or removals with an infinite tail of L's. The probability of this infinite tail remains zero. Instead of multiplying together an infinity of (1/2)'s, we have an infinity of 0.999's to multiply together. The probability of an infinite tail LLLLLLLL... is:
0.999 x 0.999 x 0.999 x ...infinitely... = 0
Duplicating the analysis above, replacing probability 1/2 with probability 0.999, leads to the same result: with probability one, the urn will be empty at the conclusion of the supertask.
----oOo----
In the analysis of the simplified urn supertask, the urn empties at the end of the supertask unless chance gives us a schedule of removals with an infinite tail LLLLLLLL... And chance does not oblige. Schedules with this infinite tail arise with probability zero.
This general analysis applies also to the probabilistic version of the original Ross-Littlewood urn supertask. To preclude the emptying of the urn, we require a schedule or removals with a similar tail. Instead of the simplified supertask's L, the corresponding tail consists of an infinity of removals:
L = remove any ball other than the smallest
It turns once again that a schedule of removals with an infinite tail of L's is a probability zero outcome. Showing that this is the case is harder. Since the number of balls in the urn is growing with each stage, the probability of an L at each stage will be different. In his original original text, Ross calculates some of the cases and then reassures us of the general result: that any balls remain is the urn occurs only with probability zero.
The probabilistic dichotomy: In Zeno's
dichotomy, a runner seeks to run a track from position 0 to position 1 and
must pass an infinity of intermediate points at positions 1/2, 3/4, 7/8,
... In the probabilistic version, if the runner arrives at one of these
intermediate points, the runner chooses between two options, each with
probability 1/2. They are:
(a) pause for a short time; or
(b) run on to the next position.
Successive pauses occupy successively shorter times: 1/2 sec., 1/4 sec.,
1/8 sec., etc. so that an infinity of pauses can be accommodated in finite
time.
What is the probability that the runner completes the track?
(Hint: the analysis is very similar to the one given for the simplified urn supertask.)
Variation on the probabilistic dichotomy: The supertask is as above. However each pause lasts one second. What is the probability that the runner completes the track?
September 19, 2021
Copyright, John D. Norton