クーポンコレクター問題で、推移行列（※）のn乗を利用することで「全24種の花札デコを、苗26個取得すると何種類の絵柄が手に入るか？」を求められるので、その解析結果とシミュレーションプログラムをまとめてみました。
※全C種類、現在の所持クーポン数 k個のとき、(C+1)次正方行列に
- 列に現在の所持デコ数
- 行に1個デコ化後の所持デコ数
を取り、各セルに推移確率を設定してn乗し、スタート時の所持デコ数にあたる列をとると、n個デコ化後の所持デコ数の確率分布になる
全24種デコの苗を26回取得して手に入る種類数の分布
確率分布
- x軸：26回取得後に手に入れているデコ種類数
- y軸：その確率
16種類前後が多い感じです。
期待値と確率表
確率は小数第3位まで記載しています。変更する場合はシミュレーションプログラムの＃部分をもとに設定可能です。
プログラム
別の場合を試す場合、
Coupon = 24 #デコ種類数
k = 26 #苗取得回数
have = 0 #すでに持っているデコ数
を自由に書き換えてお使いください。
import numpy as np
import matplotlib.pyplot as plt
import math
Coupon = 24 #デコ種類数
k = 26 #苗取得回数
have = 0 #すでに持っているデコ数
A=[0]*(Coupon+1)
for i in range(0,Coupon+1):
A[i] = [0]*(Coupon+1)
for i in range(0,Coupon+1):
for j in range(0,Coupon+1):
if i==j:
A[j][i] = i/Coupon
elif i==j-1:
A[j][i] = (Coupon-i)/Coupon
B = np.linalg.matrix_power(A, k)
x = [i for i in range(Coupon+1)]
y = [0]*(Coupon+1)
print("●全", Coupon,"種、", have,"種入手済、","苗取得", k,"回")
for i in range(0,Coupon+1):
if i >= have:
y[i] = B[i][have]
print()
print("平均：", sum([i*j for (i,j) in zip(x,y)]), "種")
print()
for i in range(0,Coupon+1):
if i >= have:
print(have,"→",i,"種類：",round(100 * B[i][have], 3),"%") #表示する小数点以下の数(3)は要調整
plt.bar(x, y)
plt.xticks(np.arange(0, Coupon+1, step=1))
plt.grid(linestyle="--")
plt.show()
回数とデココンプ達成率の関係について
問：24種類あるデコのうち、せめて約8割である19種類が欲しい（達成率80%）とき、何回くらい苗を取得すればいいか？
答：全24種の1.6倍くらい、つまり38回くらい取得すれば平均で19種ゲットくらいにはなる
一般化にデコ種類数が十分大きい場合、全種類数のk倍集めると達成率は平均1-1/e^k
グラフ
- x軸：全デコ種類数の何倍の個数を集めたか
- y軸：収集率の期待値（＝集まったデコ数 / 全デコ種類数）
確率表
平均で63%集めたいなら24種の1倍、86%集めたいなら2倍の48個の苗取得、3倍で95%
全デコ数が十分大きい場合、全デコ数の1倍は1-1/e≒0.63
2倍は1-1/e^2、3倍は1-1/e^3、k倍は1-1/e^k
に収束する
出力に使ったプログラム
デコ数が大きい場合は近似値1-1/e^xでOK
そうでない場合、24種類の場合は1-(23/24)^24x
import math
import numpy as np
import matplotlib.pyplot as plt
x = np.arange(0, 5.1, 0.1)
y = [1-1/np.e**k for k in x]
plt.xticks(np.arange(0, 5.5, step=0.5))
plt.plot(x, y)
plt.grid(linestyle="--")
plt.show()
for i in x:
print(round(i,1),"倍：",round(100*(1-1/np.e**i),3),"%")
参考：コンプリートまでの期待値計算プログラム
単純に幾何分布の期待値の和をするだけのプログラムです。
プログラム
- 関数：
gsum(k,C)：全C種のデコを手持ちk種からコンプする期待値（0≦k≦C） - 引数：
k：そのデコの手持ち数（0≦k≦C）、C：デコの種類数
#全C種のデコを手持ちk種からコンプする期待値（0≦k≦C）
def gsum(k,C):
a = 0
for i in range (k,C):
a += 1/(C-i)
return C * a
gsum(17,24) #関数の実行。全24種を手持ち17個からコンプする期待値出力結果
gsum(17,24)
：全24種を手持ち17個からコンプする期待値
62.22857142857142
コメント