概要
「DAG でスタートからゴールまで移動。必要な移動回数の期待値は？」という典型パターン。
解法
とりあえず、「振り出しに戻る」を無視します。「振り出しに戻る」マスに到達するや否や、即終了と考えておきましょう。各マス $1, 2, \ldots$ に対して、マス $n$ に到達する確率 $\dp[n]$ を求めておきます。
「ダイスを振る回数」を、「マス $n$ においてダイスを振る回数」を $n$ にわたって足したものとして考えて期待値の線形性を利用します。
まず、$x_n = 0$ となるマス $n < N$ に対する $\dp[n]$ の和を、$E$ とします。これは、「振り出しに戻ると即終了」という条件を追加したゲームにおいて、ダイスを振る回数の期待値になります。
$p = \dp[N]$ とします。これは、振り出しに戻らずにゴールできる確率です。すると、「振り出しに戻る」を含めた元の問題は、言い換えられます。
- 成功確率が $p$ であり、一回の試行にかかるコストの期待値は $E$ であるゲームを繰り返す。はじめて成功するまでにかかるコストの期待値を求めよ。
この期待値は $E/p$ と計算できます。
コメント
DAG を遷移する場合のコストの期待値を求める場合に、各頂点を始点とする移動コストに分解して考えると、期待値の計算を確率の計算に帰着できます。期待値のまま DP しても解くことができますが、こちらの形の方が計算式が単純化できることが多いように思います。
