# Foster's theorem

In probability theory, Foster's theorem, named after Gordon Foster,[1] 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 having a transition probability matrix P with elements pij for pairs i, j in 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 F and strictly positive ε.[2]