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

お久しぶりです。ほげでございます。

スマートフォンのアプリゲーム「グリモア」では頻繁にイベントが開催されており、主な報酬の形としてランキング報酬の他にメダルチャレンジというものが存在します。
メダルチャレンジとは、イベント中で特定の条件を満たすと獲得できる「メダル」を一定数消費することで引くことのできるクジ引きシステムです。
以下、クジを引くことを抽選と呼ぶことにします。

メダルチャレンジの概要

メダルチャレンジには最大5つの"シート"(クジ引き箱に相当する)が存在し、各シートに多数のアイテム(クジ)が入っています。
1回の抽選で獲得できるアイテムは1つで、獲得したアイテムはそのシートから消滅します。すなわち、100個のアイテムが存在するシートでは最大100回の抽選をすることができます。以下、 n 番目のシートをシート  n と表記します。

1回目の抽選ではシート  1 からしか引くことが出来ません。
しかし、各シートには "当たり" アイテムが唯1つ存在し、シート  1 における抽選で当たりアイテムを獲得すると、抽選するシートを任意のタイミングでシート  2 へ切り替えることが可能になります。
この際、シート  1 で抽選し続けることもできますが、シート  1 のアイテムが無くなり次第、自動的に抽選はシート  2 へ切り替わります。

同様に、シート  2 において唯一の当たりアイテムを獲得するかアイテムを引き切ると、シート  3 への移行が可能になります。
なお、最終シートの当たりアイテムを獲得して移行を実行したとき、シート  1 へ戻ることはなく、再び全アイテムの復活した最終シートを引くことになります。

シート制覇に必要な抽選回数の確率分布(シート: 2枚)

・変数設定

ここからは、メダルチャレンジにおいて最終シートの当たりアイテムを獲得するまでに必要な回数の確率分布を考察していきます。

一般的な話をする前に、まずは仮にシート枚数を  2とし、それぞれ  S_1,\ S_2 と名付けます。また、それぞれのシート内のアイテム数を  g_1,\ g_2 とします。
このとき、最終シート(シート  2 )の当たりアイテムを引くまでに必要な回数の最小値、最大値はそれぞれ  2 回,  g_1+g_2 回となります。
前者は  S_1,\ S_2 共に一発で当たりアイテムを引き当てた場合、後者は  S_1,\ S_2 両方で最後に当たりアイテムを引き当てた場合です。

ここで、確率変数  X_1,\ X_2 をそれぞれ  S_1,\ S_2 において当たりを引くまでに抽選した回数として定義し、 X = X_1 + X_2 とします。また、 P を確率とし、 P(X_1 = x_1 \land X_2 = x_2) P(x_1,\ x_2) と略記します。この記事ではこの  X の確率分布を求めていきます。

なおここでは単純化のため、抽選で当たりを引いたときは直ちに次のシートへ切り替えることとします。

・目標設定

目標は、確率  P(X = k) k を用いて表すことです。 P(X = k) は、最終シートの当たりアイテムを  k 回目で獲得する確率を表し、 k は前述の通り  (2 \le k \le g_1+g_2) を満たします。
この求めたい確率を単純に式に表すと、

 {
    \displaystyle
    \begin{eqnarray*}
        P(X = k) &=& P(X_1 + X_2 = k) \\
                 &=& \sum_{\substack{1 \le x_1 \le g_1 \\ 1 \le x_2 \le g_2 \\ x_1 + x_2 = k}}P(x_1,\ x_2)
    \end{eqnarray*}
}

となります。

この  P(x_1,\ x_2) は、 S_1 において  x_1 回目に当たりアイテムを引き、 S_2 において  x_2 回目に当たりアイテムを引く確率を表しますが、この確率は  k に依存しない定数になります。実際、

 {
    \displaystyle
    \begin{eqnarray*}
        P(x_1,\ x_2) &=& P(X_1 = x_1 \land X_2 = x_2) \\
                     &=& \frac{g_1-1}{g_1} \frac{g_1-2}{g_1-1} \cdots \frac{g_1-(x_1-1)}{g_1-(x_1-2)} \frac{1}{g_1-(x_1-1)} \cdot \\
                     & & \ \ \frac{g_2-1}{g_2} \frac{g_2-2}{g_2-1} \cdots \frac{g_2-(x_2-1)}{g_2-(x_2-2)} \frac{1}{g_2-(x_2-1)} \\
                     &=& \frac{1}{g_1 g_2}
    \end{eqnarray*}
}

