8.4 Transient and Recurrent States

Let \(X_n\), \(n\geq 0\) be a Markov chain having state space \(\mathbf {E}\) and let \[P_{ij}=P-i(T_j<\infty )\hspace {0.3cm}....\hspace {0.2cm} 4.3.1\] Then \(e_{ij}\) denotes the probability that a Markov chain starting in state \(i\) will be in state \(j\) at some positive. In particular, \(e_{ij}\) denotes the probability that a Markov chain in state \(j\) will return to state \(j\).

A state \(j\) is called recurrent if \(e_{ij}=1\).

A state \(j\) is called transient state if \(e_{ij}<1\).

If \(j\) is recurrent state, a Markov chain starting at state \(j\) returns to state \(j\) with probability one.

If \(j\) is an absorbing state, then \(P_i(T_j=1)=P_{jj}=1\) and hence \(e_{ij}=1\). Thus an absorbing state is necessary a recurrent state. \[ I_j(k)= \begin {cases} 1, &\text {if}\hspace {0.4cm} k=j\\\\ 0,&\text {if}\hspace {0.4cm} k\neq j \end {cases} \] and \(N(j)\) to denote the number of times \(n\geq 1\) that the chain is in state \(j\). \[\text {The}\hspace {0.4cm} N(j)=\sum ^{\infty }_{n=1}I_j(X_n)\] The event \(\{N(j)\geq 1\}\) is the same as the event \(\{T_j<\infty \}\), therefore \[P_i(N(j)\geq 1)=P_i(T_j<\infty )=e_{ij}\hspace {0.3cm} .....\hspace {0.2cm} 4.3.2\]

Let \(m\) and \(n\) be positive integers, then the probability that a Markov chain starting at state \(i\) first visits state \(j\) at time \(m\) and next visits \(j\), \(n\) units of time later is \[P_i(T_j=m)P_j(T_j=n).\] Therefore

\begin {align*} P_i (N(j)\geq 2) &=\sum ^{\infty }_{m=1}\sum ^{\infty }_{n=1}P_i(T_j=m)P_j(T_j=n)\\ &=\sum ^{\infty }_{m=1}P_i(T_j=m)\sum ^{\infty }_{n=1}P_j(T_j=n).\\\\ P_i(N(j)\geq 2) &=e_{ij}e_{jj}.\\\\ P_i(N(j)\geq m) &=e_{ij}e^{m-1}_{jj}\\\\ P_i(N(j)=m) &=P_i(N(j)\geq m)-P_i(N(j)\geq m+1)\\ &=e_{ij}e^{m-1}_{jj}-e_{ij}e^m_{jj}\\ &=e_{ij}e^{m-1}_{jj}(1-e_{jj})\hspace {0.5cm}.......\hspace {0.2cm} 4.3.3\\\\ P_i(N(j)=0) &=1-P_i(N(j)\geq 1)\\ &=1-e_ij\\ \implies \hspace {0.4cm} P_i(N(j)=0) &=1-e_{ij}\hspace {0.4cm}.......\hspace {0.3cm} 4.0.4\\ \end {align*}

Let \(E_i()\) be the expectation of random variables defined in terms of Markov chain starting in state \(i\). \begin {align*} E_i(I_j(X_n)) &=P_i(X_n=j)=P^{(n)}_{ij}\\ &=P\{X_n=j/X_0=i\}\\\\\\ E_i(N(j)) &=E_i\Bigg (\sum ^{\infty }_{n=1}I_j(X_n)\Bigg )\\ &=\sum ^{\infty }_{n=1}E_i(I_j(X_n))\\ &=\sum ^{\infty }_{n=1}P_{ij}^{(n)}\hspace {0.4cm}.......\hspace {0.3cm} 4.3.4\\ \end {align*}

\[\text {Set}\hspace {0.5cm}G_{ij}=E_i(N(j))=\sum ^{\infty }_{n=1}P_{ij}^{(n)}\hspace {0.5cm}...........\hspace {0.3cm} 4.3.4\] Then \(G_{ij}\) denotes the expected number of visits to state \(j\) for a Markov chain starting at state \(i\).

Theorem 8.4.1.

i: Let \(j\) be a transient state, then \[P_i(N(j)<\infty )=1\hspace {0.4cm}\text {and}\hspace {0.4cm} G_{ij}=\frac {e_{ij}}{1-e_{jj}}\] which is finite for all \(i\in \mathbf {E}\).
ii: Let \(j\) be a recurrent state, then \(P_j=(N(j)=\infty )=1\).

Also \(P_i(N(j)=\infty )=P_i(T_j<\infty )=e_{ij}\). If \(e_{ij}=0\), then \(G_{ij}=0\), while if \(e_{ij}>0\) then \(G_{ij}=\infty \).

Remark. The fundamental difference between a transient and recurrent state is that \(j\) is transient state if the Markov chain only makes a finite number of visits to state \(j\) (no matter where the chain starts from) and the expected number of visits to state \(j\) is finite.
Suppose that \(j\) is recurrent state, then if the Markov chain starts in state \(j\), it returns to \(j\) infinitely often, while if the chain starts at some other state \(i\), it may be impossible for it to ever hit \(j\). If it is possible the chain does visit \(j\) at least once, then it does so infinitely often.

\(\rightarrow \): A Markov chain is called a transient chain if all its states are transient states.
\(\rightarrow \): A Markov chain is a recurrent chain if all its states are recurrent.

Remark. A Markov Chain having finite state space must have at least one recurrent state and hence can not possibly be a transient chain.

Theorem 8.4.2. Let state \(i\) be recurrent state and suppose that \(i\) leads to \(j\) \((e_{ij}>0)\), then \(j\) is recurrent state and \(e_{ij}=e_{ji}=1\).

Consider a Markov chain having state space \(\{0,1,2,\dots ,M\}\) such that \[\sum ^{M}_{j=0}jP_{ij}=i,\hspace {0.5cm} i=0,1,2,3,\dots , d\] \[\implies \hspace {0.5cm} E\Big (X_n/X_{n-1}=i\Big )=i\hspace {0.7cm}\text {satisfies this condition is a Martingale}\] Now, \begin {align*} E\Big \{X_n/X_{n-1}=i, X_{n-2}=i_{n-2},\dots ,X_1=i_1,X_0=i_0\Big \}\\ =\sum _{j=0}^MjP\Big \{X_n=j/X_{n-1}=i,X_{n-2}=i_{n-2},\dots ,X_i=i_1,X_0-i_0\Big \}\\ =\sum ^M_{j=0}jP\Big \{X_n=j/X_{n-1}=i\Big \} =\sum ^M_{j=0}jP_{ij} =i\\ \end {align*}

The expected value of \(X_n\) given the past and present values of \(X_0,X_1,\dots ,X_{n-1}\)

A sequence of random variables having this property is called martingale.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.