ブログ名

競技プログラミングやお歌のお話をする高菜です。

トップ > ［工事中］いわゆる期待値 DP の考え方

［工事中］いわゆる期待値 DP の考え方

$$ \newcommand \id { \mathrm { id }} \newcommand \src { \mathrm { src }} \newcommand \tar { \mathrm { tar }} \newcommand \pid { p _ { \id } } $$ 毎回同じ形で出るのになんか混乱するので纏めました。

※ 「補遺 ～ 執筆後に思ったのですが」にあるとおり、これは筋の悪い方法である可能性が高いです。特に Level 1 の部分、大幅な書き換えが必要です。申し訳ありません。いったん工事中とさせてください。

とりあえず記号を導入しましょう。この記事では $G = (V, E)$ は有限な有向グラフであり、$p$ は辺重みであって任意の節点 $v \in V$ に対して $\sum _ { \delta ^ + ( v ) } p(e) = 1$ が成り立つものであるとします。つまり $p$ が確率行列の条件を満たすということですね。このグラフ上$p$を遷移確率とするマルコフ連鎖を考えていきましょう。

このグラフの上で確率やら期待値やらを DP していきましょう！DP をするので DAG であるととてもうれしいのですが、如何せん確率行列の条件 + グラフの有限性から、どうしてもループが 1 つ以上存在してしまいます。とはいえループの難しさにはレベルがあると私は思います。

  • Level 1：「終点」と呼ばれる一点だけに、確率 $1$ のループがある（要するに終点に到達したらゲームを終了する）
  • Level 2：自己ループがある（要するに各点で特定の確率で一回休みになる。いわゆるループ除去と呼ばれるテクニック？ 現状ここが実質本編）
  • Level 3：そのほか（強連結成分分解で速くなることもある。詳細は自信なし）

Level 1, 2 の場合は各点の通過確率とその点に初めて到達するまでの手数の「期待値」（正確な定義は後述）とかを DP することが多いです。また初期状態に言及しませんでしたが基本的には「始点」と呼ばれる特別な節点 $s$ に、確率 $1$ で存在するという初期状態を考えています。以下基本的にはそれを念頭に置いてお話していきます。

Level 1：「終点」と呼ばれる一点だけに、確率 $1$ のループがある

たとえば次のグラフで、終点 $t$ に行くまでに必要な手数の期待値はいくつでしょうか？ これは DP しなくてもわかりますね。上ルートが確率 $1/3$、長さ $2$、下ルートが $2/3$、長さ $3$ ですから、平均すると手数は $8/3$ になります。

これを DP でやるときには次のものを管理します。

  • $P(x)$：節点 $x$ を通過する確率（$p(e)$ と大文字小文字を除いて記号が被っているので注意です。ここよいノーテーションあったら知りたいです。）
  • $E(x)$：節点 $x$ を通過する場合は到達するまでの最小手数、しない場合は $0$、と定義した確率変数の期待値。これを「節点 $x$ を通過するときの制限期待値」と呼びます。私が今つけたのですがもっとリーズナブルで普及した呼び方があったら教えていただきたいです。

確率論的なお話を離れて、より直接的な定義で書くとこういう感じです。（ただし総和の範囲は $\gamma$ が $s$ で始まって $x$ で終わり、最後以外に $x$ を含まない $G$ のウォークで、$p(\gamma)$ は辺の $p$ の総積、$|\gamma|$ は辺の総数です。）今回の設定ではこれらの総和はともに和の順序に依存せず定義できて、有限の値に収束します。

$$ P(x) = \sum _ \gamma p(\gamma) \\ E(x) = \sum _ \gamma |\gamma| p(\gamma) $$

各節点に対する $P, E$ の値は下図のようになります。さてみなさまの疑問にお答えしていきましょう。ハイ、そこのあなたはやかったです。ええ、そうですね、例えば上側の真ん中、「ここに到達する場合は必ず手数 $1$ なのですから、$E = 1$ なのでは？？」、なるほどです。ありがとうございます。しかしそれは今回の定義では間違いです。$E$ はこの節点を通過しない場合は $0$ と定義しているため $E = 1 / 3$ が正しいです。（ちなみにここで $E = 1$ になるほうの定義は 条件付期待値 と呼ばれていて、そっちで計算してもできなくはないのですが、経験的に、そのやり方は面倒なだけでやめた方がよいと私は感じております。）

