Tuesday, May 13, 2008

Selecting a random uniform positive integer

This post is edited together from some comments arising out of comments at Pharyngula, where some commenters were discussing randomly selecting a positive integer (with equal probability on every positive integer), in a discussion of creationists abuse of mathematics.

The problem is, you can't do it.

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

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 the axiom, so whatever "probability" you end up with by dropping it will not be like the probability that people use.

(In measure theory terms, it would be put something like: The union of a countable number of measurable sets cannot have measure 1 with all the sets having equal measure.)

What does that mean? It means you either have to give up probabilities adding to 1, or you have to give up equal probability on your countably infinite set.

A probabilist called de Finetti (and facist, as it happens, but that has nothing to do with whether his work was any good) 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 said 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 somewhat unintuitive 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).

Now, 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.

** Some people regard the uniform over the positive integers as representing a complete lack of knowledge, but to my mind it actually represents the dramatically strong assumption that no matter how large a value you consider, you effectively assume that essentially all values are larger than it.

A fair number of people object to this unsual kind of construct, 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, with which I am not presently sufficiently familiar to discuss right now.

Anyway, the short version of all that is "You can't actually select an element from a countably infinite set (such as the positive integers, all the integers, the rationals, or the differences of the square roots of non-negative integers) 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, the probability can't decrease very slowly. For example, it can't even decrease at a rate proportional to 1/k -- though a finite number of values need not be required to follow the general decrease.


The Barefoot Bum said...

OK, your conclusion seems plausible and well substantiated. What are the consequences?

Efrique said...

Well, for starters, any of the arguments that were made based on choosing a random integer are either going to have to be abandoned or changed so that they're not based on an invalid premise.

I don't particularly see it as my job to make other people's arguments for them, but I'm happy to help them identify when they go wrong.

The Barefoot Bum said...

[A]ny of the arguments that were made based on choosing a random integer are either going to have to be abandoned or changed...

Agreed. Are there any interesting or surprising positive consequences?

Efrique said...

Hmm. I posted a longer reply before but it seems to have got lost in the aether.

I am afriad we're probably failing to communicate. There are an infinite number of potential consequences depending on what circumstance you try to do random selection in. Did you have a particular situation in mind?

It's not that I am trying to be difficult. It's a bit like someone saying "I have in my hand a list of all of the prime numbers" and someone else replying "well, no, you can't, because I can prove there are an infinite number of them."

Or a bit like someone saying "Obama said he was in favour of a gas tax holiday" and then someone else coming back with an actual quote. I could ask them for the consequences of the actual quote, but it's kind of difficult to answer that without some context, because there are many different kinds of potential consequences. I might be interested in the political consequences for Obama, I might be interested in the economic consequences of having or not having the GTH, I might be interested in the consequences for the original argument that was being made, and so on.

It's difficult to give a useful answer to a simple contradiction of a claim without some idea of what kind of consequences you're interested in.

[For me, the prime consequence of my post is that next time I want to refute a claim that you can do it is to point back here rather than try to retype it all...]

The Barefoot Bum said...

Why do you think we're failing to communicate?

I read the links you supplied, and I agree you've pretty much refuted the relevant arguments.

I assume you're a mathematician, or at least have more mathematical training than I do. This seems like an interesting point that I don't have the experience and training to properly explore; I'm simply wondering if you have. If you haven't, if it's not really a good starting point for interesting consequences, then it's not. I won't feel bad.

Anonymous said...

So why is it that you can have a uniform probability distribution over, say, the real unit interval [0, 1] but not over any countably infinite set? This seems quite paradoxical to my mind--why [0, 1] but not the set of all rationals between 0 and 1? What is it about countability that makes this true? (Please correct me if I'm wrong about the unit interval.)

I know some very, very basic probablity, but almost nothing about the underlying measure theory

Efrique said...

Hi intrinsicallyknotted! Thanks for coming by.

This is the fourth time I have attempted to post an answer. It keeps getting lost in the ether. So my previous long answers are going to be replaced with something shorter this time.

I'm not sure this satisfactorily answers your question; we may have to iterate a little to get to the meat of it.

You don't need measure theory to discuss the basics.

There are a couple of important things to note about the major practical difference between discrete and continuous random variables (measure theory unites them both under a single framework, and can deal with mixtures of the two as well as a number of rather esoteric cases that are very tricky without it, all of which we can ignore for the present reply, though I suspect we may have to ultimately if this reply doesn't satisfy).

With a discrete random variable, single points carry probability. With a continuous random variable, only intervals do. In the first case, an event like "(X=1)" will have a nonzero probability, while in the second case only an event like "(s < X < t)" will. Think of integrating a continuous function; you can talk about the integral between two values, but the integral at a given point is always zero.

In the discrete case, a probability of being in some interval will come from a sum, and in the continuous case (certainly for all the straightforward examples), you can write the probability of being in an interval as a Riemann sum. As long as the total measure (total probability) is 1, everything works in both cases.

Now you can map the discrete probabilities on the positive integers to rationals or any other countable set; it doesn't matter how close together they are, because you can just put them in a 1-1 correspondence.

It's tricky to construct a direct continuous analog to that - the continuous uniform isn't an analog of the situation (what proportion of rationals in (0,1) are smaller than 0.5?).

However, the problem with the discrete case has a continuous analog. Try to put uniform probability on the positive real half-line. Now, depending on how you try to do it, your integral either converges to 0 or it doesn't have a limit at all, so your total probability can't be 1. You can't generate a continuous value uniformly there, any more than you can on the positive integers.

As it turns out, generating (selecting) an element from a continuous random variable even on a finite interval is also problematic. You can't actually do it in finite time. What you do in practice is generate from some a discrete approximation to it - so at least we can get as close as we need to there, even if we never actually do it (this relates to my point in the original Pharyngula thread relating to the part about dartboards).

Does any of that help?

Adam McD said...

You mentioned that dropping the 1st or 3rd axioms would allow one to get around the problem. Changing the 3rd axiom to 'finite additivity' seems like it would possibly lead to some interesting results -- do you know where or who I could look to in order to find out more about this?

Anonymous said...

Who knows where to download XRumer 5.0 Palladium?
Help, please. All recommend this program to effectively advertise on the Internet, this is the best program!