ひたすら「畳み込み」!

確率分布の計算には「畳み込み」という操作を使います。ある2つの変数X,Yが確率分布P(X)、P(Y)に従っているときに、変数の合計X+Yの確率分布は

ガチャ_式8

こうなります。この演算をP(X)とP(Y)の「畳み込み」といい、確率分布以外にも科学技術のあらゆる場面で登場します。

ただこの式、いきなり見せられても意味がわかりにくいです。実はワタクシもお恥ずかしながら、実際に計算してみるまでちゃんとした意味がわかっていませんでした。というわけでこの一般式の説明はやめにして、具体的にやってみましょう。

2~3種目をコンプリート

前回「k種までコンプリートしている状態でk+1種目をゲットするまでに要する回数は?」という議論をしました。「畳み込み」の第一歩として、k=1とk=2を考えてみましょう。畳み込みの計算式は以下のようになります。

ガチャ_式9

さて、前回のおさらいですが

P(1, m1)は「1種目をゲットした状態で2種目を当てるのにm1回を要する確率」
P(2, m2)は「2種目をゲットした状態で3種目を当てるのにm2回を要する確率」

です。というわけでこの2つを畳み込んだ式は

「1種目をゲットした状態で2種目と3種目を当てるのに合計k回を要する確率」

という意味になります。これはシグマの中身を見るとわかりやすいかもしれません。P(1,t)P(2,k-t)とは、「2種目をt回でゲットし3種目をk-t回でゲットする確率」という意味です。
つまり合計k回なのですが、合計がk回となる組み合わせは「2種目を1回、3種目をk-1回でゲット」、「2種目を2回、3種目をk-2回でゲット」、・・・「2種目をk-1回、3種目を1回でゲット」まであります。それぞれの確率を合計して(シグマの作業)、「2種目と3種目を合計k回でゲットする確率」を出しているわけです。

さて、この「畳み込み」の計算を実際にやってみると

ガチャ_式10

こんな感じになります。「2種目と3種目を合計k回でゲットする確率」を便宜上、Q(2, k)と表します。
この「畳み込み」の作業をN-1回まで繰り返せば、求める確率の式になります。「そんなのやってられるか!」と言われそうですが、同じノリで何回か計算してみると「規則性」がわかり打ち切るのでご安心を。

2~4種目をコンプリート

Q(2, k)の結果に、さらに「4種目をゲットする確率の式」を畳み込んでみます。

ガチャ_式11

ノリは同じですが、シグマが「t=2」からになっていることにご注意ください。Q(2, t)は「2種目と3種目を合計t回でゲットする確率」ですので、tは2以上です。結果を示すと

ガチャ_式12


こうなります。規則性がぼんやりわかってきましたが、もう1回ぐらいやればハッキリします。

2~5種目をコンプリート
ガチャ_式13

5種目をゲットする確率を畳み込みます(今度はt=3からです)。結果は

ガチャ_式14

ここまでくればもう見えました。実際にワタクシもここまで計算してみて、規則性がわかりました。(ヒマな人は次の行を読まずに規則性を当ててみてください)

全N種をコンプリート!

というわけで、この作業をN-1まで繰り返せば

ガチャ_式15

こう表現できます。これが今回の目標であった

N種すべてをコンプリートするのにk回を要する確率

の式になります(*1種目を当てるのに必要な最初の1回分は便宜上抜いています。よって実際にガチャを引く回数はk+1回です)。
「規則性」を勝手に推測して作った式ですが、ちゃんと「数学的帰納法」によって正しいことを確認しているのでご安心ください(計算めっちゃ大変だったけど!)。シグマの中身は「二項係数」です。

式は一見とんでもなく複雑な式なのですが、具体例を当てはめてみるとそうでもないです。たとえばN=2およびN=3(N=1は1発でコンプリートするので計算する意味ない!)を代入すると

ガチャ_式16

こんな式になります。とくに、最も小さいN=2はすごく意味がわかりやすいと思います。
1種目を当てるための最初の1回は抜いているので、この式は「景品が2種類のとき、2種類目をk回で当てる確率」という意味です。Q(2,1)=1/2、つまり1/2の確率で1発コンプリートです。Q(2, 2)=1/4、つまり1/4の確率で2回かかります。さらに1/8の確率で3回かかり、1/16の確率で4回かかり・・・という具合です。この作業を無限にやっていくと、合計は1となります。確率なのでね。

この式の「期待値」はさっき計算したとおりです(残念ながら、求めた最終式Q(N-1, k)から期待値を計算するのはすごく大変です)。

ガチャ_式7

さて、えぐい?計算が終わりました。次回はラストで、結果を分析してみましょう!



はっぴぃ理系らいふ、いぇい

ヽ(・ε・)人(・ε・)ノ キミモナカマニナロウゼ   

【文責 べじぱみゅ】