すごろくDP
投稿者：CarpDay.icon
⠀すごろくのように状態が遷移する問題に対して，ゴールするまでの期待手番数を求める問題がABCで時々出題されます．何度やっても解き方忘れるので，まとめておきます．
1. 自己閉路がない問題
(0) 例題1
⠀$ \frac26の確率で1，$ \frac36の確率で2，$ \frac16の確率で3が出るサイコロがあります．現在，数直線上の地点0にいて，サイコロを振って出た目の分だけ右方向に移動します．地点3，またはそれより右に到着するまでに振ったサイコロの回数の期待値を求めなさい．（下の図では，3以上はまとめています．）
⠀ ⠀ ⠀⠀ ⠀ ⠀⠀ ⠀ ⠀⠀ ⠀ ⠀https://scrapbox.io/files/6866565cd2009ba2a3e5f660.png
(1) 手計算による解答例
1回かかる → 1回目に3が出るときなので，確率は$ \frac16．
2回かかる → 1回目に2が出れば2回目はどの目でもよい．1回目に1が出れば2回目は1以外．確率は$ \frac36\cdot 1 + \frac26\cdot\frac46=\frac{9+4}{18}=\frac{13}{18}
3回かかる → 1回目と2回目で1が出るとき（3回目はどの目でもよい）ので，確率は$ \left(\frac26\right)^2=\frac19．
⠀よって，求める期待値は$ 1\times\frac16 + 2\times\frac{13}{18}+3\times\frac19=\frac{3+26+6}{18}=\frac{35}{18}
(2) DP的発想による手計算による解法
⠀$ dp[i] を地点$ iからゴールに到着するまでにサイコロを投げた回数の期待値，として，ゴールから考えます．
$ dp[3] … ゴールに到着しているので，$ dp[3]=0
$ dp[2] … 必ずあと1回で3以上になるので，$ dp[2]=1
$ dp[1] … 1が出たら地点2に移動して，地点2からまた移動する．それ以外は1回でゴール．よって
⠀⠀⠀$ dp[1]=\frac26(1 + dp[2]) + \frac46\cdot 1 = 1+\frac26dp[2] = 1 + \frac13 = \frac43
$ dp[0] ... 1が出たら地点1，2が出たら地点2，3が出たらゴール．よって，
⠀⠀⠀$ dp[0] = \frac26(1+dp[1]) + \frac36(1+dp[2]) + \frac16\cdot 1 = 1+\frac26 dp[1]+\frac36 dp[2]
⠀⠀⠀⠀⠀⠀⠀⠀$ = 1+\frac49+\frac12=\frac{18+8+9}{18}=\frac{35}{18}
(3)DPで解くために表現を変更
⠀$ dp[i] の定義は(2)と同じです．各$ dp[i] の形式が揃うように書き換えます．すると，
$ dp[3] = 0 ... 初期化．
$ dp[2]= 1 + \frac26 dp[3] + \frac36 dp[3] + \frac16 dp[3]
$ dp[1] = 1 + \frac26 dp[2] + \frac36 dp[3] + \frac16 dp[3]
$ dp[0] = 1 + \frac26 dp[1] + \frac36 dp[2] + \frac16 dp[3]
となります．地点$ iから地点$ jに移動する確率を$ p_{i,j}とすると，
⠀⠀⠀$ dp[i] = 1 + \sum_j p_{i,j}\ dp[j]
と表すことができます（$ jは$ iから移動できる地点のみ）．
「1」が「1回移動」を表し，あとは確率×その後の移動回数の総和＝その後の期待値を表します．
2. 自己閉路がある問題
(0) 例題2
⠀$ \frac26の確率で1，$ \frac36の確率で2，$ \frac16の確率で 0 が出るサイコロがあります．現在，数直線上の地点0にいて，サイコロを振って出た目の分だけ右方向に移動します．地点3，またはそれより右に到着するまでに振ったサイコロの回数の期待値を求めなさい．（下の図では，3以上はまとめています．）
⠀ ⠀ ⠀⠀ ⠀ ⠀⠀ ⠀ ⠀⠀ ⠀ ⠀https://scrapbox.io/files/68666c38912e8a000b01d11d.png
(1) 例題1と同様にDPで解く
⠀上で求めた式を使います．例えば，地点0では次のようになります．
⠀⠀$ dp[0] = 1 + \frac26 dp[1] + \frac36 dp[2] + \frac16 dp[0]
右辺にも$ dp[0] があるので，このままだとDPで解けません．よって，$ dp[0] を移行して整理します．
⠀⠀$ \left( 1-\frac16\right)dp[0] = 1 + \frac26 dp[1] + \frac36 dp[2] \longleftrightarrow dp[0] = \frac65 + \frac25 dp[1] + \frac35 dp[2]
これで，DPで解くことができます．一般的に記すと次のようになります．
⠀⠀⠀$ dp[i] = 1 + \sum_{j\not= i} p_{i,j}\ dp[j] + p_{i,i}\ dp[i] \longleftrightarrow dp[i] = \frac1{1-p_{i,i}}\left( 1 + \sum_{j\not= i}p_{i,j}\ dp[j] \right) = \frac1{1-p_{i,i}} + \sum_{j\not= i}\frac {p_{i,j}}{1-p_{i,i}}\ dp[j]
まーす.iconこの数式の$ \sum_{j \neq i}の部分がよくわからないので，説明お願いします．例題2 の一般化をしているのであれば，サイコロを一回振った時の行動は，現状維持 or 右に移動の２種類なので$ \sum_{j > i}のようになるのでは？
まーす.icon上の自己閉路がない例では，$ N,\ N - 1,\ \dots,\ 0 の順に$ dp[i] を求めていると解釈したので，このように思った次第です．
CarpDay.icon確かに$ \sum_{j>i}ですね．ご指摘ありがとう．下の内容も含め，読み替えてください．
(2) 【蛇足】(1)の直感的な説明
⠀(1)で求めた式の意味を直感的に説明します．
$ \frac1{1-p_{i,i}} は，地点$ iを脱出するまでに必要な回数の期待値です．脱出するまでの回数は，成功確率$ 1-p_{i,i}の幾何分布に従います．期待値は成功確率の逆数です． (2)の例で言えば，地点0から脱出する確率は$ \frac56なので，脱出するまでに必要な回数の期待値は$ \frac65となります．
$ \frac {p_{i,j}}{1-p_{i,i}}は，地点$ iを脱出する条件下における，地点$ iから地点$ jに移動する確率です．
(2)の例で言えば，$ \frac25の確率で1つ移動，$ \frac35の確率で2つ移動です．
よって$ \sum_{j\not= i}\frac {p_{i,j}}{1-p_{i,i}}\ dp[j] は，地点$ iを脱出したあと，ゴールまでに必要な回数の期待値を表します．