進めないコストがある場合の期待値の計算(ABC314-E)
テンパって落としたので、期待値問題の復習。
問題
部分問題：
確率 $${p}$$ で成功：コスト $${a}$$ を払って終了
確率 $${q = 1-p}$$ で失敗：コスト $${b}$$ を払って継続
この遷移のコスト期待値は？
1回目で成功、2回目で成功、3回目で成功、・・・のコスト×確率をすべて足し合わせる。
$$
\begin{aligned}
E(\text{cost}) &= pa + pq(a + b) + pq^2(a + 2b) + pq^3(a + 3b) +... \\
&= \sum_{i=0}^\infty pq^i(a+bi) \\
&= \sum_{i=0}^\infty apq^i + \sum_{i=1}^\infty bpq^ii \\
&= ap \sum_{i=0}^\infty q^i + bpq \sum_{i=1}^\infty i q^{i-1} \\
&= ap \frac{1}{1-q} + bpq \frac{1}{(1-q)^2} \\
&= ap \frac{1}{p} + bpq \frac{1}{p^2} \\
&= a + b \frac{q}{p} \\
\end{aligned}
$$
ここで
$$
\begin{aligned}
\sum_{i=0}^\infty q^i &= \frac{1}{1-q} \\
\sum_{i=0}^\infty (i+1) q^i &= \frac{1}{(1-q)^2}
\end{aligned}
$$
を使用した。
この式の考え方
（以下、指摘頂いて修正しました、解説と切る位置が違っていました。）
ABC314-Eの解説より
「$${i}$$番目のルーレットが出しうる目$${P_i}$$個のうち$${Z_i}$$個が0であるとき、このルーレットの代わりに$${C_iP_i/(P_i-Z_i)}$$円払ってもとのルーレットから0の目を取り除いたようなルーレットを用いることにしても結果は変わりません。」
この意味は？
上の記号で書き直すと、
「確率 $${q}$$ で元に戻り、そのコストが $${C}$$ のときは、この遷移の代わりにあらかじめコスト $${C / p}$$ を払って必ず遷移するものとしても結果は変わりません。」
これは、
$$
E(\text{cost}) = a + b \frac{q}{p}
$$
の式を、$${a=a'+C, b=C}$$ として、
$$
E(\text{cost}) = a' + C \frac{p + 1 - p}{p} = a' + \frac{C}{p}
$$
となるので、「滞在費+次への移動費で $${C/p}$$ を払った上で確実に次に進む」と読んだことになっている。$${a'}$$ の部分はこの問題では以降の DP のコスト期待値。