であるから、各  k = 2,\ 3,\ ...,\ g_1+g_2 に対し、

 {
    \displaystyle
    C_k = \sum_{\substack{1 \le x_1 \le g_1 \\ 1 \le x_2 \le g_2 \\ x_1 + x_2 = k}} 1
}

とおけば、

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

と書けます。 g_1,\ g_2 は既知の定数なので、 C_k k で表すことができれば  P(X) の確率分布を知ることができますね。

・全確率

ここで、 P(X) の全確率が  1 になることを確認しておきます。
これは  \sum_{k = 2}^{g_1 + g_2} {C_k}/{(g_1 g_2)} = 1 が成り立つことで確認できますが、

 {
    \displaystyle
    \begin{eqnarray*}
       \sum_{k = 2}^{g_1 + g_2} C_k &=& \sum_{k = 2}^{g_1 + g_2} \sum_{\substack{1 \le x_1 \le g_1 \\ 1 \le x_2 \le g_2 \\ x_1 + x_2 = k}} 1 \\
                                    &=& \sum_{\substack{1 \le x_1 \le g_1 \\ 1 \le x_2 \le g_2}} 1 \\
                                    &=& g_1 g_2
    \end{eqnarray*}
}

となるので、確かに全確率は  1 になっています。

・Ckを求める

 C_k は、定義より「 1 \le x_1 \le g_1,\ 1 \le x_2 \le g_2,\ x_1 + x_2 = k を全て満たす自然数の組  (x_1,\ x_2) の総数」を意味しますが、これを「 0 \le x_1 \le g_1 - 1,\  0 \le x_2 \le g_2 - 1,\  x_1 + x_2 = k - 2 を全て満たす整数の組  (x_1,\ x_2) の総数」と読み替えます。

これはさらに、「ある物質  x_1,\ x_2 があり、 x_1 g_1 - 1 個、 x_2 g_2 - 1 個入っている箱の中から  k - 2 個取り出すときの個数の組み合わせの総数」とも読み替えることができます。

よって、 C_k

 
    f(x) = \left(1 + x + x^2 + ... + x^{g_1 - 1} \right) \left(1 + x + x^2 + ... + x^{g_2 - 1} \right)

を展開したときの  x^{k - 2} の係数になります。

このまま展開しても良いですが、今後シート数を一般化することや、 C_k k の閉じた式で表したいということを踏まえて、計算しやすい形へ  f(x) を式変形します。

まず、

 
    \displaystyle
    \begin{eqnarray*}
        f(x) &=& \frac{1-x^{g_1}}{1-x} \frac{1-x^{g_2}}{1-x} \\
             &=& \frac{1}{(1-x)^2} (1-x^{g_1})(1-x^{g_2})\ \ \ (|x| < 1)
    \end{eqnarray*}

であり、 1/(1-x)^2マクローリン展開

 {
    \displaystyle
    \frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + ...
}

です。よって、 a_n = n + 1 とおけば、 f(x) |x| < 1 の範囲で

 {
    \displaystyle
    \begin{eqnarray*}
        f(x) &=& \left( \sum_{n=0}^{\infty}{a_n x^n} \right) (1-x^{g_1})(1-x^{g_2}) \\
             &=& \left( \sum_{n=0}^{\infty}{a_n x^n} \right) (1 - x^{g_1} - x^{g_2} + x^{g_1 + g_2})
    \end{eqnarray*}
}

と変形できます。ここまで来れば、 x^{k - 2} の係数の計算は容易です。

・具体例 (g1=5, g2=7)

ここからは具体例として  g_1 = 5,\ g_2 = 7 を与え、 C_k の値を求めます。

これらの値を上の式へ代入すると、

 {
    \displaystyle
    \begin{eqnarray*}
        f(x) &=& \left( \sum_{n=0}^{\infty}{a_n x^n} \right) (1-x^5)(1-x^7) \\
             &=& \left( \sum_{n=0}^{\infty}{a_n x^n} \right) (1 - x^5 - x^7 + x^{12})
    \end{eqnarray*}
}

