Thursday, May 8, 2008

Consequences of Infinity

I read this recently on Pharyngula. It's an example of an argument I think is fallacious, but I've never seen anyone called on it.

If life is constant change and you are never the same person you were at any previous time, then if you lived forever, you would eventually become every possible person there is.

I've seen the same argument used as proof that there must be intelligent aliens somewhere if time/space is infinite. Consider a similar argument phrased in terms of integers.

There are an infinite number of integers. If I randomly pick an integer an infinite number of times, I must eventually pick '2'.

This sounds plausible, but it would be possible to randomly only pick odd numbers forever, which would clearly not produce a '2'. There are an infinite number of odd numbers, and even the same infinity as there are integers, but let's not go there.

So, is this a fallacy? What is it called?


Etha Jean Williams said...

I don't know if this fallacy has a name, but the mistake is that it assumes that p(n)>0 (where n is an integer). In actuality, p(n)=0. This conclusion can be arrived at fairly easily:

We know that the sum of probabilities for each integer must equal 1. We also know that the selection process is random, ie, that for any two integers n,m p(n)=p(m)=p. So we can rewrite the sum as a product p*x=1, where x is the amount of choices (integers in this case). We can then rewrite this as p=1/x.

There are an infinite amount of integers, so we take the limit as x tends towards infinity:

lim(x-->infinity)1/x = 0
So p-->0 as x-->infinity.

Thus for any integers p(n)=0, and so p(2)=0.

This is one of the bizarrities of probability -- you can have p=0 without an event being impossible. All that p=0 means is that it will not necessarily ever happen. (This is the same with continuous bounded functions; the probability of any given value is 0, but the integral of the probability distribution is 1.)

I don't know if this is what you were looking may have already known this and just wanted a name for the fallacy...but in any case, there you have it.

