クーポンコレクター問題

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

概要

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

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

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

結論

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

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

第n調和数 H_n=1/1+1/2+...+1/(n-1)+1/n を用いれば、この式は E(N)=n×H_n とも表せる。

具体例

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

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

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

となる。

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

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

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

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

E(N)（購入回数の期待値）の表

n	E(N)	n	E(N)	n	E(N)	n	E(N)	n	E(N)	n	E(N)
1	1	11	33.2	21	76.6	31	124.8	41	176.4	100	518.7
2	3	12	37.2	22	81.2	32	129.9	42	181.7	200	1175.6
3	5.5	13	41.3	23	85.9	33	134.9	43	187.1	300	1884.8
4	8.3	14	45.5	24	90.6	34	140.0	44	192.4	400	2628.0
5	11.4	15	49.8	25	95.4	35	145.1	45	197.8	500	3396.4
6	14.7	16	54.1	26	100.2	36	150.3	46	203.2	1000	7485.5
7	18.2	17	58.5	27	105.1	37	155.5	47	208.6	2000	16356.7
8	21.7	18	62.9	28	110.0	38	160.7	48	214.0	5000	45472.5
9	25.5	19	67.4	29	114.9	39	165.9	49	219.5	10000	97876.1
10	29.3	20	72.0	30	119.9	40	171.1	50	225.0	100000	1209014.6

nが大きくなるほどE(N)を手で計算するのは手間になるが、「調和級数」でググれば計算してくれるようなサイトはすぐに見つかるだろう。あるいはwolfram alphaで「48*HarmonicNumber[48]」と入力すればすぐに計算結果を出力してくれる。また、プログラミングやExcelについてちょっとでもかじったことのある人ならばE(N)を計算してくれるコードを自力で作るのは特に難しいことでもないはずである。さらに、後述のように対数関数とオイラー定数を用いた近似計算も有効である。

考察

「全種類入手するまでの平均回数」まで購入した場合に、全種類入手できる確率は?

ここで気をつけたいのは、ここまで述べた回数はいずれも「多数の人に、全種類集めるまで挑戦するという試行をさせたときの、平均の回数」である。

例えば上記のサイコロの例であれば、「100人全員が1～6の目を出し終えたあとで、それまでの回数を平均するとだいたい15回になる」という意味であって、「同じことを100人の人がやったとして、15回目には50人くらいが1～6の目全てを出し終えている」という意味ではない。

では逆に、「100人の人が15回サイコロを振った場合、全種類の目を出した人はどれくらいいるか」ということを考えると、だいたい64～65人が全種類の目を出していると計算できるのである。

ちなみにnが十分に大きければ、平均回数が終わった時点で全種類そろっている確率は1-1/e≒63.2%となる（ネイピア数の定義による）。

平均回数が50%の人が全種類そろえるまでの回数より大きくなるのは、運のいい人はすぐに全種類出るが運の悪い人はいつまでたっても最後の数個が出てこないといったことが起こりうるからである。

「全種類入手するまでの平均回数」の半分まで購入した場合に、何種類入手できているか?

問題設定からわかる通りであり、また次の「導出」では具体的に計算するが、入手済みの種類数が増えるにつれて、次の一つを新たに入手するのが難しくなっていく。

コンプガチャが問題になった理由の一つとして、「最初は少額だけ支出するつもりが多額になっていた」ということが起きやすいこともあるのだが、これは「入手済みの種類数が最初は急激に増えていくので、集まりやすいと錯覚するのだが、最後はなかなか集まらない」ということが理由といえる。

後述の「幾何分布の回数の期待値」を用いて、「全種類入手するまでの平均購入数」の半分で何種類集められているか（端数切捨て）を計算すると以下の通りとなる。上記の生写真48種類の例だと、うち43種類集めてもまだ折り返し地点なのである。

• 全6種類（14.7回）：4種類集めるまでの平均購入数は5.7回
• 全10種類（29.3回）：8種類集めるまでの平均購入数は14.3回
• 全20種類（72.0回）：17種類集めるまでの平均購入数は35.3回
• 全48種類（214.0回）：43種類集めるまでの平均購入数は104.4回
• 全100種類（518.7回）：92種類集めるまでの平均購入数は247.0回

導出

この節では前節の冒頭の式 E(N) = n×(1/1+1/2+...+1/(n-1)+1/n) を導出する。証明はけっこう難しいので、興味のある方以外は読み飛ばしてもらっても構わない。

二段階に分けて説明する。

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

「まだ持っていないものが次に出るまでの回数の期待値」を考える。

「すでに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)

となる。以上から結論の式を得る。 Q.E.D.

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

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

H_n≒log_en+γ

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

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

種類 n	期待値 E(N)	E(N)の 近似値	調和数 Hn	自然対数 logen	Hn-logen （γに近似）
6	14.70	14.21	2.45000	1.79176	0.65824
10	29.29	28.80	2.92897	2.30259	0.62638
25	95.40	94.90	3.81596	3.21888	0.59708
50	224.96	224.46	4.49921	3.91202	0.58718
100	518.74	518.24	5.18738	4.60517	0.58221
200	1175.61	1175.11	5.87803	5.29832	0.57971
500	3396.41	3395.91	6.79282	6.21461	0.57822
1000	7485.47	7484.97	7.48547	6.90776	0.57772
10000	97876.06	97875.56	9.78761	9.21034	0.57727

（計算プログラム：https://wandbox.org/permlink/Dmed6u8UjDKWgW8W）

終わりに

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

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

nが十分に大きければ,  E(N) ≒ n(log_en+0.5772...)

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

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

関連項目

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