クーポンコレクター問題の確率分布を解き明かす
クーポンコレクター問題というものをご存知だろうか?これは、例えば6種類のおもちゃが出るガシャポン*1があったとして、何回くらい引けば全種類引き当てる事ができるか?というようなことを考える問題である。
この問題に対して、平均や分散がどうなるかということは非常によく語られることである[1]。また、時として不等式による評価について議論している記事を見かけることもある[2]。
しかし、肝心の確率分布については議論される事が非常に少ない。あまりにも記事を見かけないので、私は当初クーポンコレクター問題の確率分布を求めることは不可能なのではないかとさえ思っていた。
それでもめげずに調べ続けた結果、私はついに確率分布について結論を出しているページを見つけた。本稿ではそれを紹介し、喜びを分かち合いたいと思う。
第2種スターリング数
クーポンコレクター問題の確率分布を求めるためには、第2種スターリング数について理解しておく必要がある。少し長いが、定義をWikipediaから引用する[3]。
定義も大切なのだが、第2種スターリング数は以下のように特徴付けられるということが重要である[3]。
クーポンコレクター問題の確率分布
準備が整ったので、確率分布を求めてみよう。以下の議論は全て[4][5]を参考にした。
集めるクーポンの種類を種類とし、初めて全種類のクーポンを取得できるまでの試行回数を表す確率変数をとする。この時、回目の試行で初めて全種類のクーポンを取得できる確率を求める。
回の試行により出現し得るクーポンの出方の総数はである。もし回目の試行で初めて全種類のクーポンが出るパターンの総数が分かれば、それをで割ったものが求める確率である。
回目の試行で初めて全種類のクーポンが出揃うということは、回目の時点で種類のクーポンがすでに出ている必要がある。このパターンの総数を求めるために、回目までの試行に対して1から順に番号を割り振る。そして、これらの番号付けられた試行を個のグループに分ける。同じグループに分けられた試行については同じクーポンが得られたと考える。この分け方のパターンの総数は第2種スターリング数となる。
第2種スターリング数は分けられたグループの間の順序は区別しないが、今はクーポンの種類は区別されるので、を掛ける。さらに、回目までに出る種類のクーポンは種類のうちどれであるかは問わないので、全てのパターンをカウントする必要がある。そのため、を掛ける。結局、回目の時点で種類のクーポンが出現するパターンの総数はとなる。
回目の試行でまだ出ていない最後のクーポンが出るパターンの総数は1なので、回目の試行で初めて全種類のクーポンが出るパターンの総数はとなる。以上の議論により次の式を得る。
計算してみよう
にいくつか具体的な数値を入れてを計算してみよう。手計算ではやっていられないので、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')
得られたグラフを以下に示す。
途中でピークを持ち、右側に裾野が広がっている様子が見て取れる。が小さいときに確率が0となる領域があるが、これはクーポンの種類よりも試行回数が少ないときの様子が表れているものである。
また、の増え方に対して、ピークの位置が右に移動していく速度の方がやや速いように見える。実際、全種類コンプリートするまでの試行回数の期待値はなので、これは理論的にも辻褄が合っている[1]。
まとめ
本稿ではクーポンコレクター問題の確率分布を明らかにし、実際に計算を行った結果を示した。クーポンコレクター問題ではパターンを数え上げる事が難しかったが、その難しさを既知の概念である第2種スターリング数に押し込めることで、理論的にスッキリとした結論を得ることができた。
これまで組み合わせ数学には興味がなかったが、本稿を書き上げるうちにその面白さを垣間見る事ができた。またいずれ体系的に勉強しよう。
参考
[1] クーポンコレクター問題 - Wikipedia
[2] コンプガチャの数理 -コンプに必要な期待回数の計算方法について- - doryokujin's blog
[3] スターリング数 - Wikipedia
[4] combinatorics - Probability distribution in the coupon collector's problem - Mathematics Stack Exchange
[5] CDF of probability distribution with replacement - Mathematics Stack Exchange
[6] Combinatorial — SymPy 1.3 documentation
[7] https://play.google.com/store/apps/details%3Fid%3Dru.iiec.pydroid3%26hl%3Dja%26referrer%3Dutm_source%253Dgoogle%2526utm_medium%253Dorganic%2526utm_term%253Dpydroid3%26pcampaignid%3DAPPU_1_5SOHXJe-E4-Pr7wPpLSfwAE
*1:これの呼び方は地方によって差があるような気がするが、自分の流儀で呼ばせて頂く。