((BTW, I interpreted the Pharyngula argument as assuming that there were only a finite number of possible people, and thought this was a rather silly assumption...but you are probably right; it was probably someone playing with a faulty conception of probabilities in infinite sets.)

Hematite said...

I've been meaning to give your comment a proper treatment but I keep putting it off because I wanted to do some research first. I'm not getting very far with that so I'll bite the bullet and post something.

I've always been deeply suspicious of the assertion that 1/∞ = 0, mostly on the grounds that infinity breaks arithmetic pretty badly, ∞ - ∞ ≠ 0 for example, depending on how you feel like butchering the arithmetic operations when you allow infinity as a number. But that's just a gut feeling I wanted to check up on before I mentioned limits. My math is pretty much all learned from a Computer Science perspective, and that was a good five years ago so my jargon is extremely rusty.

My original argument was based on my knowledge of cardinality from a class on theory of computing. I really enjoyed learning about cardinality. Did you know that there are the same infinity of natural numbers and prime numbers, but a larger infinity of real numbers? Contemplating facts like that really helps me hear the call of the Elder Gods. Cthulhu fhtagn and all that.

Anyhow, you're quite right that I interpreted the original statement as referring to an infinite number of possible people. I usually try to pick the most sympathetic reading of other people's statements, which I may not have done in this case. That's also the reason I didn't reference the quote; I wanted to discuss a particular interpretation without it reflecting on the author of the statement*.

The original intent of the statement was to say that if life was eternal, and life could only be said to exist when change can occur, then eventually a person (PZ) would change to become every other person (for example Ben Stein) at some point - a fate worse than oblivion! I quite liked the sentiment, and didn't want to pick on it specifically.

To get a bit (but not much) more technical, for the statement I quoted in the original post to be true we would have to assume that there are a finite number of possible people, and also that each person can only be picked once.

The set of possible people must be finite because otherwise the select-next-person function could just keep picking 'other' people, not the one we are interested in.

Each person may only be picked once because otherwise the select-next-person function might just enter a loop of always selecting from some subset of the set of possible people - a subset which did not contain the person we are interested in.

Incidentally, once we make these assumptions we don't need to select an infinite number of people anymore; for a set of n possible people and selection without replacement each person must be selected after n selections.

It would be a good exercise for me to formalise this argument, but I'm beginning to despair of ever resolving anything I post; I come up with questions far more quickly than I can formalise them, let alone answer them.

A proof would start off something like:

Assume an infinite set P, a target element tP and a selection function ƒ...

*For the record, I think the statement was by 'Dave'. Or possibly 'Mike'. Not much chance of ruining a carefully cultivated reputation there.

Daniel R said...

I don't know how to pick a random value in an infinite set. In a finite set, ok, I can provide an algorithm, but not in an infinite set. How do you get your "random integer"?

Daniel R said...

I mean, to produce one only random integer, you need an infinite time.

Hematite said...

Daniel R, good point. I was talking about picking from an infinite set, but I was thinking about transitioning between states in an infinite set. I think there's no problem with each state having an associated (finite) list of states it can transition to, and every state in the infinite set being reachable after some number of transitions.

For example, starting from 0 in the natural numbers and using the function (x+1) to determine the next state to transition to, all natural numbers will be reached eventually.

Although... thinking about picking a random number from an infinite set... is it a problem if picking any particular number takes an arbitrarily long time to be selected if we have infinite time? I think any function like that would have to assign unequal probabilities to different numbers though. efrique just said something to that effect on Pharyngula. A selection function which started from 0 and then either selected the current number, or moved to n+1 50% of the time should pick any natural number, but not with equal probability.

Thank you, I shall consider this further...

Daniel R said...

Yes, if you assign unequal probabilities to numbers, it is possible to make a random function returning in finite time, no problem
(in practice, let's say).

BTW Etha is wrong saying (in Pharyngula) "Something that happens 1/n times (where n is a very big number) still happens".

Mathematically, yes, but knowing that the universe is 12 billion years old, if some probability of some event results that we have to wait for trillions trillion trillion trillion trillion years to have a reasonable chance to see it, we could consider in practice that it never happens.

But I am not sure I understand the initial question of this debate. What is the problem, since we are all atheists...? :-)

Hematite said...

Daniel, you're talking about this comment of Etha's?

When Etha said "Something that happens 1/n times (where n is a very big number) still happens", I read it to mean it may happen rather than being impossible, which is true.

If we are talking about some unlikely event which definitely has happened, such as the beginning of life on earth, it may be explained by the anthropic principle, although it is not a very satisfying explanation.

Daniel said: But I am not sure I understand the initial question of this debate. What is the problem, since we are all atheists...? :-)

This debate? Just a math question that interested me, nothing about religion :)

Daniel R said...

Yes, it was that Etha's comment. I found it from the link you gave in your previous post, looking above the pointed text to try to understand the context.

Ok for the explanation: I did not get the nuance, English not being my mother tongue.

I don't like that "anthropic principle" much, it sound as "destiny".

For the beginning of life, well, we don't know for the moment, but I am sure that Science will find explanations in the future, little by little.

But explanations like "it must be like that, otherwise we would not be here to consider it" (as I understand the "anthropic principle") are not satisfactory, according to me... it is a recursive logic, just like "god wrote the bible in which he says he exists, therefore he exists".

Efrique said...

Hematite invited me over from the Pharyngula thread.

Consider a similar argument phrased in terms of integers.

There are an infinite number of integers. If I randomly pick an integer an infinite number of times, I must eventually pick '2'.

For starters, there's a potential problem with what you mean by "randomly". If you mean "equally likely and at random" then you can't do it.

It is simply not possible to select an integer at random where each one has the same probability of being chosen.

This sounds plausible, but it would be possible to randomly only pick odd numbers forever, which would clearly not produce a '2'.

You have to be careful. Let's assume you put a distribution over the integers (but not one where they're all equally likely). Assume for the same of argument that the probability that an odd number is selected on any one trial is p. Then the probability that in k trials they're all odd is p^k.

lim p^k = 0

That is, the probability is in the limit zero.

