Foster's theorem

Consider an irreducible discrete-time Markov chain on a countable state space ${\displaystyle S}$ having a transition probability matrix ${\displaystyle P}$ with elements ${\displaystyle p_{ij}}$ for pairs ${\displaystyle i}$, ${\displaystyle j}$ in ${\displaystyle S}$. Foster's theorem states that the Markov chain is positive recurrent if and only if there exists a Lyapunov function ${\displaystyle V:S\to \mathbb {R} }$, such that ${\displaystyle V(i)\geq 0{\text{ }}\forall {\text{ }}i\in S}$ and

1. ${\displaystyle \sum _{j\in S}p_{ij}V(j)<{\infty }}$ for ${\displaystyle i\in F}$
2. ${\displaystyle \sum _{j\in S}p_{ij}V(j)\leq V(i)-\varepsilon }$ for all ${\displaystyle i\notin F}$

for some finite set ${\displaystyle F}$ and strictly positive ${\displaystyle \varepsilon }$.[2]

• Lyapunov optimization