期待値 - メモ

期待値= $((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)$成分}$
求まった。

問題２：
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)を表す。

問題３：
S+Kの状態があり、状態0から始めて、状態x≧Sに到達したら終了。
1回の操作で状態iから状態jに遷移する確率が $P_{i,j}$ であり、状態S+kで終了するまでの操作回数の条件付き期待値は？

$P_{i,j}$ のi,j< Sを並べてできる行列S×S行列をP、i< S,j≧Sを並べてできるS×K行列をRとすると求める期待値は
$(I-P)^{-2}Rの(0,k)成分÷(I-P)^{-1}Rの(0,k)成分$
になる。
第1項は「終了までの操作回数の期待値のうち、状態S+kで終了するものの寄与分」で、
$\sum_{n,i}nP^{n-1}の(0,i)成分×Rの(i,k)成分$
第2項は「終了したときの状態がS+kである確率」