$P, E$ は初期値が $P(s) = 1, E(s) = 0$ で、遷移は次のように書けます。（ただし $x = \src(e)$。）

$$ P(y) = \sum _ { e \in \delta ^ -(v) }P \left (x \right)p(e) \\ E(y) = \sum _ { e \in \delta ^ -(v) }\left(E(x) + P(x) \right )p(e) $$

要するに、辺 $e \in \delta ^ - ( v ) $ を通過する確率が $P(x)p(e)$ なのでそれを足し合わせる、そして辺 $e$ を通るときの制限期待値が、節点 $x$ までで $E(x)p(e)$、辺 $e$ の通過分で $P(y)p(e)$ なので合計しているという感じです。なお $E(y)$ の式は纏めなおして $E(y) = P(y) + \sum _ { e \in \delta ^ - (v) } E(x)p(e)$ と書くこともできます。

あとこれどこに書くか迷った補足なのですが終点 $t$ が到達不能な場合は $P = 0, E = 0$ になります。また終点は複数にすることもできて、その場合は$P = 1$ とは限らず「その終点で終わる確率」を表すようになります。

なお余談なのですが各辺の通過コストを $1$ 以外のものにした問題も同じように解けますね。それが Level 2 で自己ループを考えるときのポイントになってきます。もっというと実数だけではなくて一般の実ベクトルでも大丈夫です。なんなら $P$ も $E$ の一種で、初期状態が始点で $1$、辺重みがすべて $0$ なやつです。

Level 2：自己ループがある場合

※ このセクションでから、「サイコロで初めて $1$ が出るまでの試行回数の期待値って $6$ ですよね」的なこと、つまり幾何分布の期待値を前提知識として仮定します。これ実はそんなに当たり前のことではありませんから、定式化とか証明とかをやったことがない方はぜひです。最初は無限確率分布の扱いに困るのではないかと思われます。

今度はこれです。自己ループは図から省略していますが、余った確率はすべて自己ループだとしましょう。つまり例えば $s$ にとどまる確率は $1/4$ です。このとき $t$ に到達するまでの手数の期待値はいくつでしょうか？

かなり大変ですが、これも DP しなくてもわかります。まず最初 $s$ から動ける確率は $\frac 3 4$ なので、動けるまでの試行回数（成功回を含む）は $\frac 4 3$ ですね。ここで上ルートと下ルートに場合分けしましょう。上ルートを通る確率は $\frac 1 3$ ですね。次に上ルートを通る場合の手数の条件付期待値を計算しましょう。最初の辺まで（最初の辺を含む）は先ほど計算した通り $\frac 4 3$ ですね。さらに次の辺は確率 $\frac 1 3$ なので渡るまで（渡る回を含む）の試行回数の期待値は $3$ で合計 $\frac {13} 3$ となります。下ルートを通る確率は $\frac 2 3$ で、$3$ 本の辺を渡るための試行回数の期待値はそれぞれ $\frac 4 3, 3, 1$ で、合計 $\frac {16} 3$ になりますね。以上確率で重みづけて足し合わせて、$\frac { 13 } { 3 } \cdot \frac { 1 } { 3 } + \frac { 16 } { 3 } \cdot \frac { 2 } { 3 } = 5$ となります。

この具体例を踏まえて Level 2 を Level 1 の場合に近い形に帰着しましょう。議論を振り返ってみると結局、確率を自己ループ以外のもので振り直して、辺の横断コストを Level 1 で暗黙に仮定していたような $1$ ではなくて、自己ループ以外を選択する確率の逆数にしてしまえば、全く同じお話であることがわかりますね。

さてこれを式で書いていきましょう。各接点 $x$ に自己ループ $\id _ x$ があるとして、その遷移確率を $p \left( \id _ x \right) = \pid (x)$ と定義すると、自己ループ以外を選択する確率は $1 - \pid (x)$ ですから、先程振り直した辺遷移確率は $p'(e) = \frac { p(e) } { 1 - \pid (x) }$（ただし $x = \src(e)$）と表せます。また辺 $e$ の移動コストはその始端 $x$ にしか依存しないため、$c(x) = \frac { 1 } { 1 - \pid (x) }$ と表せます。以上より Level 1 と同様の議論により、次の式を得ます。

$$ P(y) = \sum _ { e \in \delta ^ - (y) \setminus \left \lbrace \id _ y \right \rbrace } P \left (x \right)p'(e) \\ E(y) = \sum _ { e \in \delta ^ - (y) \setminus \left \lbrace \id _ y \right \rbrace } \left(E(x) + c(x) P(x) \right )p'(e) $$

