Friday, September 25, 2009

A puzzle about uniform probabilities on infinite sets

This puzzle is inspired by a reflection on (a) a talk [PDF] by John Norton, and (b) the problem of finding probability measures on multiverses. It is very, very similar—quite likely equivalent—to an example [PDF] discussed by John Norton. Suppose you are one of infinitely many blindfolded people. Suppose that the natural numbers are written on the hats of the people, a different number for each person, with every natural number being on some person's hat. How likely is it that the number on your hat is divisible by three?

The obvious answer is: 1/3. But Norton's discussion of neutral evidence suggests that this obvious answer is mistaken. And here is one way to motivate the idea that the answer is mistaken. Suppose I further tell you this. Each person also have a number on her scarf, a different number for each person, with every natural number being on some person's scarf. Moreover, the following is true: the number on x's scarf is divisible by three if and only if the number on x's hat is not divisible by three. (Thus, you can have 3 on your scarf and 17 on your hat, but not 16 on your scarf and 22 on your hat.) This can be done, since the cardinality of numbers divisible by three equals the cardinality of numbers not divisible by three.

If you apply the earlier hat reasoning to the scarf numbers, it seems you conclude that the likelihood that the number on your scarf is divisible by three is 1/3. But this is incompatible with the conclusion from the hat reasoning, since if the likelihood that the scarf number is divisible by three is 1/3, the likelihood that the hat number is divisible by three must be 2/3.

If there are numbers on hats and scarves as above, symmetry, it seems, dictates that the probability of your hat number being divisible by three is the same as the probability of your scarf number being divisible by three, and hence is equal to 1/2. But this conclusion seems wrong. For the numbers on scarves, even if anti-correlated with those on the hats, should not affect the probability of the hat number being divisible by three. Nor should it matter in what order the hat and scarf numbers were written—hats first, and then scarves done so as to ensure the right anti-correlation between divisibilities, or scarves first, and then hats. But if the hat numbers are written first, then surely the probability of divisibility by three is 1/3, and this should not change from the mere fact that scarf numbers are then written.

One of several conclusions might be drawn:

1. Actual infinities are impossible.
2. Uniform priors on infinite discrete sets make no sense.
3. Probabilities on infinite sets are very subtle, and do not follow the standard probability calculus, but there is a very intricate account of dependence such that whether the hat numbers are assigned first or the scarf numbers are assigned first actually affects the probabilities. I don't know if this can be done—but when I think about it, it seems to me that it might be possible. I seem to be seeing glimpses of this, though the fact that as of writing this (a couple of hours after my return from Oxford) I've been up for 21 hours may be affecting the reliability of my intuitions.

Heath White said...

Against #3, I would think it is (in some sense, at least as good a sense as the rest of the example) possible for both hat and scarf numbers to be assigned "from eternity" with neither depending on the other.

(Also, you can make the math easier, I think, if you just pick numbers, or pairs of numbers, at random, rather than use all the natural numbers.)

Alexander R Pruss said...

Heath:

Thanks for the parenthetical.

