Zenn
🤔

期待値 DP の計算の方向の考察メモ

に公開
競技プログラミング
AtCoder
期待値dp
tech

概要

期待値 DP の解説で状態遷移の最終状態から DP の計算をするというのをよく見ますが、状態遷移の方向と逆向きに計算しているように見えます。また「初期状態から計算できる場合もあるが実装が複雑になる」というのも聞いたことがあります。

そもそも期待値 DP の更新式が期待値の素朴な定義式と少しギャップがあるように思え、「感覚的に立式してるけどほんとに成り立つ？」と思ったことがありました。

そこで期待値 DP の更新式の導出や計算の方向による違いについて勉強してみます。

結論

  • 期待値の素朴な定義から期待値 DP の更新式に式変形ができた
  • 期待値 DP は状態遷移の方向とは逆向きに最終状態から計算していくのが筋がよさそう
  • その要因として、遷移先か遷移元かで確率計算の複雑さに差がある
    • ある状態から遷移する状態 (の集合)
      • 遷移確率の総和が 1 となる
    • ある状態に遷移する状態 (の集合)
      • 遷移確率自体も確率 DP で求める必要がありそう
  • 確率的な状態遷移は「ある状態を起点として複数ありうる状態のいずれかに移る」というものなので、遷移元の状態を固定して、その状態ごとに遷移先の状態をまとめていくと確率計算がシンプルになりやすそう

定義

まずは確率と状態遷移に関する記法をグラフをベースに定義してみます。

基本

  • V: 状態集合
  • E \subseteq V \times V: 有向辺集合。(u, v) \in E は状態 u から v への遷移が存在することを表す。
  • w(u, v) \in \R: u から v へ遷移したときにかかるコスト。(u, v) \in E とする。
  • P(u, v) \in [0, 1]: u から v へ遷移する確率。(u, v) \in E とする。
  • s \in V: 開始状態
  • t \in V: 終了状態 (簡単のため、1 状態とする)

パスで拡張

上をベースにパスの概念で w, P を拡張する。

  • \rho = v_0 v_1 \ldots v_k: パス。0 \le \forall i < k, (v_i, v_{i + 1}) \in E が成り立っているものとする。
    • \rho_i := v_i とする。
    • |\rho| := k とする。
  • w(\rho) \in \R: 状態 \rho_0 から \rho 上を遷移したときにかかるコスト
    • w(\rho) = \sum_{i = 0}^{|\rho| - 1} w(\rho_i, \rho_{i + 1})
  • P(\rho) \in [0, 1]: 状態 \rho_0 から \rho 上を遷移する確率
    • P(\rho) = \Pi_{i = 0}^{|\rho| - 1} P(\rho_i, \rho_{i + 1})
    • マルコフ連鎖であることが必要？

その他

遷移前後の頂点集合を扱うために以下を定義します。

  • \delta^+(v) = \left \{ u \in V \mid (v, u) \in E \right \}: v から 1 ステップで遷移できる状態 u の集合
  • \delta^-(v) = \left \{ u \in V \mid (u, v) \in E \right \}: v に 1 ステップで遷移できる状態 u の集合

注意

この記事では比較的単純な期待値 DP の問題設定について考えています。
以下、注意点です。

遷移元/先の状態に関する期待値をトポロジカルソート順に求められるようなケースです。
複雑なループがありえるケースは対象外です。

