Foster's theorem

{{Expert-subject|Mathematics|date=February 2009|reason=Needs a proof adding}}

{{ about|the theorem in Markov probability theory|the theorem in electrical engineering|Foster's reactance theorem}}

In probability theory, Foster's theorem, named after Gordon Foster,{{Cite journal | doi = 10.1214/aoms/1177728976| title = On the Stochastic Matrices Associated with Certain Queuing Processes| journal = The Annals of Mathematical Statistics| volume = 24| issue = 3| pages = 355–360| year = 1953| last1 = Foster | first1 = F. G.| jstor = 2236286| doi-access = free}} 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 \mathbb{R}$ , such that $V(i) \geq 0 \text{ } \forall \text{ } i \in S$ and

$\sum_{j \in S}p_{ij}V(j) < {\infty}$ for $i \in F$
$\sum_{j \in S}p_{ij}V(j) \leq V(i) - \varepsilon$ for all $i \notin F$

for some finite set $F$ and strictly positive $\varepsilon$ .{{Cite book | doi = 10.1007/978-1-4757-3124-8_5| chapter = Lyapunov Functions and Martingales| title = Markov Chains| url = https://archive.org/details/markovchainsgibb00brem_688| url-access = limited| pages = [https://archive.org/details/markovchainsgibb00brem_688/page/n182 167]| year = 1999| last1 = Brémaud | first1 = P. | isbn = 978-1-4419-3131-3}}

References

Category:Theorems about stochastic processes

Category:Markov processes

Foster's theorem

Theorem

Related links

References