In probability theory, Foster's theorem, named after Gordon Foster, is used to draw conclusions about the positive recurrence of Markov chains with countable state spaces. It uses the fact that positive recurrent Markov chains exhibit a notion of "Lyapunov stability" in terms of returning to any state while starting from it within a finite time interval.
Theorem Consider an irreducible discrete-time Markov chain on a countable state space S {\displaystyle S} having a transition probability matrix P {\displaystyle P} with elements p i j {\displaystyle p_{ij}} for pairs i {\displaystyle i} , j {\displaystyle j} in S {\displaystyle S} . Foster's theorem states that the Markov chain is positive recurrent if and only if there exists a Lyapunov function V : S → R {\displaystyle V:S\to \mathbb {R} } , such that V ( i ) ≥ 0 ∀ i ∈ S {\displaystyle V(i)\geq 0{\text{ }}\forall {\text{ }}i\in S} and
∑ j ∈ S p i j V ( j ) < ∞ {\displaystyle \sum _{j\in S}p_{ij}V(j)<{\infty }} for i ∈ F {\displaystyle i\in F}
∑ j ∈ S p i j V ( j ) ≤ V ( i ) − ε {\displaystyle \sum _{j\in S}p_{ij}V(j)\leq V(i)-\varepsilon } for all i ∉ F {\displaystyle i\notin F}
for some finite set F {\displaystyle F} and strictly positive ε {\displaystyle \varepsilon } .
Related links Lyapunov optimization
References