「グリモア~私立グリモワール魔法学園~」のメダルチャレンジにおける確率分布 その2

前回の記事: 「グリモア~私立グリモワール魔法学園~」のメダルチャレンジにおける確率分布 その1 - 冷水催眠

記事が完成してたのに1ヶ月放置してしまった……
お久しぶりです。第2回の記事でございます。

前回まではシート数が  2 の場合に絞って計算してきましたが、今回はシート数を  n へと一般化して計算していきます。
計算の手順は前回の記事と全く同じなので、実質的に新しい内容はありません。まとまりのない記事ですが何卒ご容赦くださいませ。

・変数設定

まず、シート枚数を  n\ (\ge 1) とします。そして前回と同様に、各シートを  S_1,\ S_2,\ ...,\ S_n と名付け、各  S_i 内のアイテム数を  g_i とします。
このとき、最終シート(シート  n)の当たりアイテムを引くまでに必要な回数の最小値および最大値はそれぞれ  n 回,  \sum_{i=1}^n g_i 回となります。

また、確率変数  X_i S_i において当たりを引くまでに抽選した回数(当たりを引いた抽選を含む)として定義し、確率変数  X X = \sum_{i=1}^n X_i で定義します。この  X が、最終シートの当たりアイテムを引くまでに必要な回数を表します。

・目標設定

以下、何の断りもなしに変数  i を用いた場合、 i 1,\ 2,\ ...,\ n の値を動くものとします。
ここも前回とほとんど同じ内容なので、詳しい計算の過程は省きます。
 k = n,\ n + 1,\ ...,\ \sum_{i=1}^n g_i に対し、集合  I_k および組み合わせの総数  C_k をそれぞれ

 {
    \displaystyle
    I_k = \left\{ (x_1,\ x_2,\ ...,\ x_n) \in {\bf N}^n\ \middle|\ 1 \le x_i \le g_i\ (\forall i),\ \sum_{i=1}^n x_i = k \right\},
}
 {
    \displaystyle
    C_k = |I_k| =\sum_{i \in I_k} 1
}

で定義すれば、確率  P(X = k)

 {
    \displaystyle
    P(X = k) = \frac{C_k}{g_1 g_2 g_3 \cdots g_n}
}

と書けます。ただし、 {\bf N}自然数全体の集合です。

 g_i は既知の定数なので、 C_k k で表すことを目標とします。

なお、全確率が  1 となることも上の定義から確かめられます。

・Ckを求める準備

 C_k は、定義より「 1 \le x_i \le g_i\ (i = 1,\ 2,\ ...,\ n),\ \sum_{i=1}^n x_i = k を全て満たす自然数の組  (x_1,\ x_2,\ ...,\ x_n) の総数」を意味するので、 C_k

 {
    \displaystyle
    f(x) = \prod_{i=1}^n \left(1 + x + x^2 + ... + x^{g_i - 1} \right)
}

を展開したときの  x^{k - n} の係数になります。この  f(x) を係数を計算しやすい形へ以下のように変形します。ただし  x |x| < 1 を満たしているものとします。

 {
    \displaystyle
    \begin{eqnarray*}
        f(x) &=& \prod_{i=1}^n \frac{1 - x^{g_i}}{1 - x} \\
             &=& \frac{1}{(1-x)^n} \prod_{i=1}^n (1 - x^{g_i}) \\
             &=& \left( \sum_{i=0}^\infty \binom{n+i-1}{n-1} x^i \right) \left( \prod_{i=1}^n (1 - x^{g_i}) \right)
    \end{eqnarray*}
}

ここで、 \binom{n}{r} は二項係数  n \mathrm{C} r = {n!}/(r!(n-r)!) を意味します。また、 {1}/{(1-x)^n}マクローリン展開 \sum_{i=0}^\infty \binom{n+i-1}{n-1} x^i となることを利用しました。


また、 f(x) の各  (\ ) 内をそれぞれ展開したときの係数  a_i,\ b_i,\ c_i

 \displaystyle {
    c_i = \binom{n+i-1}{n-1}, \\
    \prod_{i=1}^n (1 - x^{g_i}) = 1 + a_1 x^{b_1} + a_2 x^{b_2} + ... + a_m x^{b_m}
}

