Recurrent and Transient States

Return Probability Classifies a State

A state can be visited again with positive probability without being visited again with certainty. Recurrence and transience distinguish these possibilities by asking whether a chain started at a state eventually returns to it. This classification describes long-run visits to an individual state; it is not a statement that the distribution of the chain is stationary, or that the chain must move between states in any particular pattern.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\), and its transition matrix is \(P=(p_{ij})\), with each row summing to \(1\). Write \(\mathbb{P}_i\) for probability when \(X_0=i\). The first return time to \(i\) is \(T_i^+=\inf\{n\ge1:X_n=i\}\), with \(\inf\varnothing=\infty\). Since return is an event that may fail, its probability is \(\mathbb{P}_i(T_i^+<\infty)\).

The definition concerns eventual return, not whether a return is possible in one step. A state with \(p_{ii}=0\) can be recurrent if the chain returns after two or more steps with probability \(1\). Conversely, even if \(p_{ii}>0\), the chain can have a positive chance of leaving for a region from which it cannot return, making the state transient.

Repeated Visits and the Return Probability

To interpret the classification, define successive return times by \(T_i^{(0)}=0\) under \(\mathbb{P}_i\), and, for \(r\ge0\), let \(T_i^{(r+1)}=\inf\{n>T_i^{(r)}:X_n=i\}\) if \(T_i^{(r)}<\infty\); otherwise set \(T_i^{(r+1)}=\infty\). Thus \(T_i^{(r)}<\infty\) means there have been at least \(r\) returns after time \(0\). Write \(f_i=\mathbb{P}_i(T_i^+<\infty)\).

Proof. The statement for \(r=1\) is the definition of \(f_i\). Suppose \(T_i^{(r)}<\infty\) has occurred. At that time the chain is at \(i\), and the Markov property says that its future, conditional on its history up to that time, has the law of a chain started at \(i\). Therefore its conditional probability of making one further return is \(f_i\). More explicitly, for each finite \(n\), the event \(\{T_i^{(r)}=n\}\) is determined by \(X_0,\ldots,X_n\), and \(X_n=i\) on that event. The Markov property at deterministic time \(n\) gives \(\mathbb{P}_i(T_i^{(r+1)}<\infty,\ T_i^{(r)}=n)=f_i\mathbb{P}_i(T_i^{(r)}=n)\). Summing over \(n\ge0\), whose events are disjoint, yields \(\mathbb{P}_i(T_i^{(r+1)}<\infty)=f_i\mathbb{P}_i(T_i^{(r)}<\infty)\). Starting from the case \(r=1\) and applying this equality repeatedly gives \(f_i^r\). \(\square\)

Proof. If \(i\) is recurrent, then \(f_i=1\), so the lemma gives \(\mathbb{P}_i(T_i^{(r)}<\infty)=1\) for every \(r\ge1\). The event that all these return times are finite is a countable intersection of probability-one events, and therefore has probability one. On that event the chain returns to \(i\) infinitely often.

If \(i\) is transient, then \(0\le f_i<1\), so the lemma gives \(\mathbb{P}_i(T_i^{(r)}<\infty)=f_i^r\to0\) as \(r\to\infty\). The event of infinitely many returns is contained in \(\{T_i^{(r)}<\infty\}\) for every \(r\), so its probability is at most \(f_i^r\) for every \(r\). Taking \(r\to\infty\) shows that this probability is \(0\). Starting at \(i\), the chain has one visit at time \(0\); hence finitely many returns means finitely many total visits. \(\square\)

The theorem is an almost-sure statement: it describes what happens with probability one when the chain starts at \(i\). For a transient state, a return can still occur; transience says that it is not certain, and that infinitely many returns have probability zero. It does not say that every path avoids a second visit.

Worked Classifications

Common Mistake and Practical Use

Common mistake: “If \(p_{ii}>0\), then \(i\) is recurrent because the chain can return in one step.” This confuses a positive probability of return with probability-one return. In the two-state example above, an incorrect calculation might set \(\mathbb{P}_0(T_0^+<\infty)=1\) merely because \(p_{00}=\tfrac13>0\). The correction is to include every possible path after the first step: the self-loop gives a return with probability \(\tfrac13\), while the move to the absorbing state gives no return, contributing \(0\). The actual return probability is \(\tfrac13\), so state \(0\) is transient.

For a concrete chain, the basic classification procedure is:

1. Specify the starting state \(i\) and use the first return time, which begins at \(n=1\), not the hitting time that allows \(n=0\).
2. Identify all possible ways the chain can return to \(i\), including paths that return after more than one step.
3. Compute the probability of eventual return. The state is recurrent exactly when that probability equals \(1\); otherwise it is transient.
4. Interpret the result through repeated visits: recurrence gives infinitely many visits almost surely from \(i\), whereas transience gives only finitely many almost surely.

This classification is useful because it separates the possibility of return from certainty of return and makes the repeated-visit behavior precise. It does not, by itself, calculate the expected number of visits or determine recurrence from a transition-matrix series; those require additional analysis. In particular, do not infer a state’s classification solely from a self-loop, a single possible path, or a finite number of observed visits.