iriya_ufo’s blog

Curiosity was simply the first derivative of knowledge.

Coupon Collector's Problem

問題

オタクを悩ます問題の一つに，"Coupon Collector's Problem" というものがあります．
僕はこの "Coupon Collector's Problem" に関して深淵なる世界を垣間見た気がします．
大いなる感動がありましたので，今日ここに記します．

"Coupon Collector's Problem" とは何か?

これです．
http://en.wikipedia.org/wiki/Coupon_collector's_problem

おっと，リンク先にはごちゃごちゃと書いておりますが，いえいえ難しく考える必要はないのです．
僕は "Coupon Collector's Problem" なんていう名前がいけないんだと思います．
そこで今からこの問題を "フィギュア収集問題" と名づけることにします．

"フィギュア収集問題" とは何か?

これはオタクの深層心理をついたなかなか痛い問題です．
大抵のフィギュアは5k前後で買うことのできるものが多いですが，中には"おまけ"と称して別の物とついてくるフィギュアがあるのです．
つまりは"フィギュア付きのお菓子"とかそういうものです．もはやメインのお菓子など眼中にないのは分かりきったことですね．
ではこの問題を一般化します．

ある"お菓子"を買うと，n 種類あるフィギュアのうち一種類がランダムでついてきます．
このフィギュアを n 種類全部収集するには，平均いくつ"お菓子"を買えばいいでしょうか．

はい，これが"フィギュア収集問題"であります．

  • 一般化したフィギュア収集問題に日々頭を抱えているそこのあなた!
    • そんなあなたは以下を読む．

まずこの問題を解く鍵は，最初のうちの数種類のフィギュアを集めるのは至極簡単だが残り少なくなってきた種類のフィギュアを引き当てるのは限りなくムズい，というのに気づく必要があることですね．
能書きたれずにさっさと書いてみましょうか．

解法
  • 手元に0種類のフィギュアを手に入れているとする．

このとき，もう一つお菓子を買って新しいフィギュアがついてくる確率は
\frac{n-0}{n}
よって，一種類めのフィギュアを手に入れるまでに買うお菓子の数の期待値は1．

  • すでに一種類のフィギュアをGetしているものとする．

このとき，もう一つお菓子を買って新しいフィギュアがついてくる確率は
\frac{n-1}{n}
よって，二種類めのフィギュアを手に入れるまでに買うお菓子の数の条件付期待値は
\frac{n}{n-1}
以下同様に，

  • すでに k 種類のフィギュアを持っているとき，k+1 種類めのフィギュアを手にする確率は

\frac{n-k}{n}
よって，k+1 種類めのフィギュアを手に入れるまでに買うお菓子の数の条件付期待値は
\frac{n}{n-k}

k=0, k=1, …, k=n-1 の場合を全て足してやればいいから，求める期待値(平均)は
\frac{n}{n} + \frac{n}{n-1} + ... + \frac{n}1 = \frac{n}1 + \frac{n}2 + ... + \frac{n}{n}
つまり
n \sum_{k=1}^{n} \frac1{k}
となります．

あ，ちなみに条件付期待値についてはこれ参照
http://ja.wikipedia.org/wiki/%E6%9D%A1%E4%BB%B6%E4%BB%98%E6%9C%9F%E5%BE%85%E5%80%A4
こちらは条件付確率についての理解を助ける例
http://www.freedom.ne.jp/daishi/gamble/rikei/rikei01.htm

さてさて，先ほどの結果をよくみてみましょう．
n \sum _{k=1}^{n} \frac 1{k}
おお!!
結果に harmonic number が出現しているではないですか!!
僕はこの事にすごく驚いたわけです．
harmonic number は Hn と表記され
H_n := \sum _{k=1}^{n} \frac 1{k}
で定義されております．

フィギュア収集問題の簡潔さもさることながら，結果の数式もまた簡潔で綺麗ではないか．

しかし驚きは止まるところを知らなかったのだ!
僕はフィギュア収集問題と統計学と解析論にこれだけの関連性があったことを知って驚きだ．
それは一体何か?というと…

そうですね，まず先ほど求めたフィギュア収集問題の分散(variance)を求めてみましょうか．
これはもう期待値(平均)がさっき分かりましたから，それを使うと楽ですね．
分散
n^2 (\frac1{1^2} + \frac1{2^2} + \frac1{3^2} + ...) = \frac{{\pi}^2}{6} n^2
*1
となって……．
ぬおおおおお!!
こ，これはバーゼル問題の答えを含んでいるではないか!
ちなみにバーゼル問題ってのは数学者を100年近く悩ませた難問でそれを解いたのが，かのオイラー先生なわけだ．
リーマンのζ関数とも深い関わりがあってオイラー先生はすばらしく美しい解法でこの問題を解いたんです．
解き方はこちらをどうぞ．
http://en.wikipedia.org/wiki/Basel_problem
僕はこのオイラーの解法を初めて理解したときは鳥肌が立ちましたね．素晴らしい．

さらに今回はフィギュア収集問題*2の分散がバーゼル問題と関係があって目から鱗なわけです．

ある種の数式や解法が他の分野において深い関連があったりすると
"やっぱ数学は奥が深いなぁ"と感ぜずにはおれません．
すごいです．

あー…，フィギュア収集問題ってのを思いついたのは
http://www.konami.jp/th/figure/ichigo/
これ全部コンプリートしたいなって思ったからです．普通に買えるんですけどね．

*1:厳密には間違っています．実際は不等式の関連で結ばれています．

*2:そろそろこの呼び方カッコ悪く思えてきた^^;