クーポンコレクター問題とは、ランダムに出るn種類の商品を複数個買うとき、いったい何個くらい買えば全種類入手できるかを求める確率論の問題である。
概要
ガチャガチャやお菓子つきのおもちゃ、アイドルCDの生写真など等確率でランダムに封入されているものについて、どのくらい買えば全種類手に入れられるかをあらかじめ見当付けたい時に役に立つ。
ところで問題の名前の通りクーポン券を揃えたいという状況はいまいち思い浮かばないが、これはおそらく「(商品に封入されているなどする)クーポン券を全種類集めることで商品と交換できる」というようなもの（要はオフライン版コンプガチャ）だったのだろうか。
→ Wikipedia：クーポンコレクター問題
いつの時代にも阿漕な商売はあるものである。
結論
等確率でランダムに出るn種類の商品について、全種類が出揃うまでの購入回数 N の期待値（平均）E(N) は次で与えられる。
E(N) = n×(1/1 + 1/2 + ... + 1/(n-1) + 1/n)
第n調和数 Hn=1/1+1/2+...+1/(n-1)+1/n を用いれば、この式は E(N)=n×Hn とも表せる。
具体例
例1. 6面サイコロの目が全部出揃うまでに振り続ける平均回数
具体例として6面サイコロの各目（1～6）が全部出揃うまで振り続ける場合について考える。上の式にn=6を代入すれば
となる。ちなみに6回ちょうどで6種類全部を出せないと罰を食らうのが、キングボンビーの悪行「パネル・アタック」である。回避が難しいのがわかるだろう。
例2. CDの購入特典44種類を全て入手するまでの平均購入数
あるアイドルのCDを購入すると44種類のポスターがランダムで1枚プレゼントされ、このポスターを全種類集めるとイベントに招待されるとする。このとき、全種類集めるまでのCDの平均購入枚数は
CD1枚あたり1250円とすれば、イベントに招待されるためには24万円近い支出を覚悟しておく必要がある。
例3. 誕生日街頭調査
道行く人に誕生日を尋ねるとしよう。閏日を無視し、365日全ての誕生日が出揃うまで終われないとすると、聞く人数の期待値は
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で「44*HarmonicNumber[44]」と入力すれば速やかに計算結果を表示してくれる。また、プログラミングやExcelを多少使えれば、E(N)を計算させるのはそう難しくはないと思われる。さらに、後述のように対数とオイラー定数を用いた近似計算も有効である。
考察
「全種類入手するまでの平均回数」まで購入した場合に、全種類入手できる確率は?
ここで気をつけたいのは、ここまで述べた回数はいずれも「多数の人に、全種類集めるまで挑戦するという試行をさせたときの、平均の回数」である。
例えば上記のサイコロの例であれば、「100人全員が1～6の目を出し終えたあとで、それまでの回数を平均するとだいたい15回になる」という意味であって、「同じことを100人の人がやったとして、15回目には50人くらいが1～6の目全てを出し終えている」という意味ではない。
では逆に、「100人の人が15回サイコロを振った場合、全種類の目を出した人はどれくらいいるか」ということを考えると、だいたい64～65人が全種類の目を出していると計算できるのである。
ちなみにnが十分に大きければ、この平均回数以内に全種類揃っている確率は1-1/e≒63.2%となる（ネイピア数の定義による）。
50%よりやや大きい（半数の人が全種類揃えるための回数より平均回数のほうが多くなる）のは、運のいい人が早く揃えても平均をあまり下げず、運の悪い人がなかなか最後の数個が出てこず平均を上げる分が勝つからである。
「全種類入手するまでの平均回数」の「半分」まで購入した場合に、何種類入手できているか?
問題設定からわかる通りであり、また次の「導出」では具体的に計算するが、入手済みの種類数が増えるにつれて、次の一つを新たに入手するのが難しくなっていく。
コンプガチャが問題になった理由の一つとして、「最初は少額だけ支出するつもりが多額になっていた」事態が起きやすいこともあるのだが、これは「最初のうちに集まりやすいと錯覚する」ということが理由といえる。
後述の「幾何分布の回数の期待値」を用いて、「全種類入手するまでの平均購入数」の半分で何種類集められているか（端数切捨て）を計算すると以下の通りとなる。上記のポスター44種類の例だと、うち39種類集めてもまだ折り返し地点なのである。百里を行くものは九十里を半ばとせよ。
- 全6種類（14.7回）：4種類集めるまでの平均購入数は5.7回
- 全10種類（29.3回）：8種類集めるまでの平均購入数は14.3回
- 全20種類（72.0回）：17種類集めるまでの平均購入数は35.3回
- 全44種類（192.4回）：39種類集めるまでの平均購入数は91.9回
- 全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回引くごとの「まだ持っていないものが出る確率」は pi = (n - i)/n と表せて、
- まだ持っていないものが、1回で出る確率：pi
- まだ持っていないものが、2回目で出る確率：(1 - pi)×pi
- まだ持っていないものが、3回目で出る確率：(1 - pi)2×pi
- まだ持っていないものが、4回目で出る確率：(1 - pi)3×pi
のように回数と対応する（注：「3回目で出る」なら、最初の2回はすでに持っているものが出たわけだから、その回数ぶん(1 - pi)をかける）。なお、この分布は幾何分布とよばれるので、グラフや詳しい挙動を知りたい方はこの名前で調べていただきたい。
幾何分布の回数の期待値は 1/pi であることが知られている。
これは（無限級数であることを除けば）高校の数学Bで扱うテクニックで解けるので示しておく。回数の期待値をAとおくと、
A = 1×pi + 2×(1-pi)×pi + 3×(1-pi)2×pi + 4×(1-pi)3×pi + …
= pi×[1 + 2×(1-pi) + 3×(1-pi)2 + 4×(1-pi)3 + …] ・・・(1)
(1)に(1-pi)をかけると、
(1-pi)A = pi×[1×(1-pi) + 2×(1-pi)2 + 3×(1-pi)3 + …] ・・・(2)
(1)-(2)を計算すると、
piA = pi×[1 + (1-pi) + (1-pi)2 + (1-pi)3 + …]
A = 1 + (1-pi) + (1-pi)2 + (1-pi)3 + …
右辺は無限等比級数なので、A = 1/pi と計算できる。直感的に言えば、確率x (0 < x ≤ 1)の事柄が起こるまでの繰り返し回数の期待値は1/xということで、これはxが単位分数でなくても成り立つというわけだ。
全部集めるまでに、何回必要か?
上記で得た 1/pi は「i種類集めた状態」から次の一つが得られるまでの回数の期待値なので、全部集めるまでの回数の期待値E(N) は、これをi=0～n-1について足せばよいだけである（念の為、ここが単純な足し算でいける理由を確かめたい方は、期待値の線型性について調べてほしい）。よって
E(N) = 1/p0 + 1/p1 + 1/p2 + … + 1/pn-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が十分大きければ、電卓の対数があれば以下の式で簡単に調和数の近似値が得られる。
ここでγはオイラー定数と呼ばれるもので、γ=0.57721566...である。自然対数loge（または ln）はPCの電卓機能にも大抵あるので、総和がめんどくさいならこちらの近似値（のn倍=イ）が便利である。実は約0.5の誤差が出るので後で足すのだが、足せば驚くほど正確である。
種類 n |
ア 期待値 E(N) |
イ アの近似値 n(logen + γ) |
ウ アとイの差 (→0.5) |
エ 調和数 Hn |
オ 自然対数 logen |
カ エとオの差 (→γ) |
|---|---|---|---|---|---|---|
| 6 | 14.70 | 14.21 | 0.486149 | 2.45 | 1.79 | 0.658241 |
| 10 | 29.29 | 28.80 | 0.491675 | 2.93 | 2.30 | 0.626383 |
| 20 | 71.95 | 71.95 | 0.495834 | 3.60 | 3.00 | 0.602007 |
| 50 | 224.96 | 224.46 | 0.498333 | 4.50 | 3.91 | 0.587182 |
| 100 | 518.74 | 518.24 | 0.499167 | 5.19 | 4.61 | 0.582207 |
| 200 | 1175.61 | 1175.21 | 0.499583 | 5.88 | 5.30 | 0.579714 |
| 500 | 3396.41 | 3395.91 | 0.499833 | 6.79 | 6.21 | 0.578215 |
| 1000 | 7485.47 | 7484.97 | 0.499917 | 7.49 | 6.91 | 0.577716 |
| 2000 | 16356.74 | 16356.24 | 0.499958 | 8.18 | 7.60 | 0.577466 |
| 5000 | 45472.54 | 45472.04 | 0.499983 | 9.09 | 8.52 | 0.577316 |
| 10000 | 97876.06 | 97875.56 | 0.499992 | 9.79 | 9.21 | 0.577266 |
（計算プログラム：https://wandbox.org/permlink/HhNdnthIfcI8ylrw）
終わりに
改めて平均回数を求める式をここにおく。先述の0.5を足すことで近似式（=イ+0.5）の誤差は0.01ほどもない。
この E(N) に1回の値段を掛け算すればコンプリートまでにかかる額の目安となる。この手のものに出会ったらまず一度止まって考えてみることをすすめる。むやみに不利な勝負に出ることはない。
もちろんよく考えた上で勝負に出てもいいだろう。運営への好意のお布施ならそれもまたよし。しかしガチャガチャと財布のお金ならばどれくらい費やしたかが実感として分かるものの、電子マネーで気づかぬ間に使いすぎたりしないよう、くれぐれも気を付けていただきたい。月に使う金額を決め家計簿をつけるなどの対策で、支出を抑えよう。
関連項目
- 確率
- 幾何分布
- 調和級数 / オイラーの定数
- ガチャ / コンプリートガチャ
- AKB商法 - 「ポスター全44種類を集めるとイベントに招待」の元ネタ。実際には独占禁止法のおそれがあるとして企画自体が中止されている。
- 15
- 0pt