とおきます。上記の式は昇べきの順に並んでいるものとします。すなわち  (i < j \Longrightarrow b_i < b_j) を満たすものとします。)

このとき  f(x)

 {
    \displaystyle
    f(x) = \left( c_0 + c_1 x + c_2 x^2 + ... \right) \left( 1 + a_1 x^{b_1} + a_2 x^{b_2} + ... + a_m x^{b_m} \right)
}

と書けます。これにより、係数の計算が比較的簡単にできるようになります。

・Ckを求める

以上の手続きにより、 C_k の値を場合分けによって求めることが出来ます!*1
ただし、 n - 1 + b_{m+1} \le \sum_{i=1}^n g_i を満たす最大の  m M とおきました。


 {\rm (i)}\ n \le k \le n - 1 + b_1 のとき、

 {
    \displaystyle
    \begin{eqnarray*}
        C_k &=& \left( f(x)\ を展開したときの\ x^{k-n}\ の係数 \right) \\
            &=& \left( \left( \sum_{n=0}^{\infty}{c_n x^n} \right) \cdot 1\ を展開したときの\ x^{k-n}\ の係数 \right) \\
            &=& \left( c_{k-n}x^{k-n}\ の\ x^{k-n}\ の係数 \right) \\
            &=& c_{k-n}.
    \end{eqnarray*}
}


 {\rm (ii)}\ n + b_m \le k \le n - 1 + b_{m+1}\ (m = 1,\ 2,\ ...,\ M) のとき、

 {
    \displaystyle
    \begin{eqnarray*}
        C_k &=& \left( f(x)\ を展開したときの\ x^{k-n}\ の係数 \right) \\
            &=& \left( \left( \sum_{n=0}^{\infty}{c_n x^n} \right) \left(1 + \sum_{j=1}^{m} a_j x^{b_j} \right)\ を展開したときの\ x^{k-n}\ の係数 \right) \\
            &=& \left( \left(c_{k-n}x^{k-n} + \sum_{j=1}^{m} a_j c_{k-n-b_j}x^{k-n-b_j}x^{b_j} \right)\ の\ x^{k-n}\ の係数 \right) \\
            &=& c_{k-n} + \sum_{j=1}^{m} a_j c_{k-n-b_j}.
    \end{eqnarray*}
}


 {\rm (iii)}\ n + b_{M+1} \le k \le \sum_{i=1}^n g_i のとき*2

 {
    \displaystyle
    \begin{eqnarray*}
        C_k &=& \left( f(x)\ を展開したときの\ x^{k-n}\ の係数 \right) \\
            &=& c_{k-n} + \sum_{j=1}^{M+1} a_j c_{k-n-b_j}.
    \end{eqnarray*}
}

・Xの平均

確率変数  X の平均  E(X) は、恐らく

 {
    \displaystyle
    E(X) = \frac{n + \sum_{i=1}^n g_i}{2}
}

となるはずです。 f(x) の定義式から  C_k = C_{(n + \sum_{i=1}^n g_i) - k} が分かりますし、直感的にも納得できる式にはなっているのですが、証明は大変そうなので私はしていません。誰かやって!(丸投げ)

・Xの分散

これ......一般性を保ったまま計算できるんでしょうか......?

・具体例 (g1=120, g2=220, g3=280)

上記の値は、私が実際にゲーム中で利用したメダルチャレンジで用いられていた設定です*3。私はこのメダルチャレンジで136回目にシート3の当たりアイテムを獲得しました。そこで、この設定のメダルチャレンジにおいて、136回以内にシート3の当たりアイテムを獲得する確率を計算してみます。また、平均と分散も求めてみます。求めるのを忘れていました。いつか追記します。

例によって  n = 3,\ g_1 = 120,\ g_2 = 220,\ g_3 = 280 とおきます。このとき、

 {
    \displaystyle
    \sum_{i=1}^n g_i = 620,\ \prod_{i=1}^n g_i = 7392000
}