(If the probability that 2 comes up on one trial is finite, then it will certainly come up - and an infinite number of times).

There are an infinite number of odd numbers, and even the same infinity as there are integers, but let's not go there.

Yes, but there are also twice as many odd numbers as even numbers. And half as many. And...

Efrique said...

(If the probability that 2 comes up on one trial is finite, then it will certainly come up - and an infinite number of times).

Except, of course, for an event of measure zero ... as always; "certainly" is meant there in the ordinary sense of the word.

Efrique said...

To be more precise: in order to be able to construct something which could have a uniform distribution over a countably infinite set, you'd have to drop Kolmogorov's axiom of countable additivity.

Such a thing is possible to do, but when people deal with countably infinite sample spaces they do use it, so whatever "probability" you end up with by dropping it will not be like the probability that has been developed.

In measure theory terms, it's usually put something like:
The union of a countable number of measurable sets cannot have measure 1 with all the sets having equal measure.

Which means (if we talk about the thing we normally talk about when we discuss probability) you either have to give up probabilities adding to 1, or you give up equal probability on your countably infinite set.

A probabilist (and facist, as it happens, but that has nothing to do with whether his work was any good) called de Finetti claimed it was possible to have a notion that was effectively a uniform distribution over a countably infinite set by dropping the aforementioned axiom.

That is, in effect, he dropped the "probabilities add to 1" part that would otherwise be a consequence of the axiom.

In effect, he adopted Etha's approach of saying each probability was zero. The uncomfortable consequence is that the probability that *some* number is chosen is not 1 but 0.

Other probabilists have tried making each probability > 0. The uncomfortable consequence there is that of course, the probability that *some* number is chosen becomes infinite.

No actual mechanism for producing a random number from these constructs exists. Any process that gives you a number will be inevitably weighted toward the small numbers (give small numbers generally higher probability than sufficiently large numbers).

Consequently, if you're only using such a construct to represent something like a state of knowledge, and not actually requiring to be able to actually observe a value from it, it is sometimes possible to work with such things. That's the sort of thing that's effectively being done when Bayesians work with flat priors over the positive integers (they refer to things like that as "improper priors") - with appropriate normalization, you can get proper posteriors to come out the other end.

A lot of people object to this kind of thing, insisting that subjective probability and actual realizable probability ought to have the same features. They also like to point to the paradoxes that come along with not doing so.

Anyway, the short version of all that is "You can't actually select an element from a countablly infinite set with equal probability on all elements."

[Indeed, it's stronger than that. For example, not only does the probability need to generally decrease as the values become arbitrarily large, it can't decrease too slowly. For example, it can't decrease at a rate proportional to 1/k (though of course, a finite number of values need not be required to follow the general decrease).]

Efrique said...

Maybe I should post all that on my blog sometime. Indeed, I've long wanted a maths blog; maybe I'll start one.

Etha Jean Williams said...

Very interesting stuff re: the difficulties trying to choose a random element from an infinite set -- I hadn't thought of it that way. (To be honest, most of my knowledge on this is coming off of an informal half-proof my stats prof gave before saying "the rest of the proof is left as an exercise to the student.") But these arguments make a lot of sense (to the extent that anything infinite really makes sense to me; I've always found infinity a very difficult -- okay, really impossible -- concept to totally wrap my head around). Anyway, thanks for the interesting mathematical info.

Hematite said...

Efrique, thank you for your comments! I've been out of university for a few years now, and it's a wonderful and nostalgic feeling whenever I come across somebody who knows more than I do about a subject I am interested in.

I see you have posted this on your blog, I will watch eagerly for further mathsy posts!

Efrique said...

Hi Etha. It's not hard to choose a random element from an infinite set; you just have to do it with unequal probability.

Hematite - there are some good mathematics blogs aboutmeany of them have a good dose of chatty or recreational posts (which suits me because usually my brain isn't up to much).

There are even a couple of mathematics blogs by atheists (but they usually don't talk about their lack of belief much on their maths blogs).