Not only would it make the math easier, but then we'd need only one person, and so #1 would no longer be at all helpful! So we don't have here any support for Kalaam arguments. :-( (It would be helpful if the space of possibilities always had to be finite. But that's surely false.)

So, the revised story is this. You have a natural number on your hat, which you can't see. Is it divisible by three? Initially you want to say: "Probably not." But then you find out you have a natural number on your scarf, which also you can't see, and you find out that the hat number is divisible by three iff the scarf number is not. And that's all you know.

Heath White said...

We could put the revised version this way:

You have a pair of numbers on your hat and scarf, neither of which you can see, but one of which is divisible by three and the other of which is not. Question: what is the chance that your hat number is divisible by three?

My intuitive answer, when it's described this way: Duh, 1/2.

Mike Almeida said...

Alex,

I'm not sure why the probability goes to 2/3. I'm sure I'm missing something important. Suppose there's a function that maps the naturals onto itself in such a way that no number divisible by 3 gets mapped onto another divisible by 3. Map every n onto n+1. Wouldn't it then be true that the chances that the hat has a number divided by 3 remains 1/3?

Alexander R Pruss said...

Heath:

But why does the fact that there are scarf numbers affect your probabilities of hat numbers?

Here is what I am now thinking--to ask what the probabilities are in these cases is to ask a question with a false presupposition. These are cases where the probability calculus is not applicable. That much is, I think, certain.

The challenge is coming up with an alternative to the probability calculus that works in infinitary cases. If you ask "Why bother?" the answer is that we can meaningfully reason probabilistically in some infinitary cases, but it's hard to come up with a general account of what we're doing. See tomorrow's post. :-)

Mike:

The function you give is one-to-one but not onto.

Mike Almeida said...

Alex,

Certainly some other function will satisfy your description. For all odd numbers m, map m to m+1, and for all even numbers n, map n to n-1. Anything along those lines will satisfy yor description, I think. And it seems pretty clear that the probability of having a hat number divisible by 3 is 1/3, not 2/3.

Alexander R Pruss said...

Mike:

I was assuming that the hat number is divisible by 3 iff the scarf number is not. Now, the same reasoning that says that the hat number's probability of being divisible by 3 is 1/3 says that the scarf number's probability of being divisible by 3 is 1/3, and hence that the hat number's probability of being divisible by 3 is 2/3.

Mike Almeida said...

Right. There's a mapping that satisfies that description, too, given the size of the sets. Oh, that's sorta nasty.

enigMan said...

The obvious answer would be 1/3 because one in every three natural numbers is divisible by three, when we run through the natural numbers in their natural ordering. So if I was one of infinitely many blindfolded people, and those people were being produced endlessly (e.g. sexually, in an eternal universe), and the numbers were assigned in the natural way (1, 2, 3, ...) then 1/3 would be the right answer (?)

enigMan said...

Suppose you are one of infinitely many blindfolded people. Suppose that the natural numbers are written on the hats of the people, a different number for each person, with every natural number being on some person's hat. How likely is it that the number on your hat is divisible by three?

So (from my previous comment), if the infinitely many people were being selected one after another in some eternal universe, and if the numbers were being assigned to them in their natural order, and if instead of the blindfolding (which suggests a spatial rather than a temporal collection) those people were just of a race of blind people, then the probability would be 1/3.

And for the numbers on the scarves, the probability of them not being divisible by 3 would therefore also be 1/3. I am therefore in some sympathy with Mike. I guess that we should think of Actual infinite collections as spatial collections? The thing is, it does seem odd to think that the number of people in such an eternal universe would not actually be infinite. The number would not be infinite at any particular time, but surely we can consider the universe as a spatio-temporal whole.

James said...

Alex: The revised story is this. You have a natural number on your hat, which you can't see. Is it divisible by three? Initially you want to say: "Probably not." But then you find out you have a natural number on your scarf, which also you can't see, and you find out that the hat number is divisible by three iff the scarf number is not. And that's all you know.

I haven't quite thought this through as yet. But isn't this revised version a bit like the Monty Hall problem (http://en.wikipedia.org/wiki/Monty_Hall_problem).

You say that

The same reasoning that says that the hat number's probability of being divisible by 3 is 1/3 says that the scarf number's probability of being divisible by 3 is 1/3,

But this is false, isn't it, since the scarf numbers couldn't have been picked at random, right? Think of it this way. Suppose I'm given a hat number generated by some random number generator. The chances of its being divisible by 3 are 1 in 3. Fine. Suppose I'm then told that I've been assigned a scarf number such that either the scarf number is divisible by 3 or the hat number is divisible by 3. Now, this scarf number can't have been generated by the same random number generator, right? (since, if it was, the relationship "Either (hat mod 3) = 0 or (scarf mod 3) = 0" wouldn't necessarily hold). So I know someone's picked a scarf number so satisfy some predetermined condition. But then the reasoning "There's a 1 in 3 chance that the scarf is divisible by 3" is clearly mistaken, isn't it?

(EIther that or I'm talking rubbish. It's late here (in England). Plus, I haven't eaten or slept for a while and am only on this blog because I'm taking a break from writing up some notes on St John's Revelation. So, if I'm not thinking straight, I have a number of decent excuses up my sleeve...)

Alexander R Pruss said...

It's almost certain that it is not the case that both the hat and the scarf numbers are picked at random and independently. ("Almost certain" = "Probability 1". Since zero probability events can happen, that's not the same as "necessary" or "certain".) You don't know which was picked first, or if both were picked by some single process, etc.

James said...

It's almost certain that it is not the case that both the hat and the scarf numbers are picked at random and independently.

In which case it's false to say that

the same reasoning that says that the hat number's probability of being divisible by 3 is 1/3 says that the scarf number's probability of being divisible by 3 is 1/3

isn't it?

Alexander R Pruss said...

Before you found out about the scarf numbers, you had no reason to think any hat number more likely than any other hat number, and that was what grounded the intuition that the answer was 1/3. But does finding out about the scarf numbers give you any reason to think any hat number more likely than any other hat number? If so, which one(s)?

Here's another way to see the problem, with just one set of numbers. Why are we tempted in the original case, with just a hat number, to say that the probability of divisibility by three is 1/3? It's something like this:
(*) "The natural numbers are: 1, 2, 3, 4, 5, 6, 7, 8, 9, ..., and every third one is divisible by three."

But consider this parallel reasoning:
(**) "The natural numbers are: 1, 3, 2, 6, 4, 9, 5, 12, 7, 15, 8, 18, ..., and every second one is divisible by three."

Now you might say that the ordering in (*) is more "natural" than the ordering in (**). But remember that we had no information about how the hat numbers were assigned, and that, intuitively, most orderings of the natural numbers are not "natural". Moreover (and this is John Norton's argument) the probability measure given no information should be invariant under permutations, and in particular, under the permutation that takes 1, 2, 3, 4, 5, 6, 7, 8, 9, ... to 1, 3, 2, 6, 4, 9, 5, 12, 7, 15, 8, 18, ....

James said...

Before you found out about the scarf numbers, you had no reason to think any hat number more likely than any other hat number, and that was what grounded the intuition that the answer was 1/3.

Right

But does finding out about the scarf numbers give you any reason to think any hat number more likely than any other hat number?

No. My claim is that the probability is still 1/3, and that the logic that makes it 2/3 is confused since the claim that the probability that the scarf number is divisible by 3 is 1/3 is incorrect. Am I missing something obvious?

Regarding your parallel example, this hinges on having infinite sets doesn't it? and I thought you'd dropped that in your revised version.

Alexander R Pruss said...

Well, your information about the hat and scarf numbers is perfectly symmetric, so if you say one is 1/3, you should say that so is the other.

Infinity is still there--there are infinitely many possible numbers.

James said...

But it doesn't seem to me as if my information is symmetric. When I'm told my hat has a natural number written on it, then as far as I know, it could have been assigned any old number. So, as far as I know the odds of it being divisible by 3 are 1/3. But once I'm told about the scarf-numbers and their relationship to the hat-numbers, I know that either the scarf-numbers have been selected to conform to the hat-numbers or vice-versa. If the former, then I know that the probability of the scarf-number being divisible by 3 isn't simply 1/3. If the latter, then I now know my original guess was based on an incorrect assumption (namely that the hat chosen could have been assigned any old number). Either way, there's an asymmetry there.

Alexander R Pruss said...

I don't actually think that the initial information should lead you to think the probability is 1/3. That's, perhaps, the point of the story.

In the modified story, you don't actually know that the scarf and hat numbers were chosen to conform to one another. All you know is that one is divisible by three iff the other is not. This is compatible with many stories: hat number first, then scarf; scarf first, then hat; hat and scarf chosen together using some procedure that ensures that there is this sort of dependency between them; hat and scarf chosen independently, and in this case by chance happening to have the property that one is divisible by three iff the other is not.

Your new information does not favor any particular hat number. It's still the case that, as far as you're concerned, each possible hat number is as likely as any other (if not, then which ones are the ones that are more likely?). So if your initial judgment that the probability is 1/3 was based on the fact that your information did not favor any particular hat number over others, that judgment should stand.

James said...

Right, right. I think I get it now. Though I'm still slightly confused as to what we should conclude from all this...?

Alexander R Pruss said...

One context for this is measures on multiverses. For instance, some physicists (e.g., Alex Vilenkin) who have multiverse theories want to calculate the probability that we will observe some cosmological phenomenon. After all, if they could get probabilistic predictions, their theory would become testable. Roughly speaking, what they want to do is this: Take the number of people--across the multiverse--in circumstances relevantly like ours who do observe the phenomon and divide by the number of people in circumstances relevantly like ours. Now, in infinite multiverses that doesn't make sense. So what they do is to take a limit--they set up a cut-off (e.g., based on some measure of time), do the ratio, and take the limit as the cut-off goes to infinity. And that's their probability. If my reasoning is right, that's not going to be right, because if my reasoning is right, then where there are equal cardinalities--and in their case, the cardinality is always countable infinity--one cannot, without further data, define probabilities.

Now, as it happens, in their case, there is some further data--quantum fluctuations. So they can solve the problem.

James said...

But why does all this hinge on there being infinites involved? If the numbers were between, say, 1 and 100 are I claimed the probability of the number on my hat being divisible by 3 was 1/3, why would the scarf-issues be any different?

Alexander R Pruss said...

There are equally many positive integers divisible by three as not divisible by three. But there are not equally many positive integers up to a hundred divisible by three as not divisible by three.

James said...

Right. But all the same points would apply wouldn't they? You could initially conclude that the probability of the hat number being divisible by 3 was 1/3. You could then apply the same reasoning to the scarf number, and conclude that the probability of the scarf number being divisible by three was 1/3. And you could then claim that this was incompatible with the hat conclusion, since if the likelihood of the scarf number being divisible by three was 1/3, then the likelihood of the hat number being divisible by three should have been 2/3. You could then appeal to symmetry to show the problems here.

enigMan said...

whether the hat numbers are assigned first or the scarf numbers are assigned first actually affects the probabilities

Something like that can appear to be the case with equally likely natural numbers. If you pick one and then I do, then mine is (apparently) very probably going to be bigger than yours (since there are infinitely many more that are bigger); and similarly, if I pick mine first then it is apparently very probably going to be smaller than yours. But the probabilities cannot really behave like that, if the two selections are causally independent (e.g. in relativistic space they can both be first, in their own reference frame).

enigMan said...

Before you found out about the scarf numbers, you had no reason to think any hat number more likely than any other hat number, and that was what grounded the intuition that the answer was 1/3. But does finding out about the scarf numbers give you any reason to think any hat number more likely than any other hat number? If so, which one(s)?

If we can rule out uniform probability distributions over the integers (as in my previous comment) then what would really ground the assignment of 1/3 would be the postulation that the process of assigning the numbers was like 1, 2, 3... Even if it was different, the differences tend to canel out. Since every third one is divisible by three (more or less, in general), then the probability (the subjective probability) is quite rationally 1/3.

We then find out about the scarf numbers. The way we find out might indicate that such numbers were deriviative, in which case the 1/3 stands. Or it might indicate that either might be primary (they can't just both be random, as we can rationally rule out uniform probability distributions over integers). In that case, we can have a rational subjective probability of 1/2, since it could be 1/3 or it could be 2/3 and we don't know which. So, in any particular case, of our being told about the hats and the scarves, we could rationally have a subjective probability between 1/3 and 1/2.

I think that an interesting question here is how we should represent such an assignment mathematically. I don't think that we would normally have enough information to justify a precise assignment between 1/3 and 2/3. We might therefore give the probability not as a number but as a line of numbers between 1/3 and 2/3. The line might be denser or thicker towards one end. Or it might be something like 0.4 plus or minus 0.1, but that also seems too precise. We seem to need some fuzzy numbers, for subjective probabilities...

Neil Bates said...

Pardon me dropping back into this blog so late in the game, but I wanted to follow up. In line with enigMan's argument: suppose that instead of considering this process being in effect "all at once", we have people born and assigned one at a time to each number 1, 2, 3, 4, 5, 6, 7, 8, ... . Then it makes sense for each person who knows of this procedure, to bet there's a 1/3 chance of being assigned a number divisible by three. It shouldn't matter to that, whether this process goes on "forever" or not - right? How can the boundary condition of the future affect current expectations of any person? (Note that the scarfs are assigned according to a rule concerning the other numbers so I agree with those who say here, it matters which is done "directly" and which is the secondary rule.) I made a similar argument at the related thread, Probability on infinite sets and the Kalaam argument.

Alexander R Pruss said...

Why think the probability of one's number being divisible by three is 1/3? What formula gets you that?

Presumably it's due to the fact that if B_n = {1,...,n} and A_n is the set of numbers in B_n divisible by three, then the limit of |A_n|/|B_n| is 1/3 as n goes to infinity, where |X| is the number of elements in X.

But why should the limit be taken in this way?

Neil Bates said...

Well, in any finite case, it is indeed that chance and as per you offered - since that is (?) straightforward, I pivot back to "why not?"
BTW what do you think of all this Tegmark's MUH (~ modal realism) stuff bandied around lately?

Alexander R Pruss said...

Yeah, but in finite cases it doesn't matter in what order you count things up. In infinite cases, it matters crucially. If you count the results in a different order in your ratio-and-limit calculation, you can get any ratio between 0 and 1, or no ratio, you like.

Tegmark is going to have all the probabilistic problems of any infinite multiverse theory, plus the extra problems arising from the fact that his multiverse is so big that goes beyond cardinality.

Neil Bates said...

Beyond cardinality? I didn't know there was such a thing, other than as reference to Omega the unapproachable horizon of the cardinals.

Alexander R Pruss said...

There is no set of all sets.

But every set is a mathematical structure.

So there is no set of all mathematical structures.

But Tegmark thinks that there is something real for every mathematical structure.

So there is no set of the real things.

So the real things are beyond cardinality, because cardinality only applies where you have sets.