Infinity and Probability
When it comes to counting, there is a gap between finite and infinite. Two sets are equivalent or, which is the same, have the same number of elements when there exists a 1-1 correspondence between their elements. To use a handy example, two hands have the same number of fingers (5) because to each finger on one hand their correspond exactly one finger on the other, and vice versa. The notion of equivalence and 1-1 correspondence equally apply to sets finite and infinite. What sets the finite and infinite sets apart is that infinite sets are equivalent to their own subsets which may never happen with finite sets however large. Galileo Galilei had already realized that the set of all natural numbers is naturally placed into a 1-1 correspondence with their own squares:
| |
| 1 | | 2 | | 3 | | 4 | | 5 | | 6 | | 7 |
| | 1 | | 4 | | 9 | | 16 | | 25 | | 36 | | 49 |
Hence, with their own subset. Galileo arrived at the conclusion that "the attributes 'equal', 'greater,' and 'less', are not applicable to infinite, but only to finite quantities." It was Georg Cantor who, more than 250 years later, adapted those attributes to the notion of infinite. The last sentence does not make justice to the difficulty with which Cantor's theory was eventually embraced by the mathematical community. Following is a passage by Bertrand Russell
| |
We can now understand why Zeno believed that Achilles cannot overtake the
tortoise and why as a matter of fact he can overtake it. We shall see that all the
people who disagreed with Zeno had no right to do so, because they all accepted
premises from which his conclusion followed. The argument is this: Let Achilles and
the tortoise start along a road at the same time, the tortoise (as is only fair) being
allowed a handicap. Let Achilles go twice as fast as the tortoise, or ten times or a
hundred times as fast. Then he will never reach the tortoise. For at every moment
the tortoise is somewhere and Achilles is somewhere; and neither is ever twice in the
same place while the race is going on. Thus the tortoise goes to just as many places
as Achilles does, because each is in one place at one moment, and in another at any
other moment. But if Achilles were to catch up with the tortoise, the places where
the tortoise would have been would be only part of the places where Achilles would
have been. Here, we must suppose, Zeno appealed to the maxim that the whole has more terms than the part. Thus if Achilles were to overtake the tortoise, he would
have been in more places than the tortoise; but we saw that he must, in any period,
be in exactly as many places as the tortoise. Hence we infer that he can never catch
the tortoise. This argument is strictly correct, if we allow the axiom that the whole
has more terms than the part. As the conclusion is absurd, the axiom must be
rejected, and then all goes well. But there is no good word to be said for the
philosophers of the past two thousand years and more, who have all allowed the
axiom and denied the conclusion.
The retention of this axiom leads to absolute contradictions, while its rejection
leads only to oddities. Some of these oddities, it must be confessed, are very odd.
One of them, which I call the paradox of Tristram Shandy, is the converse of the
Achilles, and shows that the tortoise, if you give him time, will go just as far as
Achilles. Tristram Shandy, as we know, employed two years in chronicling the first
two days of his life, and lamented that, at this rate, material would accumulate faster
than he could deal with it, so that, as years went by, he would be farther and farther
from the end of his history. Now I maintain that, if he had lived for ever, and had
not wearied of his task, then, even if his life had continued as eventfully as it began,
no part of his biography would have remained unwritten. For consider: the
hundredth day will be described in the hundredth year, the thousandth in the
thousandth year, and so on. Whatever day we may choose as so far on that he
cannot hope to reach it, that day will be described in the corresponding year. Thus
any day that may be mentioned will be written up sooner or later, and therefore no
part of the biography will remain permanently unwritten. This paradoxical but
perfectly true proposition depends upon the fact that the number of days in all time
is no greater than the number of years.
|
Roger C. Evans gave a fanciful rendition of the paradox of Tristram Shandy which, I understand, he came across in a book on probability [S. Ross].
| |
The scene: ... at faster and faster pace, since one minute to midnight,
Genie and Jenny have each been receiving from on high -- into two
identical urns of limitless capacity -- identical sets of golden balls,
each ball engraved with one of the natural whole numbers: 1, 2, 3, ...
etc. These are being sequenced according to a precise schedule, each urn
receiving:
balls " 1" to "10" at 1 minute to midnight;
balls "11" to "20" at 1/2 minute to midnight;
balls "21" to "30" at 1/4 minute to midnight; etc.
Each ball is exchangeable (consumable in the twinkling of an eye so to
speak) for any single pure-hearted wish, and Jenny and Genie have been
enjoined to so exchange one or more of the balls present in their
respective urns immediately upon receipt of each set of ten-balls.
They've each been warned: "CHOOSE WISELY, for the content of your urn
shall become your sole future estate at midnight, when you shall pass
into the great eternal beyond!"
It is hard to understand the sequel: Jenny and Genie each exchanged a
single ball at each wishing time, retaining a net nine-ball gain in
their respective urns; they each relinquished present gluttony in hopes
of a perfect future. Their actions seemed equally circumspect, for they
might have been perceived as twins in lockstep, receiving ten new balls
(and gaining nine) in exact synchrony: after the Nth gain their separate
urns each contained 9N balls ... right up to the fateful hour! How can
one understand the awful outcome?
Genie arrived at the stroke of midnight with an urn infinitely laden,
having exchanged balls 10, 20, 30, ...etc. for wishes -- i.e. he gave up
his highest-numbered ball present at each wish-time and thus retained
all non-multiples of 10. But Jenny, alas, exercised a low-number appetite and exchanged
least-numbered balls: she disposed of balls 1, 2, 3, ... etc. in that
order -- and stripped her urn of every ball it might otherwise have
retained! She crossed over empty-urned at the fateful hour.
|
Note 1:
The probability question was this: if the choice of each sacrificed ball-number is random (with all present numbers being equally likely), what's the probability, p, of there being an empty urn at midnight?
Answer: p = 1 !
Note 2:
Perhaps Jenny escaped a hideous fate by trading each ball cleverly: for a wish to perceive her next between-gift time-span in a subjective time-scale of her own devising. She may thus have enjoyed an unending sequence of "lifetimes" (with some extra wished-for wishes perhaps?) and so have removed her awareness from the possibility of any after-midnight experience.
Let's pose our question a little differently: at discrete intervals, consecutive integers are added to a given set and immediately after that one element is removed from the set. Selection of the element is uniformly random over the whole set. The first time, numbers 1, 2, ..., a were thrown in. Then it was a turn for a+1, a+2, ..., 2a, and so on. What is the probability that, say number 1 will be eventually removed? The answer is that number 1 will be removed with the probability p equal to 1. The original problem corresponds to a = 10.
It's perhaps easier to find the probability Q that number 1 will stay in the set forever. We have to show that Q = 0.
| |
Step | 1 | 2 | 3 | 4 | 5 |
|---|
| |
#elements after the set was augmented | a | 2a-1 | 3a-2 | 4a-3 | 5a-4 |
|---|
| |
#elements after an element was removed | a-1 | 2a-2 | 3a-3 | 4a-4 | 5a-5 |
|---|
| |
Probability of not selecting a particular element | (a-1)/a | (2a-2)/(2a-1) | (3a-3)/(3a-2) | (4a-4)/(4a-3) | (5a-5)/(5a-4) |
|---|
The probability that 1 will not be removed after, say four steps, is the product of four probabilities: (a-1)/a· (2a-2)/(2a-1)·(3a-3)/(3a-2)·(4a-4)/(4a-3). The probability that 1 will never be removed appears to be a product of an infinite number of terms. Infinite products are as legitimate objects of math study as are infinite sums - series. As infinite sums, infinite products may either converge or diverge. For products, convergence takes an interesting twist: the product must have a limit which ought to be finite and different from 0. There are several explanations why a product with the limit equal to 0 is still judged divergent. If one of the terms in the product is 0, so will be the whole product - the case is trivial and not interesting(*). There is nothing similar to that case in the theory of infinite sums. However, the two are related by the following statement:
| |
Assume the terms am of an infinite product Πam are such that all vm = am - 1 have the same sign. Then the product Πam is convergent iff so is the sum of Σvm.
|
|---|
Returning to our problem, (a-1)/a = 1 - 1/a, (2a-2)/(2a-1) = 1 - 1/(2a-1), (3a-3)/(3a-2) = 1 - 1/(3a-2), (4a-4)/(4a-3) = 1 - 1/(4a-3), and so on. We may surmise that vm = 1/(ma - m + 1). (Note that a is constant.) The series Σvm compares with the harmonic series Σ1/m which is known to diverge (the proof is not difficult and I plan to return to it at a later date.) Thus the series Σvm is always (for any a) divergent, and so then is the product Πam. With a = 2 the situation is rather simple. Consecutive probabilities become: 1/2, 2/3, 3/4, ... so that the product of m terms is just 1/(m+1) which tends to 0.
In the general case, all terms am are less than 1. Multiplying more and more terms we obviously get a decreasing sequence whose limit, as it follows from the statement above, is 0. The product is, by definition, divergent. But that's OK. All we needed to solve our problem was to get the limit 0.
Note 3
Note however that this result does not preclude the possibility that by midnight the set will not be empty even though the probability of this happening is 0.
References
- S. Ross, A First Course in Probability, Prentice-Hall, 1997, 5th ed.
- R. Rucker, Infinity and the Mind, Princeton University Press, 1995
- B. Russell, Mathematics and the Metaphysics, in J. R. Newman, The World of Mathematics, Dover Publications, 2003
(*)
David Cantrell reminded me in a private correspondence that some people think otherwise. Not every one subscribes to the above definition. Sometimes a finite number of terms is allowed to be 0, in which case, regardless of the actual values of the (infinitely many) remaining non-zero terms, the product is zero. Of interest then is the product obtained by supressing all the zero terms. This product may be either convergent or divergent according to our original definition. In the former case, the whole product is said to converge to 0, while in the latter case it is said to diverge to 0.
Copyright © 1996-2008 Alexander Bogomolny
|
