A Proof of Occam's Razor

Another way of putting this is that all probability distributions over an infinite enumerated set are biased towards elements that occur earlier, regardless of the principle of enumeration.

Your proof can't be right because it doesn't use the concept of "complexity" in any non-trivial manner. If we replace "complexity" with "flubbity", so that there's only a finite number of hypotheses for any given "flubbity", your proof will still go through.

For some actual work on justifying Occam's Razor, see Kevin T. Kelly's Ockham Efficiency results. Kelly unpacks "complexity" in a nontrivial way that isn't just description length.

ETA: see this earlier discussion about learning and simplicity, it's very relevant to the topic of your interest.

This really doesn't seem to have formally proven anything, and so at least the title should not be "a proof of Occam's razor". And it doesn't seem like you've done anything more interesting or useful here than, say, Solomonoff induction, which can already be seen as a formalization of Occam's razor.

Maybe if you made your proof more rigorous and explained why you think the statement you're trying to prove is relevant to anyone (or should properly be called Occam's razor) then that would help.

To expand on cousin_it's point, this is way too weak because it allows for arbitrary encodings, like a complexity value of 1 for "The lady down the street is a witch; she did it."

And if you start with that complexity prior, it's difficult to see how evidence would rescue you from it.

I think the treatment of complexity is OK in this argument. However, I don't think it proves Occam's Razor. Other than possible exception within set theory, the complexity of an explanation of any phenomenon is always finite. (Counterexample if you disagree?) There is no finite integer which is 'almost' infinite.

So, given xn - the average probability among explanations of complexity n - it's quite possible for a (finite) positive number of integers m > n for which xm > xn.

It seems like what you're saying is: "If we have an infinite number of hypotheses, some of them must have infinetisimally small prior probability". That doesn't require a proof.

(I upvoted this article in spite of not learning much from it, since I love this kind of discussion. Why not read some papers about PAC learning, MDL, Algorithmic Info. Theory, or VC theory and compare/contrast for us the view of Occam implicit in each development?)

Clearly as complexity goes to infinity the probability goes to 0. (i.e. For any epsilon>0 there exists n such that all hypotheses with complexity>n have probability less than epsilon. (since otherwise there would be infinitely many hypotheses with probability >epsilon, taking 1/epsilon of them would produce a collection of hypotheses with probability>1))

So as the post says, "on average" Occam's razor must be true. (As must any other Razor using a different measure of complexity, or flubbity, or whatever. However, message length seems to me to be the only "nice" measure to use on hypotheses.) But it doesn't say that the simplest hypotheses have to be ranked in complexity order. Of course it would be elegant if they were.

Why should we favour the elegant explanation?

Occam's razor of course!

The part about there being sets of infinitely many mutually exclusive hypotheses needs to be marked as an assumption, since I can construct languages where it does not hold. Also, you need to strengthen this assumption by saying that every hypothesis is part of at least one such set.

You also need to somehow get from "the probability of a statement decreases monotonically with its complexity" to "the probability of a statement decreases exponentially with its complexity".

Maybe this has already been considered but has anyone noted that even without introducing complexity at all, you can at least say that some programs are more likely simply because there is no uniform distribution on a countably infinite set, no matter which probability measure or which way you label the set there must be at most a finite number of programs with the same probability.

Hopefully there's someone still here after 10 years XD.

Oh look, if we definitely the complexity as "the date when hypothesis was published", then I can say that the prior probability that our earth stands on top of a whale, on top of a turtle on top of an elephant is the highest, because this hypothesis is the oldest. And the Occam's razor becomes "don't propose new hypotheses". Trinitrotrololol)

I find it funny, that it works even in continuous case: suppose that we have probability density defined in R^n (or any other set). Then whatever bijection F:R <--> R^n we apply, the integral of probability density on that path should converge, therefore p(F(x)) goes to zero faster than 1/x. :)

Also, look: suppose the "real" universe is a random point x from some infinite set X. Let's say we are considering finite set of hypotheses "H". Probability that random hypothesis h € H is closest to x is 1/|H|. So the larger H is, the less likely it is that any particular point from it is the best description of our universe! Which gives us Occam's razor in terms of accuracy, instead of correctness, and works for uncountable sets of universes.

And in this case it is almost surely impossible to describe universe in a finite amount of symbols.

I don't think this proves anything at a practical level, given that it requires us to deal with hypotheses of arbitrarily high complexity. It breaks down when dealing with finite values.

Suppose there is a finite complexity value W, beyond which no more complex hypotheses can actually be imagined by any being in our universe. Physics implies that there is such a W. Nothing in your argument implies that z1<W, though.

Now consider the infinite sum “x1 + x2 + x3…” Since all of these values are positive (and non-zero, since zero is not a probability), either the sum converges to a positive value, or it diverges to positive infinity. In fact, it will converge to a value less than 1, since if we had multiplied each term of the series by the number of hypotheses with the corresponding complexity, it would have converged to exactly 1—because probability theory demands that the sum of all the probabilities of all our mutually exclusive hypotheses should be exactly 1.

x1, x2, ... is not the set of probabilities of all our mutually exclusive hypotheses. Each xi is the average of an infinite number of hypothesis to explain some particular set of data. Each xi would thus be zero, just as the probability of a real-valued random number between 0 and 1 comes up exactly 0.5 is zero.

