Cutting Cake (with a Razor)
Suppose that a group of friends is trying to fairly divide a cake. By fair, I mean that you want each person to receive an equal portion. Let’s further suppose that this cake can be cut into arbitrarily small pieces while still retaining its cake-ness (so this is not a real cake, but a Real cake). If there are N people, then each gets 1/N of the cake.
But what happens when the group of friends is infinitely large? Let’s say that there is one person for each natural number – so we can talk about person 1, person 2, and so on. If we try to give each person 1/kth of the cake, then we’ll run out of cake after k slices, and the rest get nothing. So it’s not possible for everyone to get an equal, nonzero amount of cake. In other words, if we want everyone to get the same amount, then nobody gets anything.
But it is possible for everyone to get some cake. For example, we can give 1/2 of the cake to the 1st person, 1/4 to the 2nd person, 1/8th to the 3rd person, 1/16th to the 4th person, &c. So we can provide cake for infinitely many people – but only if it’s an unfair distribution.
Now suppose that instead of a set of people, we have a set of hypotheses, and instead of distributing cake, we are distributing belief. If we’re talking about a set of mutually-exclusive hypotheses, then we only have a fixed amount of belief to divide between them – let’s say we start with 1 unit of belief. If we don’t want to rule out any hypothesis outright, then each hypothesis must receive some belief, however small. So, for example, we could give a belief of 1/2 to the first hypothesis, 1/4 to the second, 1/8 to the third, and so on. Of course, this isn’t the only possible distribution.
The important thing here is that this is an infinite series which must sum to 1, and so the sequence must converge to zero, and it doesn’t matter how you index the hypotheses. No matter how you index the hypotheses, and no matter how you distribute your belief, there must exist some N such that you are 99% certain that the index of the correct hypothesis is less than N. Or 99.9% certain, or 99.99% certain. In particular, if you have some way of measuring complexity, and if there are only finitely-many hypotheses of a given complexity, then you can bound the complexity of the correct hypothesis with 99.99% (or arbitrarily high) confidence.
Now, this isn’t quite the same as Occam’s Razor. It doesn’t show that, given two hypotheses of differing complexity, the simpler one must be a-priori more probable. Also, this doesn’t show the expected complexity has to be bounded – it doesn’t. But it does show that as hypotheses become arbitrarily complex, your belief in them must become arbitrarily small.
Within the framework discussed above, there are many possible ways of distributing your belief between hypotheses. I’ll talk more about this later.
mmm, cake.
Comment by clc — May 25, 2006 @ 11:55 am
I’m interested in where this is leading: algorithmic probability distributions? Why does Occam’s razor require bounded expected complexity?
Comment by Nick Hay — May 30, 2006 @ 8:46 pm
You’re right, Nick. Occam’s Razor doesn’t require bounded expected complexity (I just edited the article slightly to fix this).
I also mentioned (in my edit) that the constraints I discussed don’t imply that a simpler hypothesis must be more probable. This is really obvious, because if it were the case then you wouldn’t be able to learn much from data (since these constraints apply equally well to posterior distributions)! So we really can’t get a neat prior distribution “for free” – we have to admit that our priors are somewhat arbitrary.
And yeah, this is leading to algorithmic probability distributions, but the article I’m working on currently is on a different topic, so I’m going to come back to this later.
Comment by Peter de Blanc — May 30, 2006 @ 11:44 pm
I think you miss the idea of infinity here. Infinity isn’t a number and it doesn’t make sense to say you have an infinite number of friends. You might have an unbounded number of friends and you might talk about what happens as your number of friends approaches infinity, but you can’t ever actually have infinite friends. In this case, we might say that the size of a slice being 1/k approaches 0 as k approaches infinity, but it won’t ever actually be 0 because you can’t have an infinite number of friends. Note that your other scheme suffers from the same “problem”: as k approaches infinity, the slice size of the kth friend will approach 0, but will never actually become 0 because k is still a number.
Comment by Gordon Worley — June 10, 2006 @ 11:38 pm
Infinity isn’t a number
Gordon: That depends on what you mean by “number”! Sure, it’s not a natural number. But there certainly are infinite Cardinal numbers, and that’s the sort of number I was using here. A cardinal number is the size of a set in set theory. The set of friends I mentioned in this article has cardinality Aleph0, which is the size of the set of natural numbers.
Regardless of whether such a set of friends can exist in the real world, it can be useful to talk about such sets, just as it is useful to talk about the natural numbers.
[Note: I edited this reply on 11/1/06 because I thought that my original reply was not very revealing]
Comment by Peter de Blanc — June 11, 2006 @ 6:26 pm