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.

15 Comments »

  1. mmm, cake.

    Comment by clc — May 25, 2006 @ 11:55 am

  2. 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

  3. 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

  4. 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

  5. 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

  6. Great write-up, I am a big believer in commenting on sites to help the blog writers know that they’ve added some thing worthwhile to the world wide web!

    Comment by prime wireless danville va — November 28, 2013 @ 12:22 am

  7. ゴルフクラブ | info-job.biz | ゴルフ ドライバー | ゴルフ 通販 | ゴルフクラブ パター | ゴルフ アドレス | スラセンジャー | ゴルフ アドレス | ウェッジ メンズ | ゴルフパートナー | ランバックス | ゴルフアイアンアドレス |

    カシオ 時計おすすめ | iphost.info | アデイダス 時計 メーカー | アルマーニ ブランド | ハミルトン時計 正規 | ベビージ 時計 価格 | エディフィス時計 | オシアナス 時計 | カシオ シーン | ジーショック 人気 | プロトレック 腕時計 | カシオ 時計 電波時計 | CASIO EDIFICE時計 | G-SHOCK | CASIO PRO TREK時計 | ベビージ 時計 専門店 | スタンダード 海外モデル |

    カシオ 時計 | jinhao | リニエージ 時計 | ベビージ 時計 値段 | ベビージ 時計 | プロトレック 腕時計 | 耐衝撃構造 | ジーショック メンズ 時計 | ジーショック 人気 | カシオ シーン | カシオ オシアナス 価格 | エディフィス腕時計 | ウェーブセプター | セイコー 時計 人気 | シチズン 電波時計 | オリエント時計 ランキング | アルバ時計 ブランド |

    モンクレールダウンコート新着 | kailiblade | Monclerダウンジャケット人気 | カナダグースコート新着 | ノースフェイスダウンジャケット | デュベティカジャケットメンズ新作 | ラベンハムダウンジャケット | ラブダウンジャケット 格安 | タトラスダウンコート激安 | ミュウミュウダウンジャケット正規品 | プラダダウンコート販売店 | コロンビアダウンジャケット | Marmotジャケットメンズ人気 | Mont-Bellダウンジャケットメンズ格安 | マウンテンハードウェアコート超格安 | ヴァランドレダウンコート |

    キャロウェイ アイアン | http://www.kusca.biz | アイアン 選び方 | ゴルフ ユーティリティ | フェアウェイウッド スイング | オデッセイ パターカバー | ドライバー シャフト | ウエッジスニーカー |

    マークジェイコブス 時計 新作 | menag-air | スウォッチ 腕時計 レディース | タグ ホイヤー 腕時計 通販 | オメガ ブラック文字盤 | オリエント 腕時計 アンティーク | シチズン 腕時計 エコドライブ | DKNY 腕時計 | ティーダブル スティール 腕時計 | ニクソン 腕時計 べっこう | ベスタル 腕時計 セール | Marc Jacobs 腕時計 | ミニーマウス Watch | ゲス メンズ ウオッチ 腕時計 |

    ブルガリ 時計 メンズ 新作 | G Shock Baby G | シャネル J12 コピー | ディーゼル 腕時計 | アルマーニ レディース 時計 | テンデンス正規 | Coach メンズ 時計 | Emporio Armani 時計 修理 | Gucci 日本 | カシオ メンズ 腕時計 | ニクソン 時計 | DIESEL 腕時計 女性 | Casio 時計 レディー | ディーゼル レディース | ハミルトン 電波時計 | メンズ腕時計 セイコー | カシオ 腕時計 売れ筋 | アディダス 時計 | ブルガリ 店舗 | カシオ ソーラー電波時計 | シャネルj12クロノグラフ | シチズン 高級時計 | DIESEL 腕時計 店舗 | gショック 価格 | Coach レディース 腕時計 | ハミルトン 東京 | アディダス 時計 レディース | 腕時計 カシオ メンズ | テンデンス 時計 店舗 |

    Comment by CherveCok — December 1, 2013 @ 2:31 pm

  8. You’ll be able to fit leggings along with given knit t shirts, clothes or simply sweatshirt.

    Comment by http://www.weimbreeders.com/clarks-%E3%82%AF%E3%83%A9%E3%83%BC%E3%82%AF%E3%82%B9/clarks-desert-boot-%E3%83%87%E3%82%B6%E3%83%BC%E3%83%88%E3%83%96%E3%83%BC%E3%83%84 — May 17, 2014 @ 2:09 pm

  9. Guys trench jackets are fashioned from you will find many major dress vendors, like Monthly bill Blass, Paul Abboud, Kenneth Cole, Armani, Jamin Natural leather, Wilson’s Natural leather, UNITED STATES Synthetic leather and much more.

    Comment by http://www.geezimgood.com/%E3%83%90%E3%83%AC%E3%83%B3%E3%82%BF%E3%82%A4%E3%83%B3-%E3%82%AB%E3%82%B7%E3%82%AA-%E3%83%99%E3%83%93%E3%83%BCg-g-ms-%E3%82%B8%E3%83%BC%E3%83%9F%E3%82%BA-%E3%83%AC%E3%83%87%E3%82%A3%E3%83%BC%E3%82%B9-%E8%85%95%E6%99%82%E8%A8%88-% — May 17, 2014 @ 2:34 pm

  10. Shearling clothes will be one of the more favored categories of jacket because of their fantastic warmness plus traditional design and style which can be beautiful.

    Comment by http://www.whichcomputer.net/prada-%E3%83%97%E3%83%A9%E3%83%80b2600g-tessuto-stampatoblack-watch%E3%83%88%E3%83%BC%E3%83%88%E3%83%90%E3%83%83%E3%82%B0.html — May 17, 2014 @ 2:34 pm

  11. ma compete sociale se ‘vrrle rrtre r茅duite 脿 parr avec Davis POUJADAS soir 脿 20H et au niveau boulot, C’est compliqu茅 脿 g茅rer vu que cette petite b茅b猫te (L’amibe) Rend hyper sound 脿 la lumi猫re. Au moins, Je sais ou j’irais en vacances cet 茅t茅, Ou, Bah en Irlande, Au moins la bas pas delaware erotic d’锚tre 茅bloui par 1 truc qu’on appelle soil (que je d茅teste d’ailleurs particuli猫rement en ce defining moment alors, Qu’avant, across s’adorait, Comme quoi.)
    nike sb eric koston purple http://www.bestofsicily.it/nikefree-fr.asp?p=3538

    Comment by nike sb eric koston purple — May 17, 2014 @ 5:57 pm

  12. the dissipateur make use of toujours n’t ventilateur nufactured write “wind turbine d茅sax茅e, Ce syst猫me another n’t vntge : L’air chaud se ‘vrrle rrtre directemdurantet d茅gag茅 dehors du bo卯tier, 脌 l’inverse nufactureds mod猫les 脿 ventilateur axial comme celui harley-davidson componen Raon 7770 exemple.
    nike free run 3 homme http://www.bestofsicily.it/nikefree-fr.asp?p=886

    Comment by nike free run 3 homme — May 17, 2014 @ 5:57 pm

  13. not 1er ophtalmo avait d茅cel茅 e cataracte, not second e hyperm茅tropie (Avec storage cache sur l’oeil voyant plastic bottles faire travailler “the fain茅ant”). mes examens ophtalmologiques durent 1h tellement mon “cas” interest l’ensemble des sp茅cialistes : Aucune explication donn茅e, Seule l. a,chicago realization : l. a,chicago vue n’est pas corrigible.
    nike blazer verte http://www.bestofsicily.it/nikefree-fr.asp?p=2671

    Comment by nike blazer verte — May 17, 2014 @ 5:58 pm

  14. Today, white colored research layers often known as health care provider jackets, are utilized from just about all gurus within the healthcare premises.

    Comment by http://www.ldydtz.com/hermes-%E3%82%A8%E3%83%AB%E3%83%A1%E3%82%B9/%E3%83%90%E3%83%83%E3%82%B0/%E3%83%9D%E3%83%BC%E3%83%81 — May 18, 2014 @ 11:05 pm

  15. L’hom茅opathe m’a pr茅scrit n’t traitement l’ordre de attached to (plastic bottles l’ann茅e) Et n’t traitement imm茅diat plastic bottles l’ensemble des seconds o霉 elle se ferais piquer. Ce traitement efficace d茅j脿 une fois cuando on the prends l’ensemble des piqures l’ordre de moustiques 脿 temps, Je i am suis donn茅 1 jour l’ordre de patience (Du form: on the va voir ce que 莽a dne) Avec ce traitement imm茅diat avant l’ordre de repasser 脿 los angeles cortizone the soir (decide que j’aurais faite cuando il n’y avait pas european l’ordre de changement cours journ茅e) Concernant cette piqure qui a pris des measurements 茅normes sur los angeles joue. Franchement je n’y croyais pas du promote mais:. los angeles A MARCHE, en trois heures l’ordre de traiteml’ensemble dest toutes minute 30 (2 produits diff茅rents, 5 granules en 15 et 7CH) Le gonflement 脿 r茅duit l’ordre de 90% ne laissant or more qu’un purpose bien rouge comme l’ensemble des laissent morsures puce (n’t peu or more gros que l’ensemble des piqures l’ordre de moustiens diam猫tre),
    custom crystal nike blazers http://www.formatoclinico.com.br/Airjordan-fr.asp?p=9003

    Comment by custom crystal nike blazers — May 23, 2014 @ 6:05 pm

RSS feed for comments on this post.

Leave a comment

Powered by WordPress