space and games

May 10, 2006

Cutting Cake (with a Razor)

Filed under: General — Peter de Blanc @ 10:04 pm

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.

May 4, 2006

begin

Filed under: General — Peter de Blanc @ 9:36 pm

Hi! This is the second sentence of the first post on the web-log Space and Games. Currently, the sole author of this publication is me, Peter de Blanc.

“Space and Games” refers to two concepts which are present in many problems or situations which we, as humans, find interesting. We live in space: we are accustomed to thinking of the universe in terms of continuity, dimension, and distance, and most universes which we imagine share these features. We play games: we pursue goals, strategize, cooperate, conspire, and betray. Sometimes we fancy ourselves agents.

I will use this web-log to write about my favorite topics, including pure math, applied math, the Singularity, rationality, science, strategy, utilitarianism, psychology, optimization processes, and Occam’s Razor.

I’m looking forward to talking to all the interesting people out there. See you soon!