Foster's theorem explained

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 p _{ij} 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 V: S \to R , such that V(i) \geq 0 \forall i \in S and\sum _{j} p _{ij} V(j) < { inf ty} for i \in F \sum _{j} p _{ij} V(j) \leq V(i) - \varepsilon for all i \notin F

for some finite set

F and strictly positive \varepsilon .^[2]

Related links

• Lyapunov optimization

Notes and References

1. 10.1214/aoms/1177728976. On the Stochastic Matrices Associated with Certain Queuing Processes. The Annals of Mathematical Statistics. 24. 3. 355. 1953. Foster . F. G.. 2236286. free.
2. Book: 10.1007/978-1-4757-3124-8_5. Lyapunov Functions and Martingales. Markov Chains. limited. 167. 1999. Brémaud . P. . 978-1-4419-3131-3.