期待値に関するメモ
ある状態$ A_iから目標の状態までに行くまでの操作回数の期待値を$ X_iとおく。
状態$ A_0から一回の遷移によって独立な$ N + 1個の状態$ A_0,A_1,A_2,\cdots,A_Nに遷移するとき、$ A_0,A_1,A_2,\cdots,A_Nに遷移する確率を$ R_0,R_1,R_2,\cdots,R_Nとすると、
$ X_0 = 1 + X_0R_0 + X_1R_1 + X_2R_2 + \cdots + X_NR_N
が成り立つ。
しかし、両辺に求めるべき$ X_0が出てくるのは不便なので、移項して
$ X_0 = 1 / (1 - R_0) + X_1R_1 / (1 - R_0) + X_2R_2 / (1 - R_0) + \cdots X_NR_N / (1 - R_0)
とすると、DP遷移がしやすくなる。
感覚的には分からないことはないけど、これって自明なの？