誕生日のパラドックスでみるクイズマジックアカデミーDS

勉強 数学

昨日のエントリですべての問題を見るには約82万問解答する必要があるとしたQMADSだが，遊んでいると割と同じ問題をみかけることが多い．
同じ問題に出会う可能性がどれくらいかという話は，誕生日のパラドックスと呼ばれる有名な問題から知ることができる．
誕生日のパラドックスは，ある集団を考えるときに同じ誕生日の人の対が直観に反してわりと存在しやすいことをいうもので，たとえば同じ誕生日の2人がいる確率が50%を超えるのに必要な人数は23人となる．
要するに，集合Sから集合Tへの写像fを考えるときに，fが単射とならない確率は案外高いと言っているのだが，Sの要素数をk，Tの要素数をnとすると，写像の数はnk，単射の数はn!/(n-k)!となるので，求める確率は

P=1-\frac{n!}{n^k \cdot (n-k)!}

となる．
これを直接計算するのは結構大変で，
\frac{n!}{(n-k)!} \leq \{n-\frac{k+1}{2}\}^k

という不等式を用いたりすると，比較的簡単に求めることができる．
nがkに対して十分大きい場合，上式の両辺は非常に近い値をとる．
誕生日の場合はn=365にk=数十，QMAの場合はn=70000にk=数百程度であるので，十分使える近似値を得ることができる．
でもまあせっかくBigIntegerのライブラリを作ったので，今回はちゃんと厳密に計算した．
問題数とPの関係は次図のようになる．

Pの値は200から500くらいの範囲で急峻に変化し，800問を超えたあたりで同じ問題が出ている確率は99%に達する．ここから確率は気が遠くなるくらいゆっくりと上昇し，鳩の巣原理から70001問目でやっと100%になるわけだ．
誕生日問題と対応させると，出てきた問題の集合に同じものがある確率が50%を超えるのは312問目ということになる．
13回決勝に行くと丁度312問だが，これが直観と比べてどうかというと，なんか70000問というのが大きすぎて結局よくわからないかも．．

いままで確率の立場からこの問題を考えてきたが，同じ問題の対の期待値を求めることもできる．
ある問題Aに対して，もう一つの問題を持ってきたときにこれが同じものである確率は1/70000である．たとえば100問解いた時を考えると，期待値の線形性からAと同じ問題の対の期待値は99/70000となる．さらにこれを100問全体について考えると，再度線形性から100*99/70000=0.1414…となるが，この値は一つの対をダブルカウントしているので，最終的に求める期待値は0.0707…となる．
これを1000問までプロットしたものを下図に示す．
1000問解くとだいたい7問くらい重複することがわかる．ジャンルに偏りがある場合はもっと多くの問題が被ることになる．