クーポンコレクター問題

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

概要

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

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

→ Wikipedia：クーポンコレクター問題
　いつの時代にも阿漕な商売はあるものである。

結論

等確率でランダムに出るn種類の商品について、全種類出揃うまでの回数 N の平均（期待値）E(N) は次で与えられる。

E(N) = n・(1/1+1/2+...+1/(n-1)+1/n)　　・・・(1)

ちなみに、調和級数 H_n=1/1+1/2+...+1/(n-1)+1/n を用いれば、(1) は E(N)=n・H_n とも表せる。

次節では (1) を導出する。証明は結構難しいので興味のある方以外は読み飛ばしてもらっても構わない。

導出

二段階で説明する。

まだ持っていないものを一つ得るまでに、何回必要か?

「まだ持っていないものが次に出るまでの回数の期待値」を考える。
「すでにi種類のものを集めているとき、次に1回入手したときに、まだ持っていないものが出る確率」（0 ≤ i ≤ n-1）を p_i = (n - i)/n とかく。このとき、

• 次にまだ持っていないものが、1回で出る確率：p_i
• 次にまだ持っていないものが、2回で出る確率：(1 - p_i)×p_i
• 次にまだ持っていないものが、3回で出る確率：(1 - p_i)²×p_i
• 次にまだ持っていないものが、4回で出る確率：(1 - p_i)³×p_i

のように変わることに注意されたい（「次にまだ持っていないものが3回で出る」というのは、最初の2回はすでに持っているものが出たということなので、その回数ぶん(1 - p_i)をかけないとならない）。なお、この分布は幾何分布とよばれるので、詳しい挙動を知りたい方はこの名前で調べていただきたい。

幾何分布の回数の期待値は 1/p_i であることが知られている。
なおこの計算は（無限級数であることを除けば）高校の数学Bで扱う知識で解けるので示しておく。回数の期待値をAとおくと、

A = 1×p_i + 2×(1-p_i)×p_i + 3×(1-p_i)²×p_i + 4×(1-p_i)³×p_i + …
    = p_i×[1 + 2×(1-p_i) + 3×(1-p_i)² + 4×(1-p_i)³ + …] ・・・(1)

(1)に(1-p_i)をかけると、

(1-p_i)A = p_i×[1×(1-p_i) + 2×(1-p_i)² + 3×(1-p_i)³ + …] ・・・(2)

(1)-(2)を計算すると、

p_iA = p_i×[1 + (1-p_i) + (1-p_i)² + (1-p_i)³ + …]

A = 1 + (1-p_i) + (1-p_i)² + (1-p_i)³ + …

右辺は単なる無限等比級数で、A = 1/p_i と計算できる。

全部集めるまでに、何回必要か?

上記の計算結果 1/p_i は「i種類すでに集めているときに」次の一つが得られるまでの回数の期待値なので、全部集めるまでの回数の期待値E(N) は、これをi=0～n-1について足せばよい。よって

E(N) = 1/p₀ + 1/p₁ + 1/p₂ + … + 1/p_n-1
    = n/n + n/(n-1) + n/(n-2) + … + n/1
    = n・(1/n+1/(n-1)+...+1/2+1/1)
　 = n・(1/1+1/2+...+1/(n-1)+1/n)

となる。以上から(1)を得る。 Q.E.D.

具体例

例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〜65人くらいが全ての目を出し終えている（確率で言うと約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)
nが十分に大きければ　E(N) ≒ n(log_en+0.5772...)

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

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

関連項目

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