View source for Markov chain, ergodic

A homogeneous [[Markov chain|Markov chain]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m0623901.png" /> with the following property: There are quantities (independent of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m0623902.png" />)

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m0623903.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m0623904.png" /></td> </tr></table>

are the [[Transition probabilities|transition probabilities]]. The distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m0623905.png" /> on the state space of the chain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m0623906.png" /> is called a stationary distribution: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m0623907.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m0623908.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m0623909.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239011.png" />. A fundamental property of Markov chains,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239012.png" /></td> </tr></table>

enables one to find the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239013.png" /> without calculating the limits in (1).

Let

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239014.png" /></td> </tr></table>

be the moment of first return to the state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239015.png" /> (for a discrete-time Markov chain), then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239016.png" /></td> </tr></table>

A similar (more complicated) relation holds for a continuous-time Markov chain.

The trajectories of an ergodic Markov chain satisfy the ergodic theorem: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239017.png" /> is a function on the state space of the chain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239018.png" />, then, in the discrete-time case,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239019.png" /></td> </tr></table>

while in the continuous-time case the sum on the left is replaced by an integral. A Markov chain for which there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239021.png" /> such that for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239022.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239023.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

is called geometrically ergodic. A sufficient condition for geometric ergodicity of an ergodic Markov chain is the Doeblin condition (see, for example, [[#References|[1]]]), which for a discrete (finite or countable) Markov chain may be stated as follows: There are an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239024.png" /> and a state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239025.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239026.png" />. If the Doeblin condition is satisfied, then for the constants in (2) the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239027.png" /> holds.

A necessary and sufficient condition for geometric ergodicity of a countable discrete-time Markov chain is the following (see [[#References|[3]]]): There are numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239029.png" /> and a finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239030.png" /> of states such that:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239031.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062390/m06239032.png" /></td> </tr></table>

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J.L. Doob,   "Stochastic processes" , Wiley  (1953)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  K.L. Chung,   "Markov chains with stationary transition probabilities" , Springer  (1967)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  N.N. Popov,   "Conditions for geometric ergodicity of countable Markov chains"  ''Soviet Math. Dokl.'' , '''18''' :  3  (1977)  pp. 676–679  ''Dokl. Akad. Nauk SSSR'' , '''234''' :  2  (1977)  pp. 316–319</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D. Freedman,   "Markov chains" , Holden-Day  (1975)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M. Iosifescu,   "Finite Markov processes and their applications" , Wiley  (1980)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.G. Kemeny,   J.L. Snell,   "Finite Markov chains" , v. Nostrand  (1960)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J.G. Kemeny,   J.L. Snell,   A.W. Knapp,   "Denumerable Markov chains" , Springer  (1976)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D. Revuz,   "Markov chains" , North-Holland  (1975)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  V.I. [V.I. Romanovskii] Romanovsky,   "Discrete Markov chains" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  E. Seneta,   "Non-negative matrices and Markov chains" , Springer  (1981)</TD></TR></table>