が得られます。よって、 C_k の値は以下のように3つの場合分けで計算できます。


 {\rm (i)}\ 0 \le k - 2 \lt 5 、すなわち  k = 2,\ 3,\ 4,\ 5,\ 6 のとき、

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


 {\rm (ii)}\ 5 \le k - 2 \lt 7 、すなわち  k = 7,\ 8 のとき、

 {
    \displaystyle
    \begin{eqnarray*}
        C_k &=& \left( f(x)\ を展開したときの\ x^{k-2}\ の係数 \right) \\
            &=& \left( \left( \sum_{n=0}^{12}{a_n x^n} \right)(1 - x^5)\ を展開したときの\ x^{k-2}\ の係数 \right) \\
            &=& \left( (a_{k-2}x^{k-2}-a_{k-7}x^{k-7}x^5)\ の\ x^{k-2}\ の係数 \right) \\
            &=& a_{k-2} - a_{k-7} \\
            &=& (k - 1) - (k - 6) \\
            &=& 5. \\
    \end{eqnarray*}
}


 {\rm (iii)}\ 7 \le k - 2 < 12 かつ  k \le 12 、すなわち  k = 9,\ 10,\ 11,\ 12 のとき、

 {
    \displaystyle
    \begin{eqnarray*}
        C_k &=& \left( f(x)\ を展開したときの\ x^{k-2}\ の係数 \right) \\
            &=& \left( \left( \sum_{n=0}^{12}{a_n x^n} \right)(1 - x^5 - x^7)\ を展開したときの\ x^{k-2}\ の係数 \right) \\
            &=& \left( (a_{k-2}x^{k-2}-a_{k-7}x^{k-7}x^5-a_{k-9}x^{k-9}x^7)\ の\ x^{k-2}\ の係数 \right) \\
            &=& a_{k-2} - a_{k-7} - a_{k-9} \\
            &=& 5 - (k - 8) \\
            &=& 13 - k. \\
    \end{eqnarray*}
}


したがって、以上の場合分けによって求めた  C_k を用いれば、 g_1 = 5,\ g_2 = 7 の下で

 {
    \displaystyle
        P(X = k) = 
            \begin{cases}
                (k - 1) / {35}\ \ \ & ( k = 2,\ 3,\ 4,\ 5,\ 6) \\
                5 / {35}\ \ \ & ( k = 7,\ 8) \\
                (13 - k) / {35}\ \ \ & ( k = 9,\ 10,\ 11,\ 12)
            \end{cases}
}

となり、最終シートの当たりアイテムを  k 回目で獲得する確率が求められました。

 k 2 から  12 まで動くときの分子、すなわち  35 \cdot P(X = k) の値を列挙すると  {1,\ 2,\ 3,\ 4,\ 5,\ 5,\ 5,\ 4,\ 3,\ 2,\ 1} となります!対称的で非常に美しい!

・次回予告っ!

次回の記事は、シートの枚数を  n 枚へ一般化し、平均(分散も?)を求めていきます。

次回: グリモア~(略)~」のメダルチャレンジにおける確率分布 その2(作成中)

任意の周期数列を作る その3

目次

その1: 任意の周期数列を作る その1 - 冷水催眠
      周期  2,\ 3,\ 4,\ 6,\ 8

その2: 任意の周期数列を作る その2 - 冷水催眠
      周期  12,\ 3・2^m,\ 2^m

その3: ココ
      周期  m



前回までの記事、MathJax を使いまくってたせいでメチャクチャ重いページになっていたのに今更気づきました。次からは気をつけます!(修正するとは言っていない)


今までの話を一般化して、周期  m \hspace{10px} (m \ge 3) の周期数列  \{a_n\} の一般項を作ります。

 m 2 で割り切れるだけ割って奇数にし、その奇数個だけ独立な数列を作ってから  2 倍ずつ増やしていくという手順で作ります。

周期 m(奇数)


まずは  {a_n} の周期  m が奇数のときです。

周期  m の任意の数列を作るには一次独立な異なる数列が  m 個必要ですから、次の規則に従って  m 個の数列  f_m(n,\ 0) f_m(n,\ m-1) を作ります。


f:id:hge:20160318011215p:plain


すると、 \{a_n\} の一般項は係数  t_1 t_m を用いて次のように表せます。

 \displaystyle a_n = \sum_{k=1}^{m} {t_kf_m(n,\ k-1)}

係数  t_1 t_m は次の行列で与えられる実数です。

f:id:hge:20160318000929p:plain


 m が奇数のときに上の逆行列が存在することはどうしたら証明できるんでしょうかね・・・

 m=3 から  m=29 のときに逆行列を持つことは確認済みです。

 m が大きくなるごとに行列式の絶対値が増えていっているので恐らく大丈夫なはずです・・・・・・多分・・・・・・・・・(っ◞‸◟c)


周期 m(偶数)

次に、作りたい数列の周期  m が偶数のときを考えます。

 m 2 で割りきれるだけ割ったら奇数  p になったとき、適当な自然数  k を用いて  m=2^k \times p と書けます。

 p は奇数なので、上に書いた通りに  p 個の数列  f_p(n,\ 0) f_p(n,\ p-1) を作ると周期  p の任意の周期数列の一般項が作れます。