この変形後のグラフ・式で DP していきましょう！ すると次のように、先ほどと同じ結果を得ると思います。

一応もとのグラフでの式に直すとこういう感じにになります。辺 $e$ を通るときの $y$ までの手数の制限期待値が、$x$ までの分の寄与が $E(x) \frac { p(e) } { 1 - \pid (x) }$、$e$ 通過分の寄与が $\frac { 1 } { 1 - \pid (x) } P(x) \frac { p(e) } { 1 - \pid (x) }$ （コスト × $x$ の通過確率 × そのうえで $e$ を通過する条件付確率）というふうに分解して理解できます。これ約分できそうでできないの毎回間違ったかなって不安になります。

$$ P(y) = \sum _ { e \in \delta ^ - (y) \setminus \left \lbrace \id _ y \right \rbrace } P(x) \frac { p(e) } { 1 - \pid (x) } \\ E(y) = \sum _ { e \in \delta ^ - (y) \setminus \left \lbrace \id _ y \right \rbrace } \left ( E(x) + \frac { 1 } { 1 - \pid (x) } P(x) \right ) \frac { p(e) } { 1 - \pid (x) } $$

Level 3：そのほか（強連結成分分解）

※ 実はここはほとんど自信がない領域なのでアドバイスが欲しいところです。また知識・経験・確認不足のため当然クオリティが低く、今後加筆・修正する可能性が非常に高いです。

※ このセクションからはどの点からでも吸収確率が正な吸収マルコフ連鎖における期待値の有限性とその計算方法 （参考文献： ワープのある双六でゴールする時間の期待値をガチで求める -吸収マルコフ連鎖- #競技プログラミング - Qiita）の知識を仮定します。

DAG でない場合は一般にはとても大変なため、強連結成分分解をして強連結な部分問題と acyclic な部分問題に分解していくという方針を取ります。$G$ の強連結成分 $C$ を「解消」しましょう。$C$ のどの点からでも正の確率で $C$ の外に出られることを仮定します。このとき $C$ の点 $i$ から始めて点 $j$ まで到達し、その次の試行でちょうど $C$ から出ていくような確率を $p(i, j)$ と、そのとき$C$ から出る直前まで（≠初めて $j$ に到達するまで）の手数の制限期待値を $e(i, j)$ とおきます。すると $C$ の頂点をすべて倍加して $C ^ {\mathrm{in}}, C^{\mathrm{out}}$ と定め、$\delta ^ -(C)$ の辺はすべて $C ^ {\mathrm{in}}$ に、$\delta ^ +(C)$ の辺をすべて $C ^ {\mathrm{out}}$ につなぎ、さらに $i ^ { \mathrm{in}} \in C ^ {\mathrm{in}}$ と $j ^ { \mathrm{in}} \in C^{\mathrm{out}}$ の間には遷移確率 $p(i, j)$、コスト$e(i, j)$ の辺を貼ることにします。これをどの点からでも自分自身の外に出られるような強連結成分すべてについて行うことで、Level 1 と同様の DP ができるはずです。（こんどやってみよ～～っと）（未検証）

ただし計算量には注意しましょう。強連結成分分解は線形時間ですが、強連結成分の解消には一般の吸収マルコフ連鎖を解く必要があり、これはサイズ $|C|$ の正則な一次方程式になり、おそらくそこまで高速には解けません。例えば掃き出し法で $O (|C| ^ 3)$ 時間で解くことができます。遅いですね。また DAG 上のマルコフ連鎖 DP は線形時間ですが、強連結成分分解 $|C|$ の解消により $|C| ^ 2$ 本の辺が追加されております。多いですね。とはいえ競技プログラミングにおいては大抵の場合は手計算で強連結成分分解の解消をしていくことになるのではないでしょうか。未来の私による天才的な追記が待たれます。

補遺 ～ 執筆後に思ったのですが

期待値 DP、その点から終点までの手数の期待値を終点から DP する方が普通な気もしてきました。そうすると通過確率を管理する必要がなくて楽だったりします…？ 私がふだん勝手にいばらの道を行っていた説が急浮上しており泣いております。Level 1 に帰着したあとの解き方が違うだけなのですがちょっとまだ十分に整理できていないので言及だけしておきます。