8.4 Transient and recurrent states

Let \(\{X_n : n \ge 0\}\) be a Markov chain with state space \(\mathbf E\), and let \[ e_{ij} = P_i(T_j < \infty ) . \] Then \(e_{ij}\) is the probability that the chain, started in state \(i\), will be in state \(j\) at some positive time. In particular, \(e_{jj}\) is the probability that the chain, started in state \(j\), ever returns to \(j\).

Definition 8.4.1. A state \(j\) is recurrent if \(e_{jj} = 1\), and transient if \(e_{jj} < 1\).

If \(j\) is recurrent, a chain started at \(j\) returns to \(j\) with probability one. If \(j\) is an absorbing state, that is \(P_{jj} = 1\), then \(P_j(T_j = 1) = P_{jj} = 1\) and hence \(e_{jj} = 1\); so an absorbing state is necessarily recurrent.

To count visits, let \(I_j\) be the indicator of state \(j\), \[ I_j(k) = \begin {cases} 1 , & k = j , \\ 0 , & k \ne j , \end {cases} \] and let \(N(j)\) be the number of times \(n \ge 1\) that the chain is in state \(j\): \[ N(j) = \sum _{n=1}^\infty I_j(X_n) . \] The event \(\{N(j) \ge 1\}\) is the same as the event \(\{T_j < \infty \}\), so \[ P_i\bigl (N(j) \ge 1\bigr ) = P_i(T_j < \infty ) = e_{ij} . \] Let \(m\) and \(n\) be positive integers. By the Markov property, the probability that a chain started at \(i\) first visits \(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\bigl (N(j) \ge 2\bigr ) &= \sum _{m=1}^\infty \sum _{n=1}^\infty P_i(T_j = m)P_j(T_j = n) \\ &= \sum _{m=1}^\infty P_i(T_j = m)\sum _{n=1}^\infty P_j(T_j = n) = e_{ij}e_{jj} , \end {align*}

and, repeating the argument, \[ P_i\bigl (N(j) \ge m\bigr ) = e_{ij}e_{jj}^{m-1} , \qquad m \ge 1 . \] Consequently, for \(m \ge 1\), \[ P_i\bigl (N(j) = m\bigr ) = P_i\bigl (N(j) \ge m\bigr ) - P_i\bigl (N(j) \ge m + 1\bigr ) = e_{ij}e_{jj}^{m-1}(1 - e_{jj}) , \] and \[ P_i\bigl (N(j) = 0\bigr ) = 1 - P_i\bigl (N(j) \ge 1\bigr ) = 1 - e_{ij} . \]

Let \(E_i\) denote expectation for the chain started in state \(i\). Since \[ E_i\bigl (I_j(X_n)\bigr ) = P_i(X_n = j) = P^{(n)}_{ij} , \] the expected number of visits to \(j\) is \[ G_{ij} = E_i\bigl (N(j)\bigr ) = E_i\Bigl (\sum _{n=1}^\infty I_j(X_n)\Bigr ) = \sum _{n=1}^\infty E_i\bigl (I_j(X_n)\bigr ) = \sum _{n=1}^\infty P^{(n)}_{ij} . \] So \(G_{ij}\) is the expected number of visits to state \(j\) by a chain started in state \(i\).

Theorem 8.4.2.

(i): Let \(j\) be a transient state. Then \[ P_i\bigl (N(j) < \infty \bigr ) = 1 \qquad \text {and}\qquad 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\bigl (N(j) = \infty \bigr ) = 1\), and \(P_i\bigl (N(j) = \infty \bigr ) = 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 the two kinds of state is this. If \(j\) is transient, the chain makes only a finite number of visits to \(j\), no matter where it starts, and the expected number of visits is finite. If \(j\) is recurrent and the chain starts at \(j\), it returns to \(j\) infinitely often; if the chain starts at some other state \(i\), it may be impossible for it ever to hit \(j\), but if it does visit \(j\) at least once, then it does so infinitely often.

A Markov chain is called a transient chain if all its states are transient, and a recurrent chain if all its states are recurrent.

Remark. A Markov chain with a finite state space must have at least one recurrent state, and hence cannot be a transient chain.

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

Example 8.4.4 (A Markov chain that is a martingale). Consider a Markov chain with state space \(\{0, 1, 2, \dots , M\}\) whose transition probabilities satisfy \[ \sum _{j=0}^MjP_{ij} = i , \qquad i = 0, 1, 2, \dots , M , \] that is, \(E(X_n \mid X_{n-1} = i) = i\). Then, by the Markov property, \begin {align*} &E(X_n \mid X_{n-1} = i, X_{n-2} = i_{n-2}, \dots , X_0 = i_0) \\ &\quad = \sum _{j=0}^MjP(X_n = j \mid X_{n-1} = i, X_{n-2} = i_{n-2}, \dots , X_0 = i_0) \\ &\quad = \sum _{j=0}^MjP(X_n = j \mid X_{n-1} = i) = \sum _{j=0}^MjP_{ij} = i . \end {align*}

So the expected value of \(X_n\), given the past and present values \(X_0, X_1, \dots , X_{n-1}\), is the present value \(X_{n-1}\). A sequence of random variables with this property is called a martingale; martingales are the subject of the next section. The gambler’s ruin chain of Example 8.3.2 with \(p = \frac 12\) is an example.

Questions on this section

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