FLAGS

筆者おかあつ 大きな区分 記事の区分 記事の一覧 検索 ツイート

2009年5月8日金曜日

誕生日パラドックスとUUID (mixi05-u459989-200905081929)

ミクシ内で書かれた旧おかあつ日記を紹介します。
誕生日パラドックスとUUID
2009年05月08日19:29
誕生日パラドックスというものがある。 これは、学校のクラスで自分と同じ誕生日の人が居る確立というのが割と低く感じるものだが、あるクラスの中に誰でもいいので誕生日が同じ人がいる確立というのは、実はそれよりもずっと高くかなり頻繁に起こる、という話だ。

あと、大切な話として、1クラスが365人以上居たら同じ誕生日が最低でも一組存在する確立は100%になる。 そりゃそうだ。 タヌキの穴が2つあってタヌキが3匹いたら、最低でもひとつの巣でタヌキがダブるはずだ。 これを何故かタヌキではなくハトの巣理論と呼ぶ。

で、以下の説明が書かれていた。

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というのは122ビットの乱数を発生しそれをIDとして使うシステムのことで幅広く利用されている。 122ビットの乱数を発生させたとき、ダブりが発生する確率が50%になるまでには、天文学的な年月が必要なのだ、ということが書かれている。

だけど僕は思ったのだけど、確立が50%っていう数字は結構大きくないだろうか。 実際には100万分の1とかでもシステムは使い物にならなくなると思う。 もし将来UUIDがもっと本格的に普及したとき、かならずIDをもっと酷使するようなシステムが現れると思う。一日に10万個のIDを生成する物品流通システムとかは実際にあらわれそうだ。 これをたったの十日間運用すると、IDが一個重複する。 実務上、これでは使い物にならないと思う。

確立は考えられる時間・量・にわたって、常に「天文学的小ささ」で抑えられている必要がある。 重複する確立が100万分の1程度の小ささでは使い物にならないのではないと僕には思える。

で、122ビットの乱数に重複が表れる確立が100万分の1程度になるためには、恐らく100年も必要ないはずではないだろうか。




それとも、ここでいう確立が1%というのは、X個のIDを生成するという作業を100回繰り返すと、1度だけ衝突する、という意味なのだろうか。


コメント一覧
カオソーイ   2009年05月09日 01:09
でも、2月29日生まれで一年ダブっている人がいたら、クラスに何人いようと、同じ誕生日の人はいない気がする。

おかあつ   2009年05月09日 04:49
w そ、そっちのダブリはなしの方向で...
 
出展 2009年05月08日19:29 『誕生日パラドックスとUUID』