問題概要

問題文はこちらを参照してください。

試行回数の期待値を求める基本問題です。いわゆるコンプガチャの期待値の問題で、回数の期待値を求める問題があることを知りました。

解法

試行回数の期待値を求める問題では、ある状態から1回の試行によって遷移する状態の期待値との漸化式を立ててそれを動的計画法で解くことになります。基本的には、下記の式の形になるようです。

$$\mathrm{E}[Z]=1+\mathrm{E}[Z_1]\cdot p_1+\mathrm{E}[Z_2]\cdot p_2+...+\mathrm{E}[Z_n]\cdot p_n$$

$Z$の状態から、1回の試行によってそれぞれ$p_i$の確率で$Z_i$の状態に遷移する場合。

ここではなぜ上記の式になるのかを考えるため、確率変数の定義とその確率分布を意識していきたいと思います。

$X_i$：これまでの目の合計が$i$のとき、合計が$K$になるまでに振ることになる回数

このように考えると、求める期待値は$X_0$の期待値、$i\ge K$のときすでに$K$を超えているので、$\mathrm{E}[X_i]=0$となります。

ここで、これまでの目の合計が$i$の時に次に振るさいころの目が$1$であると仮定した場合の$X_i$の期待値を考えると、目の合計が$i+1$の時の期待値に$1$が出た試行1回を足したものになります。これは$X_i$の条件付き期待値と呼ばれるもので、式で表すと次のようになります。

$$\mathrm{E}[X_i|Y=1]=1+\mathrm{E}[X_{i+1}]$$

$Y$：これまでの目の合計が$i$のとき、次に振るさいころの目の値

同様にその他の目が出た時を考えると、次の確率分布を満たすような確率変数$\mathrm{E}[X_i|Y]$を定義することができます。

$\mathrm{E}[X_i|Y]$	$\scriptsize 1+\mathrm{E}[X_{i+1}]$	$\scriptsize 1+\mathrm{E}[X_{i+2}]$	$\scriptsize 1+\mathrm{E}[X_{i+3}]$	$\scriptsize 1+\mathrm{E}[X_{i+4}]$	$\scriptsize 1+\mathrm{E}[X_{i+5}]$	$\scriptsize 1+\mathrm{E}[X_{i+6}]$	合計
確率	$\frac{1}{6}$	$\frac{1}{6}$	$\frac{1}{6}$	$\frac{1}{6}$	$\frac{1}{6}$	$\frac{1}{6}$	1

ここで、条件付き期待値には$\mathrm{E}[\mathrm{E}[X_i|Y]]=\mathrm{E}[X_i]$という式が成り立つとのこと。したがって、$X_i$の期待値は$\mathrm{E}[X_i|Y]$の期待値を求めればよく、これは期待値の定義より下記になります。

$$\begin{eqnarray} \mathrm{E}[X_i] & = & \mathrm{E}[\mathrm{E}[X_i|Y]] \\ & = & (1+\mathrm{E}[X_{i+1}])\cdot \frac{1}{6}+(1+\mathrm{E}[X_{i+2}])\cdot \frac{1}{6}+...+(1+\mathrm{E}[X_{i+6}])\cdot \frac{1}{6} \\ & = & 1+\mathrm{E}[X_{i+1}]\cdot \frac{1}{6}+\mathrm{E}[X_{i+2}]\cdot \frac{1}{6}+...+\mathrm{E}[X_{i+6}]\cdot \frac{1}{6} \end{eqnarray}$$

例えば、$\mathrm{E}[X_{K-1}]=1+\mathrm{E}[X_{K}]\cdot \frac{1}{6}+\mathrm{E}[X_{K+1}]\cdot \frac{1}{6}+...+\mathrm{E}[X_{K+5}]\cdot \frac{1}{6}$となり、$i\ge K$のとき$\mathrm{E}[X_i]=0$より、$\mathrm{E}[X_{K-1}]=1$です。

漸化式にて$\mathrm{E}[X_{i}]$を$\mathrm{E}[X_{i+1}]～\mathrm{E}[X_{i+6}]$にて定義できているので、ＤＰで$i$を$K-1$から$0$のループを回すことで$\mathrm{E}[X_{0}]$を求めることが可能です。

結局、動的計画法の問題としてまとめると下記のようになります。

考察

条件付き期待値に関する情報は少なめだったので、最初の式をなかなか理解することができませんでした。結局このような形で、理解したつもりになっています。