クーポンコレクター問題の拡張とその確率分布

以前、クーポンコレクター問題の確率分布について調べたことがある (詳細はこちら) 。これはこれで大きな成果だったのだが、いざこれを実用しようと思うと、少々物足りないことに気づいた。

例えば、6種類のクーポンを全て集めることを考える。以前求めた確率分布では、クーポンを集め始める前の時点における確率を考えることはできる。しかし、実際にクーポンが揃っていく速さはその時々であり、例えば途中で早々に2種類集まった場合、そこからどれくらいの確率で残り4つのクーポンが集まるのかを知りたくなる。

つまり、知りたいのは $k$ 種類のクーポンのうちすでに $l$ 種類のクーポンを取得している状況で、残りの $k-l$ 種類のクーポンを集めるために必要な試行回数の確率分布はどうなるのか？ということである。本稿ではこの疑問に対する回答について述べる。

考え方の方針

$n$ 回の試行で出現し得るクーポンの出方の総数は $k^n$ となる。そのため、すでに $l$ 種類のクーポンを持っている状態から始めて、ちょうど $n$ 回で全てのクーポンが揃うパターンの総数が分かれば確率が分かる。

考えを整理するために、いくつか場合分けをしてパターンを数え上げてみよう。以下ではクーポンは全部で $k$ 種類あり、そのうちすでに $l$ 種類のクーポンを持っているとする。

$n < k-l$ のとき

残りのクーポンの数より小さい試行回数でクーポンが集まることはあり得ないので、このケースは0通りである。

$n = k-l$ のとき

それぞれの試行で未取得のクーポンが毎回ダブリなく出る必要がある。このケースは残りのクーポンの並び替えの総数と等しく、 $(k-l)!$ 通りとなる。

$k-l < n \le k$ のとき

ここが山場である。このパターンでちょうど $n$ 回目にクーポンが全て集まるためには、 $n-1$ 回目までに $k-1$ 個のクーポンが出尽くしている必要がある。試行回数が残りのクーポンの数よりも多いため、最初の時点で持っているクーポンが出ることもあり得る。それも加味すると、 $n-1$ 回目までに出るクーポンは $k-l-1$ 種類以上、 $n-1$ 種類以下となる。

最初に持っている $l$ 種類のクーポンのうち $i$ 種類のクーポンが出るとすると、 $n-1$ 回目までには $k-l-1+i$ 種類のクーポンが出ることになる。

それぞれの試行に番号を付けて、これを $k-l-1+i$ 個の区別された箱に分類しているのだと考えると、このパターンの総数は以下のように第二種スターリング数を用いて書ける。

$\displaystyle{ \left(\textstyle{k-l \atop k-l-1}\right) \left(\textstyle{l \atop i}\right) (k-l-1+i)! \{\textstyle{n-1 \atop k-l-1+i}\} }$

第二種スターリング数自体は区別のない箱への分類の総数を表しているので、 $(k-l-1+i)!$ を掛けていることに注意されたい。また、すでに持っているクーポンから $i$ 種類のクーポンを選ぶ方法には自由度がある。同様に、未取得のクーポンから $k-l-1$ 種類のクーポンを選ぶ方法にも自由度がある。そのため、さらに $\left(\textstyle{k-l \atop k-l-1}\right) \left(\textstyle{l \atop i}\right)$ を掛けている。

$0 \le i \le n-k+l$ より、 $i$ による総和を取れば、求めるパターンの総数は以下のようになる。

$\displaystyle{ \sum_{i=0}^{n-k+l} \left(\textstyle{k-l \atop k-l-1}\right) \left(\textstyle{l \atop i}\right) (k-l-1+i)! \{\textstyle{n-1 \atop k-l-1+i}\} }$

クーポンの出方の例: $k=6, l=3, n=5$

この場合、 $0 \le i \le 2$ である。それぞれの $i$ についてクーポンの出方の具体例を見てみよう。

ここでは6種類のクーポンをAからFのアルファベットで表す。また、最初の時点ですでにA, B, Cの3つのクーポンを持っているとする。

・ $i=0$

すでに持っているクーポンは1種類も出ないため、以下のようなクーポンの出方となる。

D F F F E

・ $i=1$

すでに持っているクーポンは1種類だけ出るため、以下のようなクーポンの出方となる。

D A F A E

・ $i=2$

すでに持っているクーポンは2種類だけ出るため、以下のようなクーポンの出方となる。

B F A D E

$k < n$ のとき

これは1つ前のケースとほぼ同様である。ただし、 $n-1$ 回目までに出るクーポンは $k-l-1$ 種類以上、 $k-1$ 種類以下となる。ゆえに $0 \le i \le l$ となる。これより、このパターンの総数は以下のようになる。

$\displaystyle{ \sum_{i=0}^{l} \left(\textstyle{k-l \atop k-l-1}\right) \left(\textstyle{l \atop i}\right) (k-l-1+i)! \{\textstyle{n-1 \atop k-l-1+i}\} }$