こちらについては今後追記するかもです。
(例: https://atcoder.jp/contests/abc350/tasks/abc350_e)

最終状態から DP 計算

状態遷移とは逆向きで、最終状態から DP 計算を行う方針を考えます。
(例: dp[i]: マス i からマス N に至るまでにサイコロを振った回数の期待値。dp[N] = 0)

定義

  • \mathcal P(v) \subseteq V^*: v \in V から終了状態 t に至る全てのパスの集合
    • \mathcal P(v) = \left \{ \rho \in V^* \mid \rho_0 = v \land \rho_{|\rho|} = t \right \}
  • E[v] \in \R: v \in V から最終状態 t へ到達するのにかかるコストの期待値
    • E[v] = \sum_{\rho \in \mathcal P(v) } P(\rho) \cdot w(\rho)

期待値計算

初期状態 s から終了状態 t へ遷移するのにかかるコストの期待値は E[s] と表せます。
以下では素朴な期待値の定義からスタートして、期待値 DP のよく見る形に変形します。

s = t の場合 E[s] = E[t] = 0 となります。
s \ne t の場合、s から t のパスを、s から 1 ステップ遷移した状態 u に着目して分解します: \rho = s \rho', \rho'_0 = u

では式変形していきます。

\begin{aligned} E[s] &= \sum_{\rho \in \mathcal P(s) } P(\rho) \cdot w(\rho) \\ &= \sum_{s \rho' \in \mathcal P(s) } P(s \rho') \cdot w(s \rho') \quad (\because \rho = s \rho') \\ &= \sum_{s \rho' \in \mathcal P(s) } (P(s, \rho'_0) \cdot P(\rho')) \cdot (w(s, \rho'_0) + w(\rho')) \\ &= \sum_{u \in \delta^+(s)} \sum_{\rho' \in \mathcal P(u) } (P(s, u) \cdot P(\rho')) \cdot (w(s, u) + w(\rho')) \quad (u := \rho'_0)\\ &= \sum_{u \in \delta^+(s)} P(s, u) \sum_{\rho' \in \mathcal P(u) } P(\rho') \cdot (w(s, u) + w(\rho')) \\ &= \sum_{u \in \delta^+(s)} P(s, u) \left ( w(s, u) \sum_{\rho' \in \mathcal P(u) } P(\rho') + \sum_{\rho' \in \mathcal P(u) } P(\rho') w(\rho') \right ) \\ &= \sum_{u \in \delta^+(s)} P(s, u) \left ( w(s, u) \sum_{\rho' \in \mathcal P(u) } P(\rho') + E[u] \right ) \quad (\because E[u] = \sum_{\rho' \in \mathcal P(u) } P(\rho') w(\rho'))\\ \end{aligned}

再帰的に E[u] を求めることを考えると、任意の状態 u に対してその期待値は以下で表せます。

E[u] = \sum_{v \in \delta^+(u)} P(u, v) \left ( w(u, v) \sum_{\rho' \in \mathcal P(v) } P(\rho') + E[v] \right )

常に成り立つこと

\sum_{v \in \delta^+(u)} P(u, v) = 1

固定の u から 1 ステップで遷移できる状態 v への遷移確率の和をとると 1 になる。

以下では、問題設定に条件を追加して E[u] の式をさらに変形する。

1. 任意の状態から必ず終了状態に到達できる場合

遷移の途中で「終了状態に到達しえない状態」に到達することがないケース。

  • (そもそもこれが成り立たないと期待値が定義できない？)

このとき、v から t に到達する全てのパスの確率を足し合わせると 1 となる:

\sum_{\rho' \in \mathcal P(v) } P(\rho') = 1

よって、

E[u] = \sum_{v \in \delta^+(u)} P(u, v) \left ( w(u, v) + E[v] \right )

2. 任意の遷移でコストが 1 の場合

サイコロを振る「回数」など、1 回の遷移にかかるコストが常に 1 のケース。
w(u, v) = 1 となる。

よって、

\begin{aligned} E[u] &= \sum_{v \in \delta^+(u)} P(u, v) \left ( \sum_{\rho' \in \mathcal P(v) } P(\rho') + E[v] \right ) \end{aligned}

1, 2 がともに成り立つ場合

\begin{aligned} E[u] &= \sum_{v \in \delta^+(u)} P(u, v) \left ( 1 + E[u] \right ) \\ &= \sum_{v \in \delta^+(u)} P(u, v) + \sum_{v \in \delta^+(u)} P(u, v) E[v] \\ &= 1 + \sum_{v \in \delta^+(u)} P(u, v) E[v] \quad (\because \sum_{v \in \delta^+(u)} P(u, v) = 1) \end{aligned}

典型問題でよく見る形になりました。

初期状態から DP 計算

状態遷移と同じ向きで、初期状態から DP 計算を行う方針を考えます。
(例: dp[i]: マス 0 からマス i に至るまでにサイコロを振った回数の期待値。dp[0] = 0)

