メモ

yukicoderでゆるふわgolf

期待値

期待値=((I-P)^{-1} \textbf{1})_0
というだけの話なんですが、これしか頭にないと同じ式変形に毎回一生を費やしてしまうので典型的な用法をメモしておく。


問題:
S+1の状態があり、状態0から始めて、状態Sに到達したら終了。
1回の操作で状態iから状態jに遷移する確率がP_{i,j}のとき、終了するまでの操作回数の期待値は?

前置き:
グラフがDAG→DPしろ


本題に入る前に典型問題を一つ
問題:
裏が出るまでコイントスする。期待値何回?
答え:
n回目のコイントスをする確率が(1/2)^nだから、\sum_{n=0}^{\infty}(\frac{1}{2})^n=2

元の問題に戻る
P_{i,j}のi,j≠Sを並べてできる行列S×S行列をPとすると求める期待値は
\sum_{n=1}^{\infty}\text{$n$回目の操作を行う確率}\\
=\sum_{n=1}^{\infty}\text{$n-1$回目の操作後に状態$S$に到達しない確率}\\
=\sum_{n=0}^{\infty}\text{$n$回の操作で状態$S$に到達しない確率}\\
=\sum_{n=0}^{\infty}\sum_{v\neq S}\text{$n$回目の操作後に状態$v$である確率}\\
=\sum_{n=0}^{\infty}\sum_{v}P^n\text{の$(0,v)$成分}\\
=\sum_{v}\sum_{n=0}^{\infty}P^n\text{の$(0,v)$成分}\\
=\sum_{v}(\sum_{n=0}^{\infty}P^n)\text{の$(0,v)$成分}\\
=\sum_{v}(I-P)^{-1}\text{の$(0,v)$成分}
求まった。


問題2:
S+1の状態があり、状態0から始めて、状態Sに到達したら終了。
1回の操作で状態iから状態jに遷移する確率がP_{i,j}であり、このときコストC_{i,j}がかかる。終了するまでのコスト期待値は?

P_{i,j}のi,j≠Sを並べてできる行列S×S行列をP、i≠S並べてできるS×(S+1)行列をQとすると求める期待値は

\sum_{n=1}^{\infty}\sum_{(u,v)}\text{$n$回目の操作で状態$u$から$v$に遷移する確率}\times C_{u,v}\\
=\sum_{n=1}^{\infty}\sum_{(u,v)} P^{n-1} \text{の$(0,u)$成分} \times Q_{u,v}\times C_{u,v}\\
=\sum_{n=0}^{\infty}\sum_{(u,v)} P^n \text{の$(0,u)$成分} \times Q_{u,v}\times C_{u,v}\\
=\sum_{(u,v)}\sum_{n=0}^{\infty} P^n \text{の$(0,u)$成分} \times Q_{u,v}\times C_{u,v}\\
=\sum_{(u,v)}(\sum_{n=0}^{\infty} P^n )\text{の$(0,u)$成分} \times Q_{u,v}\times C_{u,v}\\
=\sum_{(u,v)}(I-P)^{-1}\text{の$(0,u)$成分} \times Q_{u,v}\times C_{u,v}\\
=\sum_{(u,v)}(I-P)^{-1}\text{の$(0,u)$成分} \times (Q\circ C)_{u,v}\\
=\sum_{v}\sum_{u}(I-P)^{-1}\text{の$(0,u)$成分} \times (Q\circ C)_{u,v}\\
=\sum_{v}(I-P)^{-1}(Q\circ C)\text{の$(0,v)$成分}
求まった。ここで\circアダマール積(element-wise product)を表す。