お菓子の袋に入っているシールを集めたことがあるなら、最初は袋を開けるたびに新しいシールが出てきて、すぐに全部そろいそうだと思った記憶があるでしょう。ところが、アルバムがほぼ埋まる頃からは、すでに持っているシールばかりが出てきて、最後の1、2枚はなかなか出てきません。運が悪いからではなく、確率がもともとそのように動くからです。この現象を数学で解き明かしたのが「クーポンコレクター問題（Coupon Collector’s Problem）」です。
クーポンコレクター問題とは、簡単に言えば「いくつかの種類の中から1つがランダムに出るとき、すべての種類を少なくとも1回ずつ集めるには平均何回引く必要があるか」を問う確率の問題のことです。答えが思ったよりはるかに大きく、そのほとんどが最後の数種類を待つことに費やされるという点がポイントです。
本記事では、クーポンコレクター問題とは何かから、平均回数を計算する仕組み、数字で見る具体例、そしてこの問題が日常生活や技術で使われる場面と注意点まで、順に見ていきます。
最後の1枚がいちばん高くつく、クーポンコレクター問題
クーポンコレクター問題とは何か
この問題の名前は、シリアルの箱に1枚ずつクーポンを入れ、すべての種類を集めると景品をもらえる販売促進キャンペーンに由来します。数学的には、次のような条件を置きます。
(1) 種類の数が決まっている
集めるべきクーポンは全部で n 種類あり、収集者はこの数をあらかじめ知っています。
(2) 1回に1枚ずつランダムに出る
箱を1つ買うたびに n 種類のうち1つが同じ確率で出て、前に何が出たかは次の結果に影響しません。
(3) 重複が生じる
すでに持っているクーポンが再び出ることがあります。同じクーポンを何度も受け取ることこそが、収集を長引かせる原因です。
サイコロに置き換えると、「6つの面がすべて1回ずつ出るまで、サイコロを平均何回振ればよいか」という問いと同じです。
平均回数はどう計算するのか
収集の過程を「新しい種類を1つ手に入れるまで」の区間に分けて考えると、計算が簡単になります。
(1) 最初は何でも新しい
何も持っていないときは、最初の1回は必ず新しい種類なので、1回で十分です。
(2) 集めるほど新しいものが出る確率は下がる
すでに k 種類を持っているなら、新しい種類が出る確率は (n – k) / n です。成功確率が p の試行を成功するまで繰り返すと平均 1 / p 回かかるので、この区間には平均 n / (n – k) 回が必要です。
(3) 区間をすべて足し合わせる
各区間の平均を足すと、全体の平均は n × (1 + 1/2 + 1/3 + … + 1/n) になります。かっこ内の和は調和数と呼ばれ、n が大きくなると、おおよそ n × (n の自然対数) + 0.577 × n 程度に増えていきます。フランスの数学者ピエール＝シモン・ラプラス（Pierre-Simon Laplace）も、1812年の確率論の著作でこの問題を扱いました。
サイコロで実際に考えてみると分かりやすいです。平均すると、最初の面は1回、2つ目の新しい面は6/5回、3つ目は6/4回、4つ目は6/3回、5つ目は6/2回、最後の6つ目は6/1回かかります。これをすべて足すと約14.7回になり、そのうち最後の1面を待つだけで平均6回がかかります。
この式から分かるように、最後の区間、つまりちょうど1種類だけが残ったときは、それだけで平均 n 回待たなければなりません。すでに集めた種類が多いほど新しいものに出会いにくくなるという構造が、収集期間を長く引き延ばしているのです。
数字で見る収集の現実
計算結果を具体的な数字で見ると、直感とどれほど違うかがはっきりします。
- サイコロ（Die）：先ほど計算したとおり、6つの面をすべて見るには平均約14.7回振る必要があります。6回で済みそうに思えますが、その2倍以上です。
- クーポン10種類（Ten Coupons）：平均約29.3回が必要です。
- クーポン50種類（Fifty Coupons）：平均約225回が必要です。そのうち最初の25種類を集めるには約34回で済みますが、残りの25種類を集めるには約191回かかります。
- クーポン100種類（One Hundred Coupons）：平均約519回で、種類の数の5倍を超えます。
ここで挙げた数字はあくまで平均なので、実際にははるかに長くかかる人も多くいます。また、一部の種類をわざと少なく入れた「レアカード」がある場合は、すべての種類が同じ確率のときよりも期待回数はさらに大きくなります。
クーポンコレクター問題が使われる場面と注意点
この問題はシールアルバムにとどまらず、さまざまな分野で使われています。
(1) 販売促進と消費の設計
ランダムに出るコレクション型の商品は、最後の数種類を手に入れるために同じ商品を繰り返し買わせる仕組みになっています。消費者の立場からは、期待費用をあらかじめ計算してみるだけでも衝動買いを減らすことができます。
(2) コンピューターサイエンスとアルゴリズム
ランダムに選んだ要素がすべての場合を1回ずつ経るまでにかかる時間を見積もるときにこの計算が使われ、乱択アルゴリズムの教科書では代表的な例題として扱われます。
(3) 交換が答えになり得る
複数の人で一緒に集めて重複したものを互いに交換すれば、1人で集めるときよりも1人あたりが買う量は大きく減ります。自分にとって余った重複品が、ほかの人にとっては必要な1枚になるからです。
(4) 残りの回数を見積もる目安
すでにいくつかの種類を集めているなら、残りの種類についてだけ同じ方法で計算すればよいのです。たとえば50種類のうち49種類を集めたなら、最後の1枚を手に入れるまでに平均50回さらに引く必要があるということです。
ただし、実際の商品は種類ごとに出る割合が異なったり公開されていなかったりすることが多いため、計算はあくまで出発点と考えるべきです。
クーポンコレクター問題は、集めれば集めるほど新しいものを手に入れにくくなるという単純な事実が、どれほど大きな差を生むかを示しています。最後の1枚がなかなか出ないのは不運ではなく、確率が定めた道筋なのです。
収集を始める前に、何回ぐらい必要になりそうか一度計算してみて、重複を分け合える友達を探してみること、それが賢い収集への第一歩です。