クーポンの出方の例: $k=6, l=3, n=8$

この場合、 $0 \le i \le 3$ である。それぞれの $i$ についてクーポンの出方の具体例を見てみよう。

ここでも6種類のクーポンをAからFのアルファベットで表し、最初からA, B, Cの3つのクーポンを持っているとする。

・ $i=0$

すでに持っているクーポンは1種類も出ないため、以下のようなクーポンの出方となる。

D F F F D D F E

・ $i=1$

すでに持っているクーポンは1種類だけ出るため、以下のようなクーポンの出方となる。

D A F A A F D E

・ $i=2$

すでに持っているクーポンは2種類だけ出るため、以下のようなクーポンの出方となる。

B F F A D A B E

・ $i=3$

すでに持っているクーポンは3種類全て出るため、以下のようなクーポンの出方となる。

B F F C D A B E

4つのケースをまとめる

実は前述の4つのケースは以下のように一本の式にまとめられる。

$\displaystyle{ \sum_{i=0}^{\mathrm{min}(n-k+l, l)} \left(\textstyle{k-l \atop k-l-1}\right) \left(\textstyle{l \atop i}\right) (k-l-1+i)! \{\textstyle{n-1 \atop k-l-1+i}\} }$

これを $k^n$ で割れば求める確率分布が得られる。

$\displaystyle{ P(N = n) = \sum_{i=0}^{\mathrm{min}(n-k+l, l)} \frac{\left(\textstyle{k-l \atop k-l-1}\right) \left(\textstyle{l \atop i}\right) (k-l-1+i)! \{\textstyle{n-1 \atop k-l-1+i}\}}{k^n} }$

ただし、 $N$ はクーポンが全て集まるまでに必要な試行回数を表す確率変数であるとする。

計算してみよう

確率分布

前回同様、今回もpythonを使用して確率分布を計算してグラフを描いてみた。パラメータが多いので $k$ の値は6固定とした。ソースコードを以下に示す。

#!/usr/bin/python3.6
from sympy.functions.combinatorial.numbers import stirling
from sympy.functions.combinatorial.numbers import nC
import matplotlib.pyplot as plt
import math

def coupon(k, l, n):
    loopNum = min(n-k+l, l)+1

    numPattern = 0
    for i in range(loopNum):
        stir = stirling(n-1, k-l-1+i, kind=2)
        numPattern += (k-l) * nC(l, i) * math.factorial(k-l-1+i) * stir
    return float(numPattern) / k**n

def main():
    numCouponKind = 6
    numTrial = 30
    for l in range(0, numCouponKind):
        x = []
        y = []
        for n in range(1, numTrial+1):
            prob = coupon(numCouponKind, l, n)
            x.append(n)
            y.append(prob)
        plt.plot(x, y, label='l = {}'.format(l))
    plt.legend()
    plt.grid()
    plt.xlabel("n")
    plt.ylabel("probability")
    plt.savefig('coupon_lx_k6.png')
    #plt.show()

if __name__ == "__main__":
    main()

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

f:id:peng225:20210116010347p:plain — 6種類のクーポンのうちすでにl種類のクーポンを持っている場合の確率分布

$l$ が大きいほど分布が左に偏っており (つまり右に歪んでおり) 、最初に持っているクーポンが多ければ多いほど少ない試行回数でクーポンを全て収集できることが分かる。

累積分布

これまでの議論で確率分布は分かった。しかし、実際に自分がどれくらい試行を重ねればクーポンを揃えられるかというのは、累積分布を見た方が分かりやすいだろう。

私が日常生活で良く考えたくなるのは $k=3, 6$ のケースなので*1、これらについて累積分布関数の値がそれぞれ0.5, 0.9, 0.95以上になるために必要な試行回数を $l$ の値毎に示す。

・ $k=3$

l	累積0.5	累積0.9	累積0.95
0	5	9	11
1	4	8	10
2	2	6	8

・ $k=6$

l	累積0.5	累積0.9	累積0.95
0	13	23	27
1	12	22	26
2	11	21	24
3	10	19	23
4	7	17	21
5	4	13	17

クーポンを確実に集めるためには、思ったより多くの試行が必要という印象を受けた。クーポン集めは最後の方が異常にしんどいので、 $l$ が多少大きくても焼け石に水という感じだということも分かった。

まとめ

本稿ではクーポンコレクター問題の拡張として、最初からいくつかのクーポンを持っている状態でクーポンを全て集める際の試行回数について考えた。クーポンを確実に集めるために必要な試行回数は思いのほか大きく、クーポンを真面目に集めることがいかに厳しいことであるかを肌で感じた。

今後の人生で何かを集めたくなったら、大人しくメル○リを利用した方が良いかもしれない。

*1:子どものためにハッピーセットのおもちゃを集めることがある。