クーポンコレクター問題

クーポンコレクター問題とは、ランダムに出るn種類の商品を複数個買うとき、いったいいくつくらい買えば全種類入手できるかを求めるような確率論の問題である。

概要

ガチャガチャやお菓子つきのおもちゃ、アイドルCDの生写真など等確率でランダムに封入されているものについていくつくらい買えば全種類手に入れられるかをあらかじめ見当付けたい時に役に立つ。

ところで問題の名前の通りクーポン券をそろえたいという状況はいまいち思い浮かばないが、これはおそらく「(商品に封入されているなどする)クーポン券を全種類集めることで商品と交換できる」というようなもの（要はオフライン版コンプガチャ）だったのだろうと思われる。
→ Wikipedia：クーポンコレクター問題
　いつの時代にも阿漕な商売はあるものである。

ここでは、等確率でランダムに出るn種類のものについて全種類出そろうまでの回数の平均を求める。・・・のだが、導出は結構むずかしいので下のまとめまで飛ばしてしまっても良い。

導出

htmlめんどいのでややむずかしいのでかなりざっくりと説明する。

i-1種類出ている状態で次の新しいi種類目が出るまでに要する回数を X_i 、
全種類（n種類）出るまでに要する回数を N(= X₁+X₂+...+X_n) とする。

i-1種類出ている状態で次の新しいi種類目が出る確率は

　p_i=(n-i+1)/n

要する回数がk回である確率は「k回目に出る確率」×「k-1回目まで出ない確率」なので

　P(X_i=k)=p_i(1-p_i)^k-1　(ただしk=0,1,2,...)

幾何分布そのまんまなのでその論を拝借すれば、要する回数の平均（期待値）は

　E(X_i) = 1/p_i = n/(n-i+1)

（この平均の求め方は無限級数やら偏微分やらが出てきてここでやる範疇じゃないので気になる人は「幾何分布」でググれ）

これはあるi種類目についてのことなので、全体の平均回数E(N)はこれをi=1～nについて足せばよい。従って

　E(N) = E(X₁)+E(X₂)+...+E(X_n) = n/n+n/(n-1)+...+n/2+n/1
　 = n(1/n+1/(n-1)+...+1/2+1/1)
　 = n・Σ_[k=1~n]1/k

となる。

まとめ

以上より、n種類のものが全種類出そろうまでに要する平均回数E(N)は次の式で求められる。

E(N) = n(1/n+1/(n-1)+...+1/2+1/1) = n・Σ_[k=1~n]1/k = nH_n　・・・(1)

ここでH_nは調和級数と呼ばれるもので　H_n=Σ_[k=1~n]1/k　である。

具体例

例1. 6面サイコロの目が全部出そろうまでに振り続ける平均回数

具体例として6面サイコロの各目（1～6）が全部出そろうまで振り続ける場合について考える。上のまとめの(1)式にn=6を代入すれば

　平均回数 = 6×(1/6+1/5+1/4+1/3+1/2+1/1) = 14.7回

となる。ここで気をつけたいのは「同じことを100人の人がやったとして、15回目には50人が1～6の目全てを出し終えている」という意味ではない。ここで求めているのは100人全員が1～6の目を出し終えたあとで、それまでの回数を平均したものである。実際には15回目の時点で64,5人くらいが全ての目を出し終えている（確率で言うと約64.4%）。ちなみにnが十分に大きければ平均回数が終わった時点で全種類そろっている確率は1-1/e≒63.2%となる（ネイピア数の定義による）。
平均回数が50%の人が全種類そろえるまでの回数より大きくなるのは、運のいい人はすぐに全種類出るが運の悪い人はいつまでたっても最後の数個が出てこないといったことが起こりうるからである。

例2. CDに封入されている生写真全48種類を入手するまでの平均購入数

あるアイドルのCDにおまけとして生写真48種類のうちどれか1枚ランダムで封入されているとする。このとき、全種類集めるまでのCDの平均購入枚数は

　平均購入枚数 = 48×(1/48+1/47+1/46+1/45+...+1/2+1/1)=48×4.458... ≒ 214枚

CD1枚あたり1000円とすれば全種類そろえるためには20万円近い支出を覚悟しておく必要がある。

nが大きくなるほど手で計算するのは手間になるが、「調和級数」でググれば計算してくれるようなサイトはすぐに見つかるだろう。プログラミングについてちょっとでもかじったことのある人ならば作るのは特に難しいものでもないはずである。

補足：調和級数とオイラー定数

専門的なことはともかく、nが十分大きければ対数電卓さえあれば以下の式で簡単に調和級数の近似値が得られる。

H_n≒log_en+γ

ここでγはオイラー定数と呼ばれるものでγ =0.57721566...である。自然対数log_e（ln）はPCの電卓機能に入っていると思うので、nの値が大きく総和の式もめんどくさい人はこちらの式を使うと良いだろう。

n種類のものを集めるまでの平均回数とその他の数値の表

種類n	平均値E(N)	調和級数Hn	自然対数logen	Hn-logen（γに近似）
6	14.7	2.45	1.79175	0.65824
10	29.2896	2.92896	2.39789	0.53107
25	95.3989	3.81595	3.21887	0.59708
50	224.960	4.49920	3.91202	0.58718
100	518.737	5.18737	4.61512	0.57225
200	1175.60	5.87803	5.29831	0.57971
500	3396.41	6.79282	6.21460	0.57821
1000	7485.47	7.48547	6.90875	0.57671
10000	97876.0	9.78760	9.21044	0.57716

終わりに

改めて平均回数を求める式をここにおく。

E(N) = n(1/n+1/(n-1)+...+1/2+1/1) = nH_n
nが十分に大きければ　E(N) ≒ n(log_en+0.5772...)

この式から平均回数×値段でコンプリートまでにかかる額の目安がつく。この手のものに出会ったらまず一度止まって考えてみるといいだろう。何も不利な勝負に出ることはない。

もちろんよく考えた上で勝負に出てもいいだろう。しかしガチャガチャと財布のお金ならばどれくらい買ったかまたは使ったかが実感として分かるものの、電子マネーとなってしまうと気づかぬ間についつい使いすぎてしまう。月に使う金額を決め家計簿をつけるなどのごく初歩的なことで使いすぎることは抑えられるはずである。

関連項目

• 確率
• 幾何分布
• 調和級数 / オイラーの定数
• ガチャ / コンプリートガチャ
• AKB商法