誕生日パラドックスとUUID
2009年05月08日19:29
誕生日パラドックスというものがある。 これは、学校のクラスで自分と同じ誕生日の人が居る確立というのが割と低く感じるものだが、あるクラスの中に誰でもいいので誕生日が同じ人がいる確立というのは、実はそれよりもずっと高くかなり頻繁に起こる、という話だ。
あと、大切な話として、１クラスが３６５人以上居たら同じ誕生日が最低でも一組存在する確立は１００％になる。 そりゃそうだ。 タヌキの穴が２つあってタヌキが３匹いたら、最低でもひとつの巣でタヌキがダブるはずだ。 これを何故かタヌキではなくハトの巣理論と呼ぶ。
で、以下の説明が書かれていた。
http://en.wikipedia.org/wiki/Universally_Unique_Identifier
To put these numbers into perspective, one's annual risk of being hit by a meteorite is estimated to be one chance in 17 billion [19], that means the probability is about 0.00000000006 (6 × 10－11), equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs every second for the next 100 years, the probability of creating just one duplicate would be about 50%. The probability of one duplicate would be about 50% if every person on earth owns 600 million UUIDs.
UUIDというのは１２２ビットの乱数を発生しそれをＩＤとして使うシステムのことで幅広く利用されている。 １２２ビットの乱数を発生させたとき、ダブりが発生する確率が５０％になるまでには、天文学的な年月が必要なのだ、ということが書かれている。
だけど僕は思ったのだけど、確立が５０％っていう数字は結構大きくないだろうか。 実際には１００万分の１とかでもシステムは使い物にならなくなると思う。 もし将来UUIDがもっと本格的に普及したとき、かならずIDをもっと酷使するようなシステムが現れると思う。一日に１０万個のＩＤを生成する物品流通システムとかは実際にあらわれそうだ。 これをたったの十日間運用すると、ＩＤが一個重複する。 実務上、これでは使い物にならないと思う。
確立は考えられる時間・量・にわたって、常に「天文学的小ささ」で抑えられている必要がある。 重複する確立が１００万分の１程度の小ささでは使い物にならないのではないと僕には思える。
で、１２２ビットの乱数に重複が表れる確立が１００万分の１程度になるためには、恐らく１００年も必要ないはずではないだろうか。
それとも、ここでいう確立が１％というのは、Ｘ個のＩＤを生成するという作業を１００回繰り返すと、１度だけ衝突する、という意味なのだろうか。
あと、大切な話として、１クラスが３６５人以上居たら同じ誕生日が最低でも一組存在する確立は１００％になる。 そりゃそうだ。 タヌキの穴が２つあってタヌキが３匹いたら、最低でもひとつの巣でタヌキがダブるはずだ。 これを何故かタヌキではなくハトの巣理論と呼ぶ。
で、以下の説明が書かれていた。
http://en.wikipedia.org/wiki/Universally_Unique_Identifier
To put these numbers into perspective, one's annual risk of being hit by a meteorite is estimated to be one chance in 17 billion [19], that means the probability is about 0.00000000006 (6 × 10－11), equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs every second for the next 100 years, the probability of creating just one duplicate would be about 50%. The probability of one duplicate would be about 50% if every person on earth owns 600 million UUIDs.
UUIDというのは１２２ビットの乱数を発生しそれをＩＤとして使うシステムのことで幅広く利用されている。 １２２ビットの乱数を発生させたとき、ダブりが発生する確率が５０％になるまでには、天文学的な年月が必要なのだ、ということが書かれている。
だけど僕は思ったのだけど、確立が５０％っていう数字は結構大きくないだろうか。 実際には１００万分の１とかでもシステムは使い物にならなくなると思う。 もし将来UUIDがもっと本格的に普及したとき、かならずIDをもっと酷使するようなシステムが現れると思う。一日に１０万個のＩＤを生成する物品流通システムとかは実際にあらわれそうだ。 これをたったの十日間運用すると、ＩＤが一個重複する。 実務上、これでは使い物にならないと思う。
確立は考えられる時間・量・にわたって、常に「天文学的小ささ」で抑えられている必要がある。 重複する確立が１００万分の１程度の小ささでは使い物にならないのではないと僕には思える。
で、１２２ビットの乱数に重複が表れる確立が１００万分の１程度になるためには、恐らく１００年も必要ないはずではないだろうか。
それとも、ここでいう確立が１％というのは、Ｘ個のＩＤを生成するという作業を１００回繰り返すと、１度だけ衝突する、という意味なのだろうか。
コメント一覧
カオソーイ 2009年05月09日 01:09
でも、２月２９日生まれで一年ダブっている人がいたら、クラスに何人いようと、同じ誕生日の人はいない気がする。
おかあつ 2009年05月09日 04:49
ｗ そ、そっちのダブリはなしの方向で．．．