となります。また、

 {
    \displaystyle
    \begin{eqnarray*}
        f(x) &=& \prod_{i=1}^n \left(1 + x + x^2 + ... + x^{g_i - 1} \right) \\
             &=& \left(1 + x + x^2 + ... + x^{119} \right)\left(1 + x + x^2 + ... + x^{219} \right) \\
             & & \ \ \ \ \left(1 + x + x^2 + ... + x^{279} \right)
    \end{eqnarray*}
}

とおくと、 |x| < 1 の範囲において

 {
    \displaystyle
    \begin{eqnarray*}
        f(x) &=& \frac{1}{(1 - x)^3}(1 - x^{120})(1 - x^{220})(1 - x^{280}) \\
             &=& \left(c_0 + c_1 x + c_2 x^2 + ... \right) \\
             & & \ \ \ \ \left(1 - x^{120} - x^{220} - x^{280} + x^{340} + x^{400} + x^{500} - x^{620} \right)
    \end{eqnarray*}
}

と書けます。ただし、 c_i = \binom{2+i}{2} = (i+1)(i+2) / 2 とおきました。

よって、次のように  C_k の値、および  P(X = k) が求まります。

 {
    \displaystyle 
    \left\{
        \begin{eqnarray*}
            3 \le k \le 122  \ &\Longrightarrow&\ C_k = c_{k - 3} = (k - 1)(k - 2) / 2 \\
            123 \le k \le 222\ &\Longrightarrow&\ C_k = c_{k - 3} - c_{k - 123} = (\text{式1}) \\
            223 \le k \le 282\ &\Longrightarrow&\ C_k = (\text{式1}) - c_{k - 223} = (\text{式2}) \\
            283 \le k \le 342\ &\Longrightarrow&\ C_k = (\text{式2}) - c_{k - 283} = (\text{式3}) \\
            343 \le k \le 402\ &\Longrightarrow&\ C_k = (\text{式3}) + c_{k - 343} = (\text{式4}) \\
            403 \le k \le 502\ &\Longrightarrow&\ C_k = (\text{式4}) + c_{k - 403} = (\text{式5}) \\
            503 \le k \le 620\ &\Longrightarrow&\ C_k = (\text{式5}) + c_{k - 503} = (\text{式6}),
        \end{eqnarray*}
    \right. \\
}
 {
    \displaystyle 
    \left\{
        \begin{eqnarray*}
            \ (\text{式1}) &=& 120 k - 7380 \\
            \ (\text{式2}) &=& -\frac{1}{2} k^2+\frac{683}{2} k-31911 \\
            \ (\text{式3}) &=& -k^2+623k-71532 \\
            \ (\text{式4}) &=& -\frac{1}{2} k^2+\frac{563}{2} k-13221 \\
            \ (\text{式5}) &=& -120k+67380 \\
            \ (\text{式6}) &=& \frac{1}{2} k^2-\frac{1243}{2} k+193131,
        \end{eqnarray*}
    \right. \\
    P(X = k) = 
        \begin{cases}
            C_k\ /\ 7392000 \ \ & (k = 3,\ 4,\ ...,\ 620) \\
            0 & ({\rm otherwise}).
        \end{cases}
}

これを用いて、136回以内にシート3の当たりアイテムを獲得する確率を次のように計算できます。

 {
    \displaystyle 
    \begin{eqnarray*}
        P(X \le 136) &=& \frac{1}{7392000} \left( \sum_{k=3}^{122} \frac{(k - 1)(k - 2)}{2} + \sum_{k=123}^{136} \left( 120 k - 7380 \right) \right) \\
                     &=& \frac{409480}{7392000} \approx 5.54 \%.
    \end{eqnarray*}
}

ちなみに  (\text{式6}) から  c_{k - 623} を引けば、式はしっかり  0 になってくれます。
また、下の [図1] が  X の確率分布の曲線です!きれい!グリモア分布とでも呼びたいくらいきれい!以上!おしまい!


f:id:hge:20171216003040p:plain

[図 1]




*1:前回の場合分けにも当てはまる話ですが、この場合分けは計算において無駄な高次の項を削るためのものであり、本質的に意味を持ちません。f(x)をそのまま展開しても値は手に入ります。

*2: n - 1 + b_{M+1} = \sum_{i=1}^n g_i を満たす場合、この場合分けは不要です。

*3:2016年11月17日ごろ