ヤバゲータウンの確率論

2010年9月22日12時50分〜9月23日21時30分の間、一部のお客様のモバゲータウンのユーザIDに紐づくページ(マイページを含む)に、他のお客様がアクセスできる状態 となっており、単体では個人が特定できない情報ではありますが性別・地域等の一部の登録情報の閲覧その他の利用ができる可能性がありました。本事象により、情報の閲覧がされたお客様と情報の閲覧をしたお客様の組み合わせの数は最大で38組の可能性があり、現在までに閲覧されたことが確認できているのは3名、閲覧できたことが確認できているのは7名です。

http://yahoo-mbga.jp/page/guide/201009_report.html

ID登録処理時における誤ったシステム設定により、入会前のお客様に一時的に付与する仮IDがごく稀に重複してしまうことがあり、本障害が発生いたしました。対策として、この仮IDが重複することがないようにシステムの改修を行いました。

http://yahoo-mbga.jp/page/guide/201009_report.html

気になるのは二点。

  • なぜ入会前のお客様に一時的に付与する仮IDがごく稀に重複してしまったのか
  • 入会前のお客様に一時的に付与する仮IDが重複すると、なぜユーザIDに紐づくページに他のお客様がアクセスできる状態になってしまうのか

なぜ仮IDが重複すると他人のMyページが見えてしまうのかも興味があるが、今回は、前者について考えてみようと思う。

問題: 仮IDのビット数を推定せよ

仮IDというのはおそらくセッションIDの一種で、乱数が割り当てられているのだろう。生成された乱数が既存のIDと重複する可能性があるため、重複チェック処理を入れないと違うユーザに同じIDが割り当てられることがありうる。
では、乱数の範囲はどの程度だったのだろう?

簡単なモンテカルロ法で結果を見積もってみる

ビット数k=32,ユーザ数n=50万程度なら現実的な時間で答えが出る。

実行結果はけっこうばらつきが大きいのだけれど、k=32とするとn=50万-60万あたりで重複回数がそれっぽくなる。ユーザ数については割とリアルな数字といえるが、セッションIDが32ビットなのは常識的にちょっと考えにくいような……。
ちなみにk=64だと重複の発生は確認できませんでした。

乱数で割り当てたIDの衝突可能性についてのモデルを作りたい(Open problem)

K=2^k種類の数字をランダムで1個選ぶという操作をn回行った(復元抽出、K>n)ところ、重複する数字がm組存在した。

  • mの期待値が38になるK,nを求めよ。
  • K,nが与えられたときのp(m)を求めよ。
  • nが与えられたとき、重複の発生率がa以下になる――すなわち、[tex:\sum_{m=1}^{\infty}{p(m)}

誰か解いてくれるといいですね。
たぶんm「組」っていうのがめんどくさそう。