クーポンコレクター問題の確率分布を解き明かす

クーポンコレクター問題というものをご存知だろうか?これは、例えば6種類のおもちゃが出るガシャポン*1があったとして、何回くらい引けば全種類引き当てる事ができるか?というようなことを考える問題である。

この問題に対して、平均や分散がどうなるかということは非常によく語られることである[1]。また、時として不等式による評価について議論している記事を見かけることもある[2]。

しかし、肝心の確率分布については議論される事が非常に少ない。あまりにも記事を見かけないので、私は当初クーポンコレクター問題の確率分布を求めることは不可能なのではないかとさえ思っていた。

それでもめげずに調べ続けた結果、私はついに確率分布について結論を出しているページを見つけた。本稿ではそれを紹介し、喜びを分かち合いたいと思う。

第2種スターリング数

クーポンコレクター問題の確率分布を求めるためには、第2種スターリング数について理解しておく必要がある。少し長いが、定義をWikipediaから引用する[3]。

第2種スターリング数
第2種スターリング数 (Stirling number of the second kind)  \{{\textstyle {n \atop k}}\}は、 x^{n}を下降階乗冪 x^{\underline {k}}\equiv x\,(x-1)(x-2)\cdots (x-k+1)級数:

 \displaystyle{
x^{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}\,x^{\underline {k}}
}

で展開したときの展開係数として定義される。この定義では、 0\leq k\leq nである。便宜上、 \{{\textstyle {0 \atop 0}}\}=1と定義する。第2種スターリング数は

 \displaystyle{
\left\{{n \atop k}\right\}=\left\{{n-1 \atop k-1}\right\}+k\,\left\{{n-1 \atop k}\right\}
}

なる漸化式で計算できる。

定義も大切なのだが、第2種スターリング数は以下のように特徴付けられるということが重要である[3]。

第2種スターリング数の特徴付け
第2種スターリング数 \{{\textstyle{n \atop k}}\}は、組合せ数学において、番号づけされた n個の要素をグループ k個に分割する組み合わせの数を与える。分割する要素は番号付けされているので個別に区別できるが、グループは順序を特に区別しないものとする。

クーポンコレクター問題の確率分布

準備が整ったので、確率分布を求めてみよう。以下の議論は全て[4][5]を参考にした。

集めるクーポンの種類を k種類とし、初めて全種類のクーポンを取得できるまでの試行回数を表す確率変数を Nとする。この時、 n回目の試行で初めて全種類のクーポンを取得できる確率 P(N = n)を求める。

 n回の試行により出現し得るクーポンの出方の総数は k^nである。もし n回目の試行で初めて全種類のクーポンが出るパターンの総数が分かれば、それを k^nで割ったものが求める確率である。

 n回目の試行で初めて全種類のクーポンが出揃うということは、 n-1回目の時点で k-1種類のクーポンがすでに出ている必要がある。このパターンの総数を求めるために、 n-1回目までの試行に対して1から順に番号を割り振る。そして、これらの番号付けられた試行を k-1個のグループに分ける。同じグループに分けられた試行については同じクーポンが得られたと考える。この分け方のパターンの総数は第2種スターリング数 \{\textstyle{n-1 \atop k-1}\}となる。

第2種スターリング数は分けられたグループの間の順序は区別しないが、今はクーポンの種類は区別されるので、 (k-1)!を掛ける。さらに、 n-1回目までに出る k-1種類のクーポンは k種類のうちどれであるかは問わないので、全てのパターンをカウントする必要がある。そのため、 \left(\textstyle{k \atop k-1}\right) = kを掛ける。結局、 n-1回目の時点で k-1種類のクーポンが出現するパターンの総数は k! \{\textstyle{n-1 \atop k-1}\}となる。

 n回目の試行でまだ出ていない最後のクーポンが出るパターンの総数は1なので、 n回目の試行で初めて全種類のクーポンが出るパターンの総数は k! \{\textstyle{n-1 \atop k-1}\}となる。以上の議論により次の式を得る。

 \displaystyle{
P(N = n) = \frac{k!}{k^n} \{\textstyle{n-1 \atop k-1}\}
}

計算してみよう

 n, kにいくつか具体的な数値を入れて P(N = n)を計算してみよう。手計算ではやっていられないので、pythonを利用する。第2種スターリング数はsympyのstirling関数を用いて計算することが出来るので、それを利用する[6]。数値だけ示しても分かり辛いので、結果をmatplotlibでグラフ化した。Python自体はpydroid3を使って実行した[7]。なお、sympyなどの必要なパッケージはあらかじめpipでインストールしておく必要がある。

計算に用いたソースコードを以下に示す。

from sympy.functions.combinatorial.numbers import stirling
import matplotlib.pyplot as plt
import math

startCouponKind = 2
numCouponKind = 6
numTrial = 30
for k in range(startCouponKind, numCouponKind+1):
  x = []
  y = []
  for n in range(1, numTrial+1):
    stir = stirling(n-1, k-1, kind = 2)
    prob = math.factorial(k) * stir / (k**n)
    x.append(n)
    y.append(prob)
  plt.plot(x, y, label='k = {}'.format(k))
plt.legend()
plt.savefig('/storage/emulated/0/coupon.png')

得られたグラフを以下に示す。

f:id:peng225:20190314084353j:plain

途中でピークを持ち、右側に裾野が広がっている様子が見て取れる。 nが小さいときに確率が0となる領域があるが、これはクーポンの種類よりも試行回数が少ないときの様子が表れているものである。

また、 kの増え方に対して、ピークの位置が右に移動していく速度の方がやや速いように見える。実際、全種類コンプリートするまでの試行回数の期待値は O(k \mathrm{log} k)なので、これは理論的にも辻褄が合っている[1]。

まとめ

本稿ではクーポンコレクター問題の確率分布を明らかにし、実際に計算を行った結果を示した。クーポンコレクター問題ではパターンを数え上げる事が難しかったが、その難しさを既知の概念である第2種スターリング数に押し込めることで、理論的にスッキリとした結論を得ることができた。

これまで組み合わせ数学には興味がなかったが、本稿を書き上げるうちにその面白さを垣間見る事ができた。またいずれ体系的に勉強しよう。

*1:これの呼び方は地方によって差があるような気がするが、自分の流儀で呼ばせて頂く。