| HPS 0628 | Paradox | |
Back to doc list
How to Build An Infinite Lottery Machine
(And How Not to Build One)
John D. Norton
Department of History and Philosophy of Science
University of Pittsburgh
http://www.pitt.edu/~jdnorton
The discussion of the last chapter treats the chance properties of an infinite lottery machine whose operation conforms with label independence. Can there be such a machine? No doubt some unrealistic idealizations are needed to specify its mechanism. As a practical matter, no one can assemble an infinity of balls and shake them up in an infinite container. Are these idealizations modest? Or are they extravagant?
We shall see below, at the end of the discussion, that there is at least one highly idealized mechanism, drawing on quantum theory, that realizes an infinite lottery machine. Before we venture to such exotic realms, it is interesting to ask a narrower question. What if we start with the more familiar randomizers and try to combine them, even in exotic ways?
Can an infinite lottery machine whose
operation conforms with label independence be constructed from ordinary
probabilistic randomizers, such as tossed coins, rolled dice and spinning
pointers?
We shall allow some exotic processes in the construction, for otherwise merely handling an infinity of distinct outcomes will be beyond our design specification. In particular, we will allow supertasks, that is, the completion of an infinity of discrete tasks.
The proposals explored
below are elaborated, along with others in John D. Norton, "How
to Build an Infinite Lottery Machine" European Journal for
Philosophy of Science, 8 (2018), pp. 71-95.
(with Alexander R. Pruss) Correction to John D. Norton “How to Build an
Infinite Lottery Machine, ” European Journal for Philosophy of Science. 8
(2018), pp. 143-44.
John D. Norton, "How
NOT to Build an Infinite Lottery Machine." Studies in History and
Philosophy of Science. 82(2020), pp. 1-8.
A warning that things will not be so simple comes in one of the earliest treatments of an infinite lottery in the recent literature. The paper gives no ordinary mechanism for how the machine operates. Rather the operation is specified as follows. (p. 223)
"In an entirely fair and purely random way, God would simply choose a number. The fairness of the procedure would consist in the fact that the chance of any given number being chosen would be the same as that of any other number."
Presumably, they chose a supernatural mechanism since they could not find a simpler mechanism such as some combination of coin tosses. To see what the problem may have been, let us look at some plausible candidates.
We begin with what initially seems like a promising
strategy. We consider a track with cells, numbered 1, 2, 3, ... A flea
jumps from one to the next cell. If the flea starts at cell 1 and jumps to
the next and then the next under some transition probability rule, it is
easy to find a rule that gives a uniform probability
distribution over the cells, if the number of cells is finite.
For example, assume that the track has 100 cells. Here are the probabilities that the flea, starting in cell one, jumps to the next cell:
Probability of jump cell 1 to cell 2 = 99/100
Probability of jump cell 2 to cell 3 = 98/99
Probability of jump cell 3 to cell 4 = 97/98
...
Probability of jump cell 98 to cell 99 = 2/3
Probability of jump cell 99 to cell 100 = 1/2
These probabilities would be realized by ordinary randomizers that inform the flea as to whether it should jump. A pointer spun on a dial with 100 divisions can provide the first transition probability of 99/100. The second could come from one with 99 divisions; and so on.
It is now easy to see that, if the flea jumps according to these transition probabilities, that the probability that it halts in any particular cell is 1/100.
For example:
The probability that the flea halts
in cell 1
= probability that the flea does not jump to cell 2
= 1 - probability that the flea does jump to cell 2
= 1 - 99/100 = 1/100
The probability that the flea halts
in cell 10
= probability that flea jumps from cell 1 to cell 2
x probability that flea jumps from cell 2 to cell 3
x probability that flea jumps from cell 3
to cell 4
...
x probability that flea jumps from
cell 9 to cell 10
x probability
that flea does NOT jump from cell 10 to cell 11
= 99/100 x 98/99 x 97/98 x ... x 91/92 x (1-90/91)
= 1/100
We might now try to realize an infinite lottery machine by taking the number of cells to an infinite limit. That is, we consider the case of a track with a countable infinity of cells, 1, 2, 3, ... The idea seems promising. The schedule of transition probabilities above can be adapted to any finite track size, no matter how large. Might the uniformity of chances be preserved if we take the infinite limit?
Since there are an infinity of cells that could be visited, we would assume that the pace of the fleas jumping is accelerated, according to the sorts of schedules that we saw with supertasks described in an earlier chapter. That way, all the jumping the flea undertakes will be completed in a finite time.
If we take the limit of transition probabilities as the number of cells goes to infinity, we end up with:
Probability of jump cell 1 to cell 2 = 1
Probability of jump cell 2 to cell 3 = 1
Probability of jump cell 3 to cell 4 = 1
...
That is, for each cell, there is a probability of one that this cell is vacated. It follows that the probability that the flea remains in any nominated cell is zero. Thus we end up with the awkward conclusion that, with probability one, the flea is nowhere on the track since:
probability(flea in cell 1) = probability(flea in cell 2) = ... = 0
How are we to think of this? Are we to say that the flea has visited every cell and jumped off to infinity?
This, at least, was where I
left the discussion in my 2018 paper cited above. I now realize that this
was hasty. The situation is messy and there is more
to say. We have an outcome space that has a countably infinite
number of states: flea in cell 1, flea in cell 2, etc. There is no outcome
in the space for the flea "jumping off to infinity." That is, we have an
outcome space, such that the probability of each individual outcome is
zero. If the probability measure is countably additive, we have a
contradiction with the unit norm of the probability measure. At best we
can say that the probability measure is only finitely additive. Then,
following the discussion of the last
chapter, we have escaped a contradiction. But have we built an
infinite lottery machine? There are two problems.
First, the scenario is incompletely defined since we have not
provided a specification for the randomizer that provides the probability
one transition probability. A poor choice here would lead to incoherence.
For example, a probability zero outcome is that we toss a coin and it
comes up both heads and tails. That poor choice leaves us no measure zero
but still possible outcome that would allow the flea to stay in the cell.
Second, given the incomplete specification of the randomizer,
there is no obvious symmetry in the resting positions of the flea. Nothing
in this scenario ensures that label independence holds.
Here is a scheme designed to avoid the difficulties of the jumping flea. Instead of the flea always jumping in one direction only on its track, we will assume that the flea may jump in either direction. To host these jumps, we will assume that the flea is on a huge track with a countable infinity of cells extending in the plus and minus number direction, so that they are numbered ..., -3, -2, -1, 0, 1, 2, 3, ...
For concreteness, we can use the following transition probabilities for each step of the flea's walk:
Probability of flea remaining in present cell = 1/2
Probability of flea jumping one cell in the positive direction = 1/4
Probability of flea jumping one cell in the negative direction = 1/4
Unlike the jumping flea above, the only randomizer needed is a quite ordinary one that can deliver outcomes with these three probabilities. (Two tossed coins would suffice. tail-tail = jump one cell negatively; head-head = jump one cell positively; one head-one tail = stay in present cell.)
The flea starts initially at cell zero. With each step of the process, the flea either stays were it is or moves one cell negatively or one cell positively. What results is a process that has been dissected at length in the literature on stochastic processes, the random walk. After a large number of jumps, the probability of the various positions of flea comes close to the bell curve of a normal distribution.
For N steps, the various bell curves for the flea's position x are plotted here. The important fact is that, as the number of steps in the process N grows large, the bell curve probability distributions become flatter and approach arbitrarily closely to a uniform distribution over all the positions.
So far everything has proceeded within the normal analysis of a random walk. We now add an extra piece. The time required for each step is accelerated so that infinitely many steps are completed in a finite time. In the limit of infinitely many steps, we end up with a probability distribution of various positions that is uniform over all the countably many cells. It looks like the supertask realizes an infinite lottery machine.
This appearance, however, is deceptive. For it makes the assumption that we can always assign a definite cell position to the flea once the infinity of steps is completed. That assumption does not hold in general.
Most commonly the flea will continue jumping left and right throughout the infinity of steps. That means that its trajectory does not settle down to any definite position at the end of the infinity of steps. This behavior is like that of the marble in Black's transfer machine. Since the transfers never ceases, we can assign no definite position to the marble at the end of the process. This failure to adopt a definite position is illustrated by the flea trajectory on the left of the figure:
For the flea to have a definite position, it must cease its jumping at some finite stage and stay in its current cell for all the remaining stages. This convergence to a definite position is illustrated by the flea trajectory on the right of the figure.
It can happen that flea's jumping ceases at some finite stage so that it has a definite position at the end of the infinitely many stages. However the probability of this happening is zero. For example, if the flea is to stop jumping at stage 1000, then its future behavior is:
Step 1001, no jump. Probability = 1/2
Step 1002, no jump. Probability = 1/2
Step 1003, no jump. Probability = 1/2
and so on infinitely.
That is
Probability that the flea first
stops jumping at stage 1000
= 1/2 x 1/2 x 1/2 x 1/2 x ... (infinitely often)
= 0
Since there are a countable infinity of stages at which the flea can stop jumping, the probability that the flea first stops jumping at any stage is the sum of countably many zero probabilities:
0 + 0 + 0 + 0 + 0 + ... = 0
Hence we have for the possible configurations of the flea-track system at the end of the supertask:
Probability(flea in cell 1) = probability(flea
in cell 2) = ... = 0
Probability(flea has no definite position) = 1
That is, all the possible trajectories of the flea
form a huge outcome space. Those trajectories in which the flea settles
into a definite position at the end of the supertask is a subset of
probability zero. In so far as this supertask random walk implements an
infinite lottery machine, it succeeds in returning a
result with probabilty zero.
This has been a discouraging start. Perhaps we are not using these ordinary randomizers well. Here's another approach. Collect a countable infinity of coins. Toss them all fairly and lay out the results in an array as shown. The resulting outcome space is huge. it is uncountably infinite. Somewhere in this huge outcome space there must be what we seek, a countable infinity of outcomes all of equal chance.
One way to encode a countable infinity of outcomes of equal chance in this array is to look for rows in the array of the form:
Head-Head-Head-...-Tail-Tail-Tail-...
that is, some finite list of all heads followed by all tails. For example the outcome "5" is:
5 = Head-Head-Head-Head-Head-Tail-Tail-Tail-Tail-...
The outcome of the infinite lottery machine is the number encoded in the first row that encodes a number. The infinite array below, for example, returns 5 as its result:
It may now seem that we have devised an infinite lottery machine using ordinary randomizers. It is exotic in structure. We do need some sort of supertask to flip the infinity of coins and then to search through the array to find the first row that encodes a number.
Since there is an infinity of these rows, it seems safe that there will be a number encoded in at least one of them. It seems safe, but alas it is not so. There is a probability zero that any of the infinity of rows encodes a number.
To see this:
The probability that the first row encodes the number 5 is zero, since the
row arises from two outcomes
Probability 5 heads in a row = 1/2 x 1/2 x 1/2 x 1/2 x 1/2 = 1/32
Probabillity ∞ tails in a row = 1/2 x 1/2 x 1/2 x ... =
That both happen has a probability 1/32 x 0 = 0
This is true for any number the row might encode:
Probability row one encodes any number
= Probability row one encodes 0 + probability row one encodes 1 +
probability row 1 encodes 2 + ...
= 0 + 0 + 0 + ... = 0
Therefore the probability that row one encodes no number = 1.
A similar calculation gives the same result for each of the other rows.
Finally, the probability that no row encodes a number
= probability that row one encodes no number
x probability that row two encodes no number
x probability that row three encodes no
number
x ...
= 1 x 1 x 1 x 1 x ... =1
That is we have for the operation of the machine:
Probability(outcome 1) = probability(outcome
2) = ... = 0
Probability(no definite outcome number chosen) = 1
Once again, the infinite lottery machine succeeds
in returning a result with probability zero.
Here is another attempt that uses a different sort of probabilistic randomizer. The system consists of a pointer that can spin freely around a dial. It is so designed that it will come to rest with a uniform probability distribution around the dial. We might label the positions of the pointer with the angles 0 to 360 degrees. It will be more convenient, however, to relabel the angular positions so that the full range just goes from zero to one.
If we spin the pointer, it will come to rest on some number in the interval 0 to 1. This is not yet an implementation of an infinite lottery machine since the possible outcomes are drawn from the uncountably infinite set of the real numbers in the interval from 0 to 1.
Some modification is needed. One is to spin the pointer repeatedly until it comes to rest on a rational number, such as 1/2 or 3511/4157. We can map the rational numbers one-one to the natural numbers, 1, 2,, 3, ..., as we say in an earlier chapter. This mapping allows us to use the result as a selection of a natural number. We have an infinite lottery machine.
The problem with this newest scheme is now familiar. The rational numbers form a countably infinite, measure zero set among the uncountably infinite set of real numbers. Thus we have for any spin of pointer:
Probability(outcome 1) = probability(outcome
2) = ... = 0
Probability(no definite outcome number chosen) = 1
On each spin, the pointer-on-a-dial will return a result with probability zero. Repeated spins of the dial will not improve the chances of success. The probability that no result is returned remains one, even if we spin the pointer a countable infinity of times in a supertask.
We have now seen a sequence of attempts to build an infinite lottery machine with ordinary probabilistic randomizers. None has succeeded. The design may fail to meet the specification. If the design is able to choose natural numbers, it does so in an unhelpful way: the probability of each number is zero and the probability that any number at all is returned is also zero.
In retrospect, these problems were inevitable. That this is so follows if we list the properties that an infinite lottery machine system must have if it is composed of ordinary probabilistic randomizers. There are two:
I. The outcome space of probabilistic
randomizers used to host an infinite lottery machine is countably
additive.
II. An infinite lottery machine is implemented in this space by
identifying a countable infinity of outcomes with equal chance properties.
How might this countable infinity of outcomes be realized? Call them Outcome1, Outcome2, ... The simplest way is to identify a countable infinity of outcomes of equal probability so that
P(Outcome1) = P(Outcome2) = P(outcome3) = ... = ε
With such a set, we run into a familiar problem.
If ε > 0, we contradict the unit norm of countably additive probability measure. For then we have:
P(Outcome1) + P(Outcome2) + P(outcome3) + ... = ∞ x ε = ∞
This contradiction precludes systems with ε > 0.
If ε = 0, we run into a different problem. For we now have:
Probability(any one of Outcome1, Outcome2, ...
obtains)
= P(Outcome1) + P(Outcome2) + P(Outcome3) + ...
= 0 + 0 + 0 + ... = 0
That is, the outcomes corresponding to number selections in the infinite lottery occupy a tiny part of the randomizer outcome space. It is a space of probability zero. That means that that the infinite lottery machine will only successfully return a number with probability zero.
This last result now explains why all our efforts so far have failed to produce a functioning infinite lottery machine. In each case, if we had a sufficiently well specified mechanism, we found it would deliver its result only with probability zero. We can now see that this unhappy behavior was not due to a lack of design imagination in our part. The failure was inevitable.
There is an escape from these last problems. It will not ultimately save the project of constructing an infinite lottery machine from ordinary probabilistic randomizers. However its failure is interesting in drawing out some of the ideas of earlier chapters.
We can partition the randomizer outcome space into a countable infinity of subsets, numbered 1, 2, 3, 4, ..., in such a way that each has equal chance properties. This is done by ensuring that the partition is implemented symmetrically with respect to the probabilistic properties of the outcome space.
A partition is exhaustive. That means that there are no further outcomes outside of its subsets. It follows that one of the partitions must be chosen when the randomizers operate. So a number must be selected. This much is promising.
Now comes some trouble. The subsets provided by the partition must be probabilistically non-measurable. That is, the probability measure of the randomizer space can assign no probability to them.
It must be so. Otherwise
they would either have to each be assigned probability:
ε > 0 then unit normalization is
violated, as above;
or
ε = 0 then the probability of
successful operation is zero, as above.
We have seen probabilistically non-measurable sets in an earlier chapter. We can assume that they exist on the authority of the axiom of choice of ZFC set theory. That means that we can, after all, use probabilistic randomizers to build an infinite lottery machine from ordinary probabilistic randomizers.
There is a catch. And it is a big one. Notoriously,
as we saw with the Banach-Tarski
paradox, ZFC set theory gives us no means for constructing these
non-measurable sets.
This fact--that we have no means of constructing non-measurable sets in ZFC set theory is fatal for our purposes. It means that there is no formula that tells us which of the infinitely many subsets in the outcome space corresponds to each of the infinite lottery outcomes, 1, 2, 3, ...
This result is maddening. The machine can run and produce a result. But we cannot know which that result is because we have no means to read the result.
The issues just raised are rather abstractly presented. That is especially so for the non-constructibility of the non-measurable outcomes. Let us work quickly through an example that will help make matters a little more concrete.
What would it take to upgrade the pointer on a dial system to become an infinite lottery machine? We need to partition the dial outcome space into a countable infinity of subsets, where each has the same chance properties.
Natural ways of seeking this partition fail. The simplest approach is to divide the outcome space of the real numbers from 0 to 1 into a large number of equal sized intervals. For example, here we have divided space into ten intervals.
| 0-0.1 |
0.1-0.2 |
0.2-0.3 |
0.3-0.4 |
0.4-0.5 |
0.5-0.6 |
0.6-0.7 |
0.7-0.8 |
0.8-0.9 |
0.9-1 |
We can continue this division into 100, 1000 and more equal sized intervals. However what happens when we "take the limit to infinity" is rather unclear. We end up with an infinity of zero-sized intervals, such as the interval from 0.5 to 0.5. Such intervals are either empty or contain just one number, such as 0.5 in the last example. Whatever we have here, this limit is not the division of the outcome space into a countable infinity of subsets.
It turns out that there is a more sophisticated way of partitioning the space and it does lead us to a countable infinity of subsets, such that each has the same chance properties. These are the Vitali sets. They are, of course, non-measurable and all we can assure is their existence.
Here is the briefest sketch of how they arise:
First, we can divide the real numbers into an uncountably infinite number of subsets, each of countably infinite size. They are represented by the rectangles in the figure. There is an uncountable infinity of these rectangles. Each rectangle corresponds to a countable infinity of real numbers.
Second, we select one real number from each set. That it is possible to form a new set by doing this is assured by the axiom of choice.
Third, we form a duplicate of the set formed in the second step by adding a fixed rational number to each member of the set.
Fourth, we repeat for all rational numbers in the interval 0 to 1.
What results is a countable
infinity of Vitali sets that partitions the outcome space. Since
each set was produced from the first by an addition operation, it relates
to the uniform probability distribution in the same way. That does not
mean that the sets have equal probability, for Vitali sets are
non-measurable. It does mean that whatever chance properties that first
Vitali set has are shared by all the rest. They are equal chance outcomes.
With these Vitali sets, we now have an infinite lottery machine realized using the spinning pointer. We spin the pointer and it will come to rest in one of the countable infinity of Vitali sets that, we imagine, encodes the different natural numbers 1, 2, 3, ... The trouble, of course, is that we only know that these Vitali sets exist. But we cannot specify which of the infinity of subsets possible are these Vitali sets. The machine works, but we cannot read the result.
This failure of specification arises in the second step above. We form the first Vitali set by selecting one number from each of the uncountable infinity of sets arising in the first step. That such a set exists is assured by the axiom of choice. However that axiom gives us no means to specify which that set is.
It is natural at this moment to seek ways to specify which numbers are chosen in this first step. What if we choose the smallest number in each set? That fails since there is no assurance that each set has a smallest number.
For example, the set {1, 1/2, 1/4, 1/8, ...} has no smallest element.
What if we choose suitably defined average of each set? Again, there is no assurance that the arithmetic average is in the set.
For example the set {0.2, 0.4, 0.6, 0.8} does not contain its arithmetic average 0.5.
We could continue in this vein for a long time. The
result will always be the same. No simple formula
can specify which numbers are to be chosen in forming the Vitali set of
the second step above.
The prospects for an idealized infinite lottery machine are dim, if we seek to build it from ordinary probabilistic randomizers. If we are willing to entertain other sorts of stochastic processes, then matters become considerably easier. The measurement process of quantum mechanics is a stochastic process that is quite hospitable to an infinite lottery machine.
A quantum particle with a definite momentum has a completely indefinite position. It is represented by wave extending over all space, a "momentum eigenstate." Its one dimensional representation is something like this.
If we perform a position measurement on the particle, it undergoes a "collapse of the wave function" and is momentarily localized at just one point.
The chance of a collapse in some spatial region is proportional to the amplitude of the wave in this region (integrated over the region). The momentum eigenstate is distributed perfectly uniformly in space. Thus the chance of a collapse in any volume of space is proportional to the volume of the space.
Using this property of quantum measurement, we can build an infinite lottery machine by dividing space up into the equal volume cells shown. Each is equipped with a particle detector. We number the cells for convenience ..., -2, -1, 0, 1, 2, 3, .... When we perform a measurement operation on the wave, it will collapse into one of these cells and the particle detector in that cell only will be triggered. The number of that triggered detector is the selection of the infinite lottery machine.
We can, of course, renumber these outcomes to give us the more familiar outcomes 1, 2, 3, 4, ... The following renumbering would suffice:
0→1, 1→3, 2→5, 3→7, ..., -1→2, -2→4, -3→6, ...
An infinite lottery has chance properties that differ from normal probabilities. If building an infinite lottery machine is so difficult, should we take those alternative chance properties seriously?
August 23, 2021
Copyright, John D. Norton