定義

  • \mathcal P(v) \subseteq V^*: 開始状態 s から v \in V に至る全てのパスの集合
    • \mathcal P(v) = \left \{ \rho \in V^* \mid \rho_0 = s \land \rho_{|\rho|} = v \right \}
  • E[v] \in \R: 開始状態 s から v \in V へ到達するのにかかるコストの期待値
    • E[v] = \sum_{\rho \in \mathcal P(v) } P(\rho) \cdot w(\rho)

期待値計算

初期状態 s から終了状態 t へ遷移するのにかかるコストの期待値は E[t] と表せます。
こちらでも素朴な期待値の定義から式変形します。

s = t の場合 E[s] = E[t] = 0 となります。
s \ne t の場合、s から t のパスを、t から 1 ステップ戻った状態 u に着目して分解します: \rho = \rho' t, \rho'_{|\rho'|} = u

では式変形していきます。

\begin{aligned} E[t] &= \sum_{\rho \in \mathcal P(t) } P(\rho) \cdot w(\rho) \\ &= \sum_{\rho' t \in \mathcal P(t) } P(\rho' t) \cdot w(\rho' t) \quad (\because \rho = \rho' t) \\ &= \sum_{\rho' t \in \mathcal P(t) } (P(\rho') \cdot P(\rho'_{|\rho'|}, t)) \cdot (w(\rho') + w(\rho'_{|\rho'|}, t)) \\ &= \sum_{u \in \delta^-(t)} \sum_{\rho' \in \mathcal P(u) } (P(\rho') \cdot P(u, t)) \cdot (w(\rho') + w(u, t)) \quad (u := \rho'_{|\rho'|})\\ &= \sum_{u \in \delta^-(s)} P(u, t) \sum_{\rho' \in \mathcal P(u) } P(\rho') \cdot (w(\rho') + w(u, t)) \\ &= \sum_{u \in \delta^-(s)} P(u, t) \left ( \sum_{\rho' \in \mathcal P(u) } P(\rho') w(\rho') + w(u, t) \sum_{\rho' \in \mathcal P(u) } P(\rho') \right ) \\ &= \sum_{u \in \delta^-(s)} P(u, t) \left ( E[u] + w(u, t) \sum_{\rho' \in \mathcal P(u) } P(\rho') \right ) \quad (\because E[u] = \sum_{\rho' \in \mathcal P(u) } P(\rho') w(\rho'))\\ \end{aligned}

再帰的に E[u] を求めることを考えると、任意の状態 u に対してその期待値は以下で表せます。

E[u] = \sum_{v \in \delta^-(u)} P(v, u) \left ( E[v] + w(v, u) \sum_{\rho' \in \mathcal P(v) } P(\rho') \right )

「最終状態から DP 計算」との違い

1. \sum_{v \in \delta^-(u)} P(v, u) が 1 になるとは限らない。

「最終状態から DP 計算」する場合、同じような項として \sum_{v \in \delta^+(u)} P(u, v) が出てきました。これは、固定の u からそれぞれの状態に遷移する確率の和だったので 1 となりました。

一方で、\sum_{v \in \delta^-(u)} P(v, u) は固定の u に遷移できる状態の遷移確率の和であり、1 になるとは限りません。(1 を超えることもある？)

2. \sum_{\rho' \in \mathcal P(v) } P(\rho') が 1 になるとは限らない。

これは初期状態 s から v にいたる全てのパスの確率を足し合わせたものです。v に到達しなくても最終状態に到達しうるので、1 より小さくなりえます。

実装が複雑になる理由

最終状態から逆向きに計算する場合と違い、本質的に簡単にできない項が存在するため、期待値計算の中でそのような項も合わせて計算する必要があります。

E[u] = \sum_{v \in \delta^-(u)} P(v, u) \left ( E[v] + w(v, u) \sum_{\rho' \in \mathcal P(v) } P(\rho') \right )

特に上式の \sum_{\rho' \in \mathcal P(v) } P(\rho') が追加で計算・管理が必要となる部分です。これは初期状態から v にいたるパスの遷移確率の和で、確率 DP として初期状態から順に求める必要がありそうです。

Discussion