Foster's theorem

This article is about the theorem in Markov probability theory. For the theorem in electrical engineering, see Foster's reactance 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 ${\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]

Related links

• Lyapunov optimization

References

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