フォスターの定理

確率論では、ゴードン・フォスターにちなんで名付けられたフォスターの定理^[1]は、可算状態空間を持つマルコフ連鎖の正の再帰性についての結論を導くために使用されます。これは、正の再帰性マルコフ連鎖が、有限の時間間隔内で任意の状態から開始してその状態に戻るという点で 「リアプノフ安定性」の概念を示すという事実を利用しています。

のペア の要素を持つ遷移確率行列を持つ可算状態空間上の既約離散時間マルコフ連鎖を考える。フォスターの定理によれば、マルコフ連鎖が正の再帰的であるためには、次を満たすリャプノフ関数が存在しなければならない。 ${\displaystyle S}$ ${\displaystyle P}$${\displaystyle p_{ij}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle S}$ ${\displaystyle V:S\to \mathbb {R} }$${\displaystyle V(i)\geq 0{\text{}}\forall {\text{}}i\in S}$

1. ${\displaystyle \sum _{j\in S}p_{ij}V(j)<{\infty }}$のために${\displaystyle i\in F}$
2. ${\displaystyle \sum _{j\in S}p_{ij}V(j)\leq V(i)-\varepsilon }$全ての${\displaystyle i\notin F}$

ある有限集合に対して、かつ厳密に正である。^[2]${\displaystyle F}$${\displaystyle \epsilon }$

• リャプノフ最適化