This makes the proof fail. It's interesting, though. But I don't think you can save it. Basically, you have an infinite set of mutually-exclusive hypotheses, and you want to label them with an infinite series that sums to 1. But you can't relate an infinite convergent series to the order of your hypotheses, unless the complexity n of the hypothesis is a term in the formula for its probability - and, if it is, your approach will require that this formula decreases with n. So your approach requires presuming what you're trying to prove.

I'm also bothered by the idea that hypotheses are mutually exclusive. Having an explanation of complexity n does not prevent having an explanation of complexity n+1. If your proof applies only to a set of hypotheses pre-selected for being mutually exclusive, this set could have a very different distribution than the set of hypotheses that a would-be user of Occam's razor faces in the wild.

There does not appear to be any a priori ordering of probability by complexity value, and unless you assume this the conclusion is improperly drawn. If you assume it, the argument is circular.

If the issue I'm missing is that the conclusion should read:

hypotheses with a greater complexity value tend to have a lower prior probability

Then that would explain my confusion. It does make the conclusion pretty weak, as it's unclear if infinite possibilities even exist. If they don't, the proof collapses.

I'd written out more reasoning, but I think this works best via counterexample. Consider:

 X1,  Xm,  Xn, ...   z1, zn, zz

A. .05, .04, . 03, .......... 1, m, n,

B. .03, .04, .05, .......... n, n, n

n>m and for all Xa, a not equal to n or m, Xa<.03.

I may misunderstand the system you're using, but it looks to me like there is nothing preventing n and m from taking any arbitrary value. In other words, any hypothesis of any arbitrary complexity could conceivably have a higher average probability than X1, principally because our definition of complexity is completely undefined. At some point, hypotheses must start declining in probability, but that does not prevent there from being a spike at complexity level 1,000,000, and it does not prevent complexity level 5 being more likely than complexity level 1.

Assume ... is identical in all cases, and each member of ... < x1, x2, and x3. If I understand the system correctly, in this case, hypotheses of complexity 2 would have a higher probability than those with complexity 1, which contradicts the conclusion, which is that hypotheses with a greater complexity value have a lower prior probability. Because the definition of complexity is vacuous, this could start at any particular n.

In something more like natural language, simply because x1 is higher than some infinite subset of x's, that does not mean it is higher than all X's. Xn could be greater than X1 for any arbitrary value of n. I don't see anything that says x1 must be the greatest x, and if it is not, the conclusion appears false. There is some level of complexity that is, on average, better than every other, but there is no particular reason it must be the lowest level of complexity. Z1 could be equal to just about any natural number.

I would be totally unsurprised if I missed something here, so please correct me if I have misunderstood the proof.

Hmmm... I'd say that the problem is formulated in a way that allows for some maths, but in the process loses some of its essence.

For example, the 'proof' only talks about the length of the hypothesis, because that can be easily quantified. However, that does not rule out very short pseudo-explanations like 'god did it' or 'it's magic'. To rule out those, in practice one would need to introduce some non-mathematical language about what language is acceptable -- but that would make it very hard to reason about it mathematically.

As some commentators didn't like or couldn't understand the original phrasing of the theorem, I have added a phrase interpreting this. I didn't remove the phrase because it would make the previous comments difficult to understand.

Occams's Razor is based on empirical observations.

You can't prove it - indeed, you can easily imagine worlds where it is not true.

Define the "simplicity" of a hypothesis as 1/"complexity". If you can construct a probability distribution based on the "simplicity" of a hypothesis, then, by the same argument as above, you can prove that you should prefer the hypothesis with less "simplicity".

I cannot help but get the impression that this conclusion relies on doing nasty things with infinity. In particular it seems to take both the following assumptions:

• 0 can not be a probability.
• There can be an infinite number of probabilities in a probability distribution.
• All the probabilities in a distribution sum to 1.

... and then play them off against each other. If I was one of those high complexity theorems I'd be feeling fairly violated right about now. In fact I can recall someone using similar reasoning in a discussion with Eliezer (it involved throwing darts at a continuous real valued dart board). It ended with Eliezer questioning "0 can not be a probability" in the case of infinite sets. I don't recall if he also questioned infinite set atheism.

I voted the post up because it is interesting but I think it is incorrect. It doesn't give me reason to believe that Occams's Razor is to be preferred over the reverse distribution.

Now, x(n) is a finite real number. So in order for this series to converge, there must be only a finite number of earlier terms in the series equal to or greater than x(n). There will therefore be some complexity value, y(n), such that all hypotheses with a complexity value less than y(n) have an average probability of less than x(n). Leaving the derivation for the reader, it would also follow that there is some complexity value z(n) such that all hypotheses with a complexity value less than z(n) have a lower probability than any hypothesis with a complexity value of n.

From this it is clear that on average, or as the complexity tends to infinity, hypotheses with a greater complexity value have a higher prior probability, which could be a definition of an Anti-Occamian Razor.

For Chaos!

Alternately, if you prefer, order according to 1/complexity. The numbers wouldn't be integers but they would still be a finite number at each value and could be treated the same way.