クーポンコレクター問題

6面サイコロの全ての目が出るまでにサイコロを平均で何回振る必要があるだろうか。
実は、この問題は、「クーポンコレクター問題」と呼ばれ、コンプガチャ等の問題にも関係がある。
この問題を考えるには、幾何分布や調和数・調和級数、調和平均に関する知識が必要である。

まず最初に、無限等比級数の和から、幾何分布の総和・平均値・分散を求める。
次に、幾何分布のモーメント母関数から、幾何分布の総和・平均値・分散を求める。
続いて、調和数・調和級数や調和平均とは何かを考える。
最後に、これまでの知識を用いて、クーポンコレクター問題について考える。


スクリプトプログラム

n種類のとき、全種類を
揃える為の平均回数は、[回]

幾何分布

ある特定の事象が起こる確率をpとする。
また、余事象が起こる確率をq≡1-pとする。
pが一定のとき、試行は独立であり、ベルヌーイ試行である、という。
ここまでは、二項分布の時と同じ設定である。
今度は、x回目の試行で初めてその事象が起こる場合を考える。
その確率は、次の関数:

で与えられる。この分布を幾何分布(geometrical distribution)の確率密度関数と呼ぶ。

まず最初に、準備として、無限等比級数の和の式:

及び、その両辺をqで微分した式:

及び、さらにその両辺にqを掛けて、qで微分した式:

を計算しておく。

次に、幾何分布の総和と平均を求める。先程の準備において、計算した最初の式と、
第二の式の両辺に、それぞれ確率pを掛けると、

及び、

と計算され、確率の和が1であり、幾何分布の平均値が、
確率pの逆数になることが分かる。

続いて、幾何分布の分散を求める。まず、求める分散であるが、
分布の総和が1であることから、

と式変形できる。即ち、二項分布のところで述べた、
「分散は、『二乗の平均』から『平均の二乗』を引いたものに等しい。」
という性質をここでも用いることが出来るのである。
従って、先程の準備において、計算した第三の式の両辺に、
確率pを掛けると、幾何分布の二乗の平均:

が得られるので、ここから先程求めた平均の二乗を引けば、幾何分布の分散は、

と求められる。

最後に、幾何分布のモーメント母関数を求める。
幾何分布の確率密度関数をモーメント母関数の定義式に代入すると、

を得る。総和は、

であり、平均は、

であり、二乗の平均は、

であるから、これらを代入して、分散:

を得る。

モーメント母関数を用いても、幾何分布の
3次以上のモーメントを導出するのは、煩雑である。
また、二項分布・ポアソン分布・正規分布と比較すると、
3次・4次のモーメントや、歪度・尖度を求める理由は、殆ど無い。
それでも一応、数式処理ソフト「Maxima」を利用して、
これらを計算する為のコマンドラインだけは以下に示しておく。
ここでは、θの代わりにtを用いた。
geometrical : taylor((p*exp(t)/(1-(1-p)*exp(t))),t,0,4);
E0 : coeff(geometrical, t, 0)*0!;
E1 : coeff(geometrical, t, 1)*1!;
E2 : coeff(geometrical, t, 2)*2!;
E3 : coeff(geometrical, t, 3)*3!;
E4 : coeff(geometrical, t, 4)*4!;
V2 : E2-2*E1*E1+E1^2*E0;
V3 : E3-3*E1*E2+3*E1^2*E1-E1^3*E0;
V4 : E4-4*E1*E3+6*E1^2*E2-4*E1^3*E1+E1^4*E0;
SKEW : V3/(sqrt(V2)^3);
KURT : V4/V2^2;




調和数・調和級数

「調和数」とは、1からnまでの自然数の逆数和:

を表すが、これとは別に「オアの調和数」というものがあり、
両者を区別する為に、こちらを「調和級数」或いは、
「調和級数の和」と呼ぶこともあるが、本来は、
Hnにおいて、n→∞とした極限:

を「調和級数」と呼ぶ。無限級数であることを強調する為に、こちらを
「無限調和級数」或いは、「無限調和級数の和」と呼ぶこともあるようだ。
これは、「リーマンのゼータ関数」:

において、s=1とした場合に他ならない。また、その値は、
「無限等比級数の和とテイラー展開」f(x)=ln(1-x)の記事より、

であること、即ち正の無限大に発散することが分かる。




調和平均

我々は、単に「平均」といった場合、一般的には、相加平均(算術平均):

のことを指すことが多いが、平均には、他にも、相乗平均(幾何平均):

や、逆数の相加平均の逆数である「調和平均」:

が存在する。 ここで、先程のn番目の調和数(調和級数)Hnは、
1からnまでの自然数の逆数の「総和」である為、
それらの調和平均の逆数のn倍に等しい。換言すれば、
nHnで割ったものは、1からnまでの調和平均である。」




クーポンコレクター問題

n種類の景品が、等確率で封入されたガチャがあるとする。
また、一般的に、ソーシャルゲームのガチャ等は、店頭のガチャポンとは違って、
それまでに獲得した景品の数量に関係なく、各景品の出現確率に変動はないとする、
「復元抽出」であるので、分布は「幾何分布」に従う、として構わないだろう。

ここでは、既にn種類中k-1種類の景品を獲得しているものとする。
その時、次にk種類目が出る確率pkは、

であり、幾何分布に従うので、k種類目が出るまでに要する
試行回数の期待値は、幾何分布の平均値:

で与えられる。題意は、全n種類が出るまでに要する回数なので、
kを1からnまで足し合わせて、

となるので、求める期待値は、n番目の調和数(調和級数)Hn
n倍で与えられる。換言すれば、
nHnを掛けたものが、n種類のクーポンコレクター問題の解である。」

これは、6面サイコロの全ての目が出るまでにサイコロを平均で何回振る
必要があるか、という問題にも、n=6の場合として、適用できる。
何故なら、サイコロの各目が出る確率は、等確率で一定であり、
ベルヌーイ試行と見なせるからである。因みに、その回数は、

と求められる。

参考程度に、n=20までの逆数、調和数、調和平均、及び、nHnの値を示す。
n 1 / n Hn n / Hn nHn
1 1 1 1 1
2 0.5 1.5 1.333333333 3
3 0.333333333 1.833333333 1.636363636 5.5
4 0.25 2.083333333 1.92 8.333333333
5 0.2 2.283333333 2.189781022 11.41666667
6 0.166666667 2.45 2.448979592 14.7
7 0.142857143 2.592857143 2.699724518 18.15
8 0.125 2.717857143 2.943495401 21.74285714
9 0.111111111 2.828968254 3.181371861 25.46071429
10 0.1 2.928968254 3.414171521 29.28968254
11 0.090909091 3.019877345 3.642532045 33.21865079
12 0.083333333 3.103210678 3.866962718 37.23852814
13 0.076923077 3.180133755 4.087878373 41.34173882
14 0.071428571 3.251562327 4.305622527 45.52187257
15 0.066666667 3.318228993 4.520483677 49.7734349
16 0.0625 3.380728993 4.732707068 54.09166389
17 0.058823529 3.439552523 4.942503389 58.47239288
18 0.055555556 3.495108078 5.150055334 62.91194541
19 0.052631579 3.547739657 5.355522625 67.40705349
20 0.05 3.597739657 5.55904593 71.95479314


Shadow Academy トップへ戻る

inserted by FC2 system