クーポンコレクター問題

クーポンコレクター問題とは、ランダムに出る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回

となる。ちなみに6回ちょうどで6種類全部を出せないと罰を食らうのが、キングボンビーの悪行「パネル・アタック」である。回避が難しいのがわかるだろう。

例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万円近い支出を覚悟しておく必要がある。

例3. 誕生日街頭調査

道行く人に誕生日を尋ねるとしよう。閏日を無視し、365日全ての誕生日が出揃うまで終われないとすると、聞く人数の期待値は

平均人数 = 365×(1/1+1/2+1/3+ ... +1/364+1/365) = 365×6.478... ≒ 2364人

芸人にやらせちゃだめよ。

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種類集められた状態にあるとしよう(0 ≤ i ≤ n-1)。この状態になってから新たに(i+1)種類目を得るまでの間の回数は、期待値として何回だろうか？

この状態にある間は、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 と計算できる。直感的に言えば、確率x (0 < x ≤ 1)の事柄が起こるまでの繰り返し回数の期待値は1/xということで、これはxが単位分数でなくても成り立つというわけだ。

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

上記で得た 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倍=イ）が便利である。実は約0.5の誤差が出るので後で足すのだが、足せば驚くほど正確である。

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

種類 n	ア 期待値 E(N)	イ アの近似値 n(logen + γ)	ウ アとイの差 （→0.5）	エ 調和数 Hn	オ 自然対数 logen	カ エとオの差 (→γ)
6	14.70	14.21	0.486	2.45000	1.79176	0.65824
10	29.29	28.80	0.491	2.92897	2.30259	0.62638
25	95.40	94.90	0.496	3.81596	3.21888	0.59708
50	224.96	224.46	0.498	4.49921	3.91202	0.58718
100	518.74	518.24	0.4991	5.18738	4.60517	0.58221
200	1175.61	1175.11	0.4995	5.87803	5.29832	0.57971
500	3396.41	3395.91	0.4998	6.79282	6.21461	0.57822
1000	7485.47	7484.97	0.49991	7.48547	6.90776	0.57772
10000	97876.06	97875.56	0.499991	9.78761	9.21034	0.57727

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

（ウ列のみ別の編集者が加筆しています：Wolfram Alphaの結果例）

終わりに

改めて平均回数を求める式をここにおく。先述の0.5を足すことで近似式（=イ+0.5）の誤差は0.01ほどもない。

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

または,  E(N) ≒ n(log_en + 0.5772...) + 0.5

この E(N) に1回の値段を掛け算すればコンプリートまでにかかる額の目安となる。この手のものに出会ったらまず一度止まって考えてみることをすすめる。むやみに不利な勝負に出ることはない。

もちろんよく考えた上で勝負に出てもいいだろう。運営への好意のお布施ならそれもまたよし。しかしガチャガチャと財布のお金ならばどれくらい費やしたかが実感として分かるものの、電子マネーで気づかぬ間に使いすぎたりしないよう、くれぐれも気を付けていただきたい。月に使う金額を決め家計簿をつけるなどの対策で、支出を抑えよう。

関連項目

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