Jump to content

Foster's theorem

From Wikipedia, the free encyclopedia

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

[edit]

Consider an irreducible discrete-time Markov chain on a countable state space having a transition probability matrix with elements for pairs , in . Foster's theorem states that the Markov chain is positive recurrent if and only if there exists a Lyapunov function , such that and

  1. for
  2. for all

for some finite set and strictly positive .[2]

[edit]

References

[edit]
  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.