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:
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
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.
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?
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.
|#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|
The probability that 1 will not be removed after, say four steps, is the product of four probabilities:
|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,
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 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.
A divergent infinite product, even when it is divergent to 0, behaves in ways that justify the terminology. As with divergent series, some operations that make appear natural make no sense (and are not applicable) to the infinite products. For example, the product
as we just saw, diverges to zero. Observe now that, starting with the second fraction, the numerator of a term coincides with the denominator of the previous fraction, which appears to suggest that the two numbers can be cancelled out. But, if we do carry out the cancellations, the only number that will remain is the numerator of the very first term - 1! Certainly different from 0.
- 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.