A Practical Route to Recurrence Classification
Classifying a chain state by state is most reliable when three questions are kept separate: what is the probability of ever returning, what is the expected number of visits, and which other states communicate with it? The first two questions are connected by a return-series identity. The third organizes the answer: in a communicating class, recurrence is shared by every state. We develop those tools and apply them to a finite reducible chain and two chains on the integers.
Throughout, a discrete-time Markov chain \((X_n)_{n\ge0}\) is defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with finite or countable state space \(S\) and transition probabilities \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\). Each transition row sums to \(1\). Write \(\mathbb{P}_i\) for probability when \(X_0=i\), and let \(p_{ij}^{(n)}=\mathbb{P}_i(X_n=j)\). In particular, \(p_{ii}^{(0)}=1\).
The return series adds the probabilities of being at \(i\) at each time; it does not add first-return probabilities. Its value is the expected total number of visits to \(i\), counting time zero. The following result is the main computational bridge between the two quantities.
Proof. Let \(V_i=\sum_{n\ge0}\mathbf{1}_{\{X_n=i\}}\) be the total number of visits to \(i\) when the chain starts at \(i\). For an integer \(r\ge1\), the event \(V_i\ge r\) means that there are at least \(r-1\) returns after time zero. At each return, the chain starts afresh from \(i\), so the probability of another finite return is \(f_i\). More explicitly, the Markov property at a return time follows by partitioning according to its possible finite values and applying the ordinary Markov property at each deterministic time. Applying this argument successively gives \(\mathbb{P}_i(V_i\ge r)=f_i^{r-1}\). For a nonnegative integer-valued variable, including one that may be infinite, \(\mathbb{E}_i[V_i]=\sum_{r\ge1}\mathbb{P}_i(V_i\ge r)\); hence \(\mathbb{E}_i[V_i]=\sum_{r\ge1}f_i^{r-1}\). Also, by summing the nonnegative indicators defining \(V_i\), \(\mathbb{E}_i[V_i]=\sum_{n\ge0}\mathbb{P}_i(X_n=i)=R_i\). The geometric series is \(1/(1-f_i)\) if \(f_i<1\), and diverges if \(f_i=1\). This proves each assertion. \(\square\)
Communication provides a second organizing principle. A communicating class is a maximal set of states whose members communicate with one another. A class need not be closed: a chain can leave it for another class without any route back. Recurrence, however, is shared within a communicating class.
Proof. The case \(i=j\) is immediate, so take distinct communicating states \(i,j\). First, from any state \(k\) communicating with \(i\), the chain hits \(i\) with probability \(1\). To see this, choose a positive-probability path from \(i\) to \(k\) with no internal visit to \(i\), by deleting loops from a path if necessary. If there were positive probability, starting at \(k\), of never hitting \(i\), following this path and then avoiding \(i\) would give a positive probability of no return to \(i\) from \(i\). That contradicts recurrence of \(i\). Thus \(\mathbb{P}_k(T_{\{i\}}<\infty)=1\).
Next, from \(i\), the chain hits \(j\) with probability \(1\). Choose a finite path from \(i\) to \(j\) with positive probability and no internal visit to \(i\); let its probability be \(c>0\). Since \(i\) is recurrent, after each return to \(i\) the chain has another opportunity to follow this path. The probability of failing on the first \(m\) such opportunities is at most \((1-c)^m\), which tends to \(0\). So \(j\) is hit almost surely from \(i\). Starting at \(j\), the chain hits \(i\) almost surely by the first part, and then hits \(j\) almost surely by the second part. Therefore its first return to \(j\) is finite with probability \(1\), so \(j\) is recurrent. If a communicating class had both a recurrent state and a transient state, this implication would be contradicted; hence the final assertion follows. \(\square\)
Worked Classifications
Worked Example: A Finite Chain with Three Different Outcomes
Consider \(S=\{0,1,2,3\}\). From \(0\), the chain moves to \(1\) with probability \(1\). From \(1\), it moves to \(0\) or \(2\), each with probability \(\tfrac12\). State \(2\) stays at \(2\) with probability \(1\), and state \(3\) moves to \(2\) with probability \(1\). Each row sums to \(1\): the four row sums are \(1\), \(\tfrac12+\tfrac12=1\), \(1\), and \(1\).
States \(0\) and \(1\) communicate, since \(0\to1\) and \(1\to0\) both have positive probability. Starting at \(0\), a return requires the path \(0\to1\to0\), whose probability is \(1\cdot\tfrac12=\tfrac12\). Thus \(f_0=\tfrac12\). Starting at \(1\), a return requires the path \(1\to0\to1\), also of probability \(\tfrac12\cdot1=\tfrac12\); the alternative move to \(2\) prevents a return. Thus \(f_1=\tfrac12\). The return-series criterion gives \(R_0=R_1=1/(1-\tfrac12)=2\), so both states are transient.
State \(2\) returns at time \(1\) with probability \(1\), so \(f_2=1\) and \(R_2=\infty\). State \(3\) leaves for \(2\) at time \(1\) and can never return, so \(f_3=0\). Since \(p_{33}^{(0)}=1\) and \(p_{33}^{(n)}=0\) for every \(n\ge1\), \(R_3=1\). State \(2\) is a recurrent singleton class; state \(3\) is a transient singleton class; and \(\{0,1\}\) is a transient communicating class that is not closed.
Check: For states \(0\) and \(1\), the computed return probability \(\tfrac12\) gives return-series sum \(1+\tfrac12+\tfrac14+\cdots=2\). For state \(3\), only the time-zero term contributes, agreeing with \(R_3=1\).
Worked Example: The Simple Symmetric Random Walk on the Integers
Let \(S=\mathbb{Z}\), and from every \(k\in\mathbb{Z}\) move to \(k+1\) or \(k-1\), each with probability \(\tfrac12\). Every transition row sums to \(\tfrac12+\tfrac12=1\). The chain is irreducible: from any integer to any other there is a finite path of steps in the required direction, with positive probability.
Starting at \(0\), a return is possible only at an even time. For \(n\ge1\), returning at time \(2n\) requires exactly \(n\) steps right and \(n\) steps left, so \(p_{00}^{(2n)}=\binom{2n}{n}/2^{2n}=\binom{2n}{n}/4^n\); also \(p_{00}^{(0)}=1\), and \(p_{00}^{(2n+1)}=0\). Introduce the return-series generating function \(U(s)=\sum_{m\ge0}p_{00}^{(m)}s^m\) for \(0\le s<1\). The binomial series gives
Let \(F(s)=\mathbb{E}_0[s^{T_0^+}\mathbf{1}_{\{T_0^+<\infty\}}]\). Decomposing a visit at time \(m\ge1\) by its first return time gives \(p_{00}^{(m)}=\sum_{r=1}^{m}\mathbb{P}_0(T_0^+=r)p_{00}^{(m-r)}\). Multiplying by \(s^m\) and summing the nonnegative terms yields \(U(s)-1=F(s)U(s)\), hence \(F(s)=1-1/U(s)=1-\sqrt{1-s^2}\). As \(s\) increases to \(1\), the terms defining \(F(s)\) increase to the first-return probabilities’ sum, so \(f_0=F(1-)=1\). Thus \(0\) is recurrent, and the recurrence class property shows that every integer is recurrent.
Check: The return series is \(R_0=\lim_{s\uparrow1}U(s)=\lim_{s\uparrow1}1/\sqrt{1-s^2}=\infty\), in agreement with the return-series criterion.
Worked Example: A Biased Walk with a Transient Communicating Class
Let \(S=\mathbb{Z}\), with a move one step right of probability \(p=\tfrac23\) and one step left of probability \(q=\tfrac13\) from every state. Each row sums to \(p+q=\tfrac23+\tfrac13=1\), and all integers communicate. We compute the first-return probability at \(0\).
First find the probability of hitting \(0\) from \(1\). On the finite interval \(\{0,1,\ldots,M\}\), let \(h_x^{(M)}\) be the probability, starting at \(x\), of hitting \(0\) before \(M\). It satisfies \(h_0^{(M)}=1\), \(h_M^{(M)}=0\), and \(h_x^{(M)}=p h_{x+1}^{(M)}+q h_{x-1}^{(M)}\) for \(1\le x<M\). Put \(r=q/p=\tfrac12\). Solving this difference equation gives \(h_x^{(M)}=(r^x-r^M)/(1-r^M)\): the expression has the stated boundary values, and substitution into the recurrence verifies it because \(p r+q/r=q+p=1\). The bounded-interval solution is unique, since a maximum or minimum of the difference of two solutions cannot be attained strictly inside unless that difference is constant; the zero boundary values then force it to be zero. For \(x=1\), as \(M\to\infty\), \(h_1^{(M)}\to r=\tfrac12\). The events “hit \(0\) before \(M\)” increase to “ever hit \(0\)” as \(M\) increases: any finite path that hits \(0\) has a finite maximum. Therefore the probability of ever hitting \(0\) from \(1\) is \(\tfrac12\).
From \(-1\), the probability of hitting \(0\) is \(1\). Indeed, on \(\{-M,-M+1,\ldots,0\}\), the probability from \(-1\) of hitting \(0\) before \(-M\) is \((1-r^{M-1})/(1-r^M)\), which tends to \(1\) as \(M\to\infty\); these events increase to eventual hitting of \(0\). After leaving \(0\), the first step is right with probability \(\tfrac23\) and left with probability \(\tfrac13\). Consequently,
Thus \(0\) is transient, and the return-series criterion gives \(R_0=1/(1-\tfrac23)=3\). Translation invariance gives the same first-return probability and return-series sum at every integer. Hence the entire communicating class \(\mathbb{Z}\) is transient.
Check: The probability of no return after leaving \(0\) is \(1-f_0=1-\tfrac23=\tfrac13\), and \(1/(1-f_0)=1/(\tfrac13)=3\), as computed.
Using the Criteria Without Confusing Them
For a finite chain, first identify communication classes and determine whether transitions can leave each class. Then compute first-return probabilities or return-series sums only where needed. A finite closed irreducible class is recurrent, a standard result from the earlier material on recurrence in finite chains; a class that can be left may still be recurrent or transient, so its return behavior must be checked. In a countable chain, do not infer recurrence merely from the fact that every state communicates with every other: the biased walk above is irreducible and transient.
Common mistake. In the finite example, one might incorrectly call state \(1\) recurrent because it can move to \(0\) and then return to \(1\). That calculation omits the other first step: from \(1\), the chain moves to \(2\) with probability \(\tfrac12\), after which it can never return. The correct first-return probability is \(\mathbb{P}_1(T_1^+<\infty)=\tfrac12\cdot1+\tfrac12\cdot0=\tfrac12\), not \(1\). The return series is then \(2\), not infinity.
A second common error is to start the return series at \(n=1\). By convention here, \(R_i\) includes \(p_{ii}^{(0)}=1\), so the transient state \(3\) in the finite example has \(R_3=1\), not \(0\). Keeping the definitions separate prevents both errors: \(f_i\) concerns the first return after time zero, while \(R_i\) counts all visits including the initial one.
Check Your Understanding
For each question, state whether the return probability or the return series is being requested, and include time zero in a return series.
- In the finite chain above, what is the probability that state \(1\) returns to itself in exactly two steps? Why is that not its first-return probability?
- If a state has first-return probability \(f_i=\tfrac34\), compute its return-series sum and classify it.
- For the simple symmetric random walk, why are all odd-time return probabilities zero?
- In the biased-walk example, which hitting probability from a neighboring state contributes to a return after the first step to the right?
- Can a communicating class be transient even if every state can reach every other state? Give the example discussed here.