進めないコストがある場合の期待値の計算(ABC314-E)

テンパって落としたので、期待値問題の復習。

• 問題

  • https://atcoder.jp/contests/abc314/tasks/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 のコスト期待値。