Coupon collector's problem

先日，こんなニュースを目にしました。
AKB48の「景品商法」中止　「独禁法に抵触する恐れ」

このニュースを数学的に考察すると，背景になかなか面白い数学の問題が潜んでいます。

【問題】
44種類のポスターが同様に確からしく添付されているCDが発売されている。
(1) CDを44枚買ったときにちょうど44種類のポスターが揃う確率を求めよ。
(2) CDを44枚買ったときに揃うポスターの種類の期待値を求めよ。
(3) 44種類のポスターが揃うまで購入するCDの枚数の期待値を求めよ。

直観的に，答はどのくらいの数字になると思いますか？




-------------------
【解答】
(1)は 44! / 44^44 ≒ 1.29×10^(-18)
70京人に１人の割合，という計算です。


(2)はカウント用の確率変数を用意する問題です。

44枚CDを買ったときに，第 j 種類のポスターが入っていれば X_j = 1，そうでなければ X_j = 0 となる確率変数 X_j を用意すると，
　　P(X_j = 1) = 1-(43/44)^44
であるので，求める期待値は
　　E(X_1 + …… + X_44) = E(X_1) + …… + E(X_44) = 44(1-(43/44)^44) ≒ 28
感覚的にも妥当な数字ですね。


(3)は条件付期待値の和の問題です。

１種類目を揃えるまでには１枚買えばよい。
１種類目が揃ったという条件下において，CDを１枚買うとき，それがまだ持っていないポスターである確率は43/44なので，２種類目のポスターを引き当てるまでに買うCDの枚数の期待値は44/43
２種類目が揃ったという条件下において，CDを１枚買うとき，それがまだ持っていないポスターである確率は42/44なので，３種類目のポスターを引き当てるまでに買うCDの枚数の期待値は44/42

同様に繰り返し，これらの期待値の和をとると，44種類目のポスターを引き当てるまでに買うCDの枚数の期待値は
　1 + 44/43 + 44/42 + …… + 44/2 + 44 ≒ 192.4

CD１枚が1500円と仮定すると，金額の期待値は 1500 × 192.4 = 28万8600円。
とてつもない金額になってしまいます。

なお，(3)の問題は，Coupon collector's problem という有名問題です。


よろしければクリックお願いします。
人気blogランキングへ

Comments

1. Posted by とみお   2008年03月07日 21:22

どうもはじめまして(?)
ほぼ　ｎ×logｎ　なんですね。でかっ。

2. Posted by フルカワ   2008年03月10日 01:16

クーポンコレクター問題、coupon collector's problemは深いです。
個人的には未解決の問題があります。

n種類のおまけをそろえるまでの買う個数xの確率が最大のときの最頻値xは何か?

その最頻値と、期待値：n * (1 + 1/2 + … + 1/n) において、

予想:最頻値<期待値？

は真か偽か？

http://www2.ezbbs.net/cgi/reply?id=dslender&dd=07&re=30140

3. Posted by 名大生   2008年03月24日 13:49

名大⇒東大大学院へロンダしたいけど数学科ってどんな雰囲気？名大だと馬鹿にされないか不安です。

4. Posted by はじめまして   2008年03月30日 22:34

今年の東大の３問目の六角形を答える問題は
難問なのでしょうか？正６になることがわかりませんでしたが・・・

5. Posted by i   2008年05月08日 23:15

＞＞triton先生
差し上げた問題の解答解説がこのＵＲＬにあります。
http://www.geocities.jp/seikosukensmc/
いやはやでも結構自信作だったあの問題や、友達が命を懸けて（笑）作ったラングレーが解かれるとはよもや思いませんでした。崇拝します。

6. Posted by triton   2008年05月09日 00:59

>名大生さん
大学名で馬鹿にされたりなどされませんよ。完全に実力がものを言う世界ですし。

>はじめましてさん
どこまで記述すべきなのか判断が難しいでしょうね。正六角形になるという結論自体はそんなに難しくはないと思います。

>iさん
ありがとうございます。
いえいえ。幾何が好きなだけですよ。笑

7. Posted by はじめまして   2008年05月24日 14:39

東大の正六角形の問題特集とか、
機会がございましたら、
やっていただけると参考になります
ところで数学の勉強法なのですが、
分からなくて答えをみるタイミングとか
どうすればいいのですか？

8. Posted by triton   2008年05月26日 08:55

>はじめまして さん

コメントありがとうございます。
東大入試問題のレビューは是非やっていきたいと思っています。
正六角形の問題とは，どの問題でしょうか？
2008年度の，正八面体を回転させる問題でしょうか。

答えを見るタイミングに関してですが，どの大学も一問あたり25〜30分となっていますので，実際の入試では解ける問題は20分程で答案を仕上げたいところです。
それから逆算すると，考え始めてから答案の方針が出来上がるまでにかけられる時間は5〜10分程度でしょう。長くても15分程度だと思います。

ただ，これはあくまで実際の入試を考えた方法です。個人的には，分からない問題はもっと長く深く考える習慣をつけるのがよいと思います。
フィールズ賞受賞者の広中平祐先生の有名な話にもある通り，一つの問題を何日もあるいは何週間も考え続けて最後に解けたときの感動は，何物にも代えられない素晴らしい体験だと思います。

9. Posted by はじめまして   2008年05月27日 22:07

貴重なアドバイスありがとうございます。
ある程度時間内に解けるようにしながらも
自分で考える姿勢を失わずに、根気よく
考えることも大切だということですね？
たしかに、自ら問題を解決する姿勢は
数学に限らず、化学や物理などにも
共通する、大切な要素だと感じております。
２００８年の3問目です。

10. Posted by Shu   2022年10月18日 23:17

はじめまして！
横からすみません
(2)の問題なのですが、最後の行
E(X_1)+…+E(X_44)=44×(1-(43/44)^44)と出していますが、これって、1から44までのすべてのjでP(X_j)を「j種類のポスターが入っている」という前提で計算しているという事ですよね？
(1-(43/44)^44)は「少なくとも~種類ポスターが入っている」という考えになるので、「j種類のポスターが入っている」と言えないのでは(j種類入っている確率がすべて1-(43/44)^44なのがしっくり来ていない)と疑問に感じています。
統計習いたての身で変な質問すみません…