直感とのズレ

10種類のシールがランダムに入ったお菓子があるとします。1袋に1枚、どの種類かは買うまでわかりません。10種類すべてを揃えるには、平均して何袋買えばいいでしょうか。

「10種類だから10個」と答えたくなります。しかし実際には約 29.3個 必要です。この差を生むのがクーポンコレクター問題（Coupon Collector's Problem）の本質です。

なぜこれほど多くなるのか、確率の構造から順に追っていきます。

確率を段階に分解する

ポイントは「全部揃えるまでの試行を、段階ごとに分けて考える」ことです。

いま k 種類持っているとします。次に買ったとき、まだ持っていない新しい種類が出る確率は

P(\text{新種が出る} \mid k\text{種類持ち}) = \frac{10 - k}{10}

です。たとえば 0 種類のときは確率 10/10 = 1（何を買っても新種）。9 種類まで揃えたあとは確率 1/10（100種の中の残り1種）になります。

この「新種が出るまで同じ試行を繰り返す」構造は幾何分布（geometric distribution）に従います。成功確率 p の幾何分布では、成功するまでの試行回数の期待値は 1/p です。

したがって、k 種類持っているときに次の新種を引くまでに必要な期待枚数は

E[\text{追加枚数} \mid k\text{種類持ち}] = \frac{10}{10 - k}

10種類のシールを集める各段階で、次の新種を引くまでに必要な期待枚数の棒グラフ

0種類 → 1種類は期待1.00枚、8種類 → 9種類は期待5.00枚、そして9種類 → 10種類はなんと期待10.00枚かかります。後半の「あと1種類が出ない」感覚が数字に表れています。

期待値を合計する

各段階の期待枚数を足し合わせると、全10種類を揃えるまでの総期待枚数が求まります。

E[T] = \frac{10}{10} + \frac{10}{9} + \frac{10}{8} + \cdots + \frac{10}{1}

= 10 \left(\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{10}\right)

= 10 \times H_{10}

ここで H_{10} は調和数（harmonic number）——1/1 + 1/2 + \cdots + 1/n の和です。H_{10} \approx 2.9290 なので

E[T] = 10 \times 2.9290 \approx 29.29\text{ 枚}

直感の「10個」の約3倍です。

一般化と近似

n 種類ある場合の期待値は同じ構造で

E[T] = n \times H_n

n が大きくなると調和数は H_n \approx \ln n + \gamma と近似できます。\gamma はオイラー・マスケローニ定数（Euler–Mascheroni constant）で \gamma \approx 0.5772 です。よって

E[T] \approx n(\ln n + \gamma) \approx n \ln n + 0.5772n

この近似式でいくつかの n を計算すると

種類数 n 期待枚数 E[T]
10 約 29.3
50 約 225
100 約 519
500 約 3,118
1000 約 7,485

n が増えると期待枚数は n \ln n のオーダーで増えていきます。コンプリートガチャで全100種を揃えるには平均519回——これはガチャ課金の設計に直結する数字です。

シミュレーションで確かめる

モンテカルロシミュレーションで実際に確かめます。

import random
import statistics

def simulate_coupon_collector(n: int, trials: int = 100_000) -> list[int]:
    """n 種類を揃えるまでの購入回数を trials 回シミュレートする"""
    results = []
    for _ in range(trials):
        collected = set()
        count = 0
        while len(collected) < n:
            collected.add(random.randint(0, n - 1))
            count += 1
        results.append(count)
    return results

n = 10
data = simulate_coupon_collector(n)

print(f"n={n} のとき")
print(f"  シミュレーション平均: {statistics.mean(data):.2f}")
print(f"  理論値 (n × Hₙ)  : {n * sum(1/k for k in range(1, n+1)):.2f}")
print(f"  標準偏差          : {statistics.stdev(data):.2f}")
print(f"  最大値 (最悪ケース): {max(data)}")

実行すると

n=10 のとき
  シミュレーション平均: 29.29
  理論値 (n × Hₙ)  : 29.29
  標準偏差          : 13.17
  最大値 (最悪ケース): 129

平均は理論値とほぼ一致します。注目すべきは標準偏差が約13という大きさです。

分布の形——平均だけでは語れない

10種類のシールが揃うまでの購入枚数の確率分布。平均29.3枚で右に裾が長い分布を示す

分布を見ると、最頻値は22枚前後ですが右に裾が長く伸びています。平均29.3枚でも、実際には約10%のケースで50枚以上かかります。シミュレーションの最悪ケースが129枚というのもその現れです。

分散の理論値は n^2 \sum_{k=1}^{n} \frac{1}{k^2} - n H_n で、n=10 のとき約174（標準偏差≈13.2）です。

ガチャやコンプリートボーナスの設計では「平均は安い」ように見えても、分布の裾が長いため一定割合のユーザーが平均の2〜3倍以上使ってしまいます。「コンプリートまで最大○○個保証」という天井設計はこの裾の長さへの対処策です。

まとめ

  • 10種類全部を揃えるまでの期待枚数は「10個」ではなく 約29.3個。直感の約3倍。
  • 各段階で「次の新種が出る確率 = (残り種類数)/n」となり、この待ち時間は幾何分布に従う。
  • 段階ごとの期待枚数を足すと E[T] = n \times H_n。n=10 では 10 \times H_{10} \approx 29.29。
  • 一般化すると E[T] \approx n \ln n + 0.5772n（オイラー・マスケローニ定数 \gamma を使った近似）。
  • 標準偏差も大きく（n=10 で約13）、分布の裾が長い。平均だけ見てコストを語ると実態から外れる。
  • ガチャ・福袋・コンプリートボーナスの設計において、この問題は課金額の期待値と分散を直接左右する。

前回の不偏分散の記事で「期待値をとって推定量の性質を調べる」手法を扱いましたが、クーポンコレクター問題でも同じく「段階ごとの期待値を足し合わせる」線形性が中心的な役割を担っています。