N種類出るくじをk回引いた時全種類入手できる確率

0.問題定義

1. 回数の期待値と分散

まずは、「平均で何回引けばN種類すべて入手できるのか。また、その回数のばらつきはどれくらいか。」を知りたい。ここでいう平均とは、たくさんの人が全種類入手しようと思ってこのくじ引きをするとき、a回で入手できる人、b回で入手できる人などさまざまだろうが、それらをすべて平均したら何回となるのか、という意味である。

これについては全種類の景品を集めるのに必要な回数の期待値(分析ノート:データサイエンティストのメモ書き)の記事がわかりやすい。そこにある結論を述べれば、平均E(N)と分散V(N)はそれぞれ

n = 4

sum = 0.0
for k in range(1,n+1):
    sum += 1.0/k
print( "E = %f" % (n * sum) )

sum = 0.0
for k in range( 1,n ):
    sum += k / (n - k ) ** 2
print( "V = %f" % (n * sum) )    

2. k回目を引いた時点で全種類入手となっている確率

まず、p種類入手できていて次に1回引くとき起きうる状況について、図1に示す。

図1 p種類入手できていて、次に1回引くとき起きること

図1において、「p種類入手できているようなここまでの引きパターンの総数」はまだ具体的にはわからないから、仮にu通りあったとしている。さて、図1が示しているのは、この状況で1回引くと次のどちらかが起きる、ということである。

• まだ持っていないものを新たに引く。この引き方は(N-p)通りある。この場合、入手済の種類の数は1増えてp+1種類となる。したがって「p+1種類入手済の引きパターンの総数が、u・(N-p)通り増える」ことになる。
• すでに持っているものを再び引く。この引き方はp通りある。この場合、入手済の種類の数はp種類のままである。したがって「p種類入手済の引きパターンの総数が、u・p通り増える」ことになる。

図2 p種類入手済(pは1からN)の引きパターン総数uが、くじを引くたびにそれぞれ増加していく様子

#
# n_lottery_probability.py
#
# by zhuo  2023.04.15

import numpy as np

N = 4
upto = 30

#### initialization

## initial values of u
u = np.zeros( N, dtype=float )
u[0] = 1.0

## initial values of the matrix A
A = np.zeros( (N,N), dtype=float )
for i in range( 0, N ):
    A[i][i] = float(i+1)
for i in range( 0, N-1 ):
    A[i+1][i] = float(N-1-i)

#### calculation
nall = 1.0
for j in range( 0, upto ):
    print( "%2d\t%f" % ( j+1, u[-1]/nall ) )
    u = A @ u
    nall *= float(N)

グラフ1:　2種類から8種類までのランダムくじをコンプする確率のグラフ

• この計算・グラフ表示を行うpython codeはこちらである:　n_lottery_probability_plots.py
• 上記を実行して得られる確率をtab separate fileに納めたのがこちらである:　probs.tsv