probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...

, Foster's theorem, named after

Gordon Foster Frederic Gordon Foster (24 February 1921 – 20 December 2010) was an Irish computational engineer, statistician, professor, and college dean who is widely known for devising, in 1965, a nine-digit code upon which the International Standard Boo ...

, is used to draw conclusions about the positive recurrence of

Markov chains A Markov chain or Markov process is a stochastic process, stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought ...

with

countable In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...

state spaces. It uses the fact that positive recurrent Markov chains exhibit a notion of "

Lyapunov stability Various types of stability may be discussed for the solutions of differential equations or difference equations describing dynamical systems. The most important type is that concerning the stability of solutions near to a point of equilibrium. ...

" 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 In mathematics, a stochastic matrix is a square matrix used to describe the transitions of a Markov chain. Each of its entries is a nonnegative real number representing a probability. It is also called a probability matrix, transition 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 In the theory of ordinary differential equations (ODEs), Lyapunov functions, named after Aleksandr Lyapunov, are scalar functions that may be used to prove the stability of an equilibrium of an ODE. Lyapunov functions (also called Lyapunov’s se ...

V: S \to \mathbb

, such that

V(i) \geq 0 \text \forall \text i \in S

and #

\sum_p_V(j) <

for

i \in F

\sum_p_V(j) \leq V(i) - \varepsilon

for all

i \notin F

for some finite set ''F'' and strictly positive ''ε''.

References

Theorems regarding stochastic processes Markov processes {{probability-stub

Theorem

Related links

References