それを[前回の記事]でやったように、周期を2倍にする操作を  k 回行うことによって、周期  m の数列の一般項を作ることができます。

周期  p の任意の周期数列の一般項は  \displaystyle \sum_{i=1}^{p} {t_if_p(n,\ i-1)} と表せますが、これに次の操作を  k 回施します。


f:id:hge:20160318011655p:plain


 \displaystyle \operatorname{sgn}\left(\sin{\frac{(2n-1)\pi}{2a}}\right) は0にならないので  \displaystyle \frac{\sin{\frac{(2n-1)\pi}{2a}}}{\left|\sin{\frac{(2n-1)\pi}{2a}}\right|} とも書けます。前回の記事と同じ処理をしていることになります。

自分でも上の式で合ってるのかよく分からないのですが、具体例を書けば多分伝わります。


具体的には、 \displaystyle \sum_{i=1}^{p} {t_if_p(n,\ i-1)} は1度目の延長操作で

f:id:hge:20160318001937p:plain

となり、2回目の延長操作で (sgn(~)をfp(n, k)に含めてΣを結合し、Σの範囲を1から2pとして変換する)

f:id:hge:20160318001945p:plain

となり、3回目の延長操作で

f:id:hge:20160318001951p:plain

となり・・・・・・ といった感じで2倍2倍2倍2倍と伸ばしていきます。

 k 回伸ばしたら周期  m の一般項の原型の出来上がりです!


あとは係数  t_1 t_m を求めるだけです。

 m が奇数のとき、係数を求めるのにでっかい行列の逆行列を使っていました。

その逆行列

f:id:hge:20160318003417p:plain

とおきます。そして

f:id:hge:20160318004013p:plain

というように行列をさらに  k 個作ると、 A_m = A_{2^k \times p} に到達します。


そのとき、一般項の係数  t_1 t_m

 {
\left(
    \begin{array}{c}
        t_1 \\
        t_2 \\
        t_3 \\
        \vdots \\
        t_m \\
    \end{array}
\right) = A_m
\left(
    \begin{array}{c}
        a_1 \\
        a_2 \\
        a_3 \\
        \vdots \\
        a_m \\
    \end{array}
\right)}

で求められます。


書き方や表現が違いますが、今までやってきたことは前回の記事の後ろの方でやったことと全部同じ原理です。

実質的に異なるところは周期が任意の奇数の数列を作ったところだけです。

実際に1つ周期数列の一般項を作って、この記事を締めくくりたいと思います。


周期数列 1, 1, 4, 5, 1, 4, 1, 9, 1, 9, 1, 1, 4, 5, 1, 4, 1, 9, 1, 9, ...

ふ・・・深い意味なんてないんだからねっ!///


この数列の周期は  m=10=2^1 \times 5 です。

まずは①,②,③に従って  5 つの数列を作ります。


f:id:hge:20160318004833p:plain


上の5つの数列の一次結合は  \displaystyle \ \sum_{i=1}^{5} {t_if_5(n,\ i-1)}\ となります。

 5 \times 2^1 = 10 なので、求める周期数列の一般項は1回の延長操作をして

f:id:hge:20160318013103p:plain

と表せます。


次に係数  t_i を求めます。 5 次正方行列  A_5

f:id:hge:20160318013602p:plain

で定めます。

次に、 10\ (=m) 次正方行列  A_{10}=A_m

f:id:hge:20160318005236p:plain

で定めます。

この  A_m から、係数  t_i が次のように求まります。

f:id:hge:20160318005333p:plain

これを  (1) 式に代入すれば、求める一般項は

f:id:hge:20160318010226p:plain

となります!


欠点

この方法の欠点はコンピューターでの浮動小数点計算には向いていていないところ、そしてグラフが連続ではなくボッコボコで汚いところです。

コンピューターで一般項を浮動小数点計算すると本来  \operatorname{sgn}(0)=0 となってほしいところが  \operatorname{sgn}(0.00000000000001)=1 などと評価されてしまうことがあります。これは  n \equiv 0 \pmod{m} のときに発生してしまいます。


周期が  2,\ 3,\ 4,\ 6,\ 8,\ 12,\ 3・2^m,\ 2^m のときは式もグラフもきれいで  \operatorname{sgn} とかいうチートツールを酷使しない前回までの方法を使おうね!おねーちゃんとのお願いだよ!


そういえばはてなブログなんかにこの話載せちゃっていいのだろうか・・・・・・?