The Return-Series Criterion for Recurrence

Return Probabilities and Recurrence

A state can be visited repeatedly without visits occurring at every time step. To decide whether it is recurrent, we therefore need to distinguish the probability of being back at that state at a specified time from the probability that the first return occurs at that time. The return-series criterion makes this distinction precise: recurrence is equivalent to an infinite sum of n-step return probabilities, while transience is equivalent to a finite sum.

Let \((X_n)_{n\ge0}\) be a time-homogeneous Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Use the natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). For \(i,j\in S\), write \(p_{ij}^{(n)}=\mathbb{P}_i(X_n=j)\), where \(\mathbb{P}_i\) means the chain starts at \(i\); in particular, \(p_{ij}^{(0)}=\mathbf{1}_{\{i=j\}}\). Fix a state \(i\), and define its first return time by \(T_i^+=\inf\{n\ge1:X_n=i\}\), with \(\inf\varnothing=\infty\).

Definition: The state \(i\) is recurrent if \(\mathbb{P}_i(T_i^+<\infty)=1\), and transient if \(\mathbb{P}_i(T_i^+<\infty)<1\). Its n-step return probability is \(p_{ii}^{(n)}=\mathbb{P}_i(X_n=i)\). The return series is \(\sum_{n=0}^{\infty}p_{ii}^{(n)}\). Starting at \(n=1\) instead gives the same convergence or divergence, since the \(n=0\) term is just \(1\).

For \(k\ge1\), let \(f_k=\mathbb{P}_i(T_i^+=k)\), and let \(r=\mathbb{P}_i(T_i^+<\infty)=\sum_{k=1}^{\infty}f_k\). The return series records the probability of being at \(i\) at each specified time, whether or not the chain has visited \(i\) at an earlier positive time. The first-return probabilities \(f_k\), by contrast, concern only the first such visit.

The Renewal Identity

We first derive the identity that links the two sequences. If \(n\ge1\) and \(X_n=i\), then there must have been a first return by time \(n\). Partition the event \(\{X_n=i\}\) according to the first-return time \(k\). On \(\{T_i^+=k\}\), the chain is at \(i\) at time \(k\). The Markov property at the deterministic time \(k\) gives probability \(p_{ii}^{(n-k)}\) of being at \(i\) at time \(n\). Thus, for \(n\ge1\),

p_{ii}^{(n)}=\sum_{k=1}^{n} f_k p_{ii}^{(n-k)}.

This identity includes the case \(k=n\), where the factor \(p_{ii}^{(0)}=1\) accounts for a return occurring exactly at time \(n\). Introduce the power series \(U(z)=\sum_{n=0}^{\infty}p_{ii}^{(n)}z^n\) and \(F(z)=\sum_{k=1}^{\infty}f_kz^k\), for \(0\le z<1\). Since \(p_{ii}^{(n)}\le1\), \(U(z)\le\sum_{n=0}^{\infty}z^n=1/(1-z)\), so \(U(z)\) is finite. Also \(F(z)\le1\). Multiplying the renewal identity by \(z^n\) and summing over \(n\ge1\) gives

U(z)-1 =\sum_{n=1}^{\infty}\sum_{k=1}^{n} f_k p_{ii}^{(n-k)}z^n =F(z)U(z).

The rearrangement is valid because every summand is nonnegative: set \(m=n-k\), and the double sum becomes the product of the two nonnegative series. In particular, \(1-F(z)>0\), since \(F(z)\le z\sum_{k\ge1}f_k\le z<1\). Therefore \(U(z)=1/(1-F(z))\).

Theorem (Return-series criterion): For a state \(i\) of a discrete-time Markov chain, \(i\) is recurrent if and only if \(\sum_{n=0}^{\infty}p_{ii}^{(n)}=\infty\). It is transient if and only if \(\sum_{n=0}^{\infty}p_{ii}^{(n)}<\infty\). More precisely, if \(r=\mathbb{P}_i(T_i^+<\infty)<1\), then \(\sum_{n=0}^{\infty}p_{ii}^{(n)}=1/(1-r)\).

Proof. The partial sums defining \(U(z)\) and \(F(z)\) increase as \(z\) increases to \(1\). By monotone convergence for nonnegative series, \(\lim_{z\uparrow1}U(z)=\sum_{n\ge0}p_{ii}^{(n)}\), allowing the value \(+\infty\), and \(\lim_{z\uparrow1}F(z)=\sum_{k\ge1}f_k=r\). If \(r<1\), the identity \(U(z)=1/(1-F(z))\) gives \(\lim_{z\uparrow1}U(z)=1/(1-r)<\infty\). If \(r=1\), then \(F(z)\) increases to \(1\), so \(1/(1-F(z))\) increases without bound; hence \(\sum_{n\ge0}p_{ii}^{(n)}=\infty\). By definition, \(r=1\) means recurrence and \(r<1\) means transience. These are the only cases because \(0\le r\le1\). This proves both equivalences and the stated formula. \(\square\)

The theorem concerns recurrence, not the mean time to return. In particular, its conclusion is about whether the return-probability series is finite. It does not require the chain to be aperiodic: the series can diverge even when the chain can return only at selected times.

Worked Example: A Periodic Recurrent State

Consider the chain on \(S=\{a,b\}\) with transition matrix \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\). Each row sums to \(1\). Starting at \(a\), the chain alternates deterministically: it is at \(a\) at even times and at \(b\) at odd times. Thus \(p_{aa}^{(0)}=1\), \(p_{aa}^{(2k)}=1\) for every integer \(k\ge1\), and \(p_{aa}^{(2k+1)}=0\) for every integer \(k\ge0\).

It follows that \(\sum_{n=0}^{\infty}p_{aa}^{(n)}=1+1+1+\cdots=\infty\), so the criterion says \(a\) is recurrent. Directly, \(T_a^+=2\) with probability \(1\), which confirms recurrence. The chain is periodic, but that does not affect the divergence test: the zero terms at odd times do not prevent infinitely many positive terms at even times.

Worked Example: A Geometric Return Series

Take \(S=\{a,b\}\) and \(P=\begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix}\). The first row sums to \(\tfrac12+\tfrac12=1\), and the second row sums to \(0+1=1\). From \(a\), the chain either stays at \(a\) or moves to the absorbing state \(b\). To be at \(a\) at time \(n\), it must stay at \(a\) on all \(n\) steps, so \(p_{aa}^{(n)}=(\tfrac12)^n\) for \(n\ge0\).

The return series is geometric:

\sum_{n=0}^{\infty}p_{aa}^{(n)} =\sum_{n=0}^{\infty}\left(\tfrac12\right)^n =\frac{1}{1-\tfrac12}=2.

For comparison, the first return occurs at time \(1\) exactly when the first step stays at \(a\). Therefore \(f_1=\tfrac12\), \(f_k=0\) for \(k\ge2\), and \(r=\tfrac12\). The theorem's formula gives \(1/(1-r)=1/(1-\tfrac12)=2\), matching the series calculation. Since \(r<1\), \(a\) is transient.

Check: The one-step return probability is \(p_{aa}^{(1)}=\tfrac12\), and the probability of staying at \(a\) for two consecutive steps is \(p_{aa}^{(2)}=(\tfrac12)(\tfrac12)=\tfrac14\), agreeing with the formula \(p_{aa}^{(n)}=(\tfrac12)^n\).

Worked Example: Distinguishing Returns from First Returns

Let \(S=\{a,b,c\}\), with transition matrix \(P=\begin{bmatrix}0&1&0\\\tfrac12&0&\tfrac12\\0&0&1\end{bmatrix}\). The row sums are \(0+1+0=1\), \(\tfrac12+0+\tfrac12=1\), and \(0+0+1=1\). Starting from \(a\), the chain first moves to \(b\). At each visit to \(b\), it moves to \(a\) with probability \(\tfrac12\), or to the absorbing state \(c\) with probability \(\tfrac12\).

To be at \(a\) at time \(2k\), the chain must complete \(k\) successive two-step cycles \(a\to b\to a\). Each cycle has probability \(1\cdot\tfrac12=\tfrac12\), so \(p_{aa}^{(2k)}=(\tfrac12)^k\) for \(k\ge1\). At odd times it cannot be at \(a\), so \(p_{aa}^{(2k+1)}=0\) for \(k\ge0\). Consequently,

\sum_{n=0}^{\infty}p_{aa}^{(n)} =1+\sum_{k=1}^{\infty}\left(\tfrac12\right)^k =1+1=2.

But the first return is at time \(2\) only if the first move from \(b\) is to \(a\). Thus \(\mathbb{P}_a(T_a^+=2)=\tfrac12\), and \(\mathbb{P}_a(T_a^+=2k)=0\) for every \(k\ge2\): a return at time \(2\) has already occurred on those paths that would otherwise be counted. The chain moves to \(c\) with probability \(\tfrac12\), so \(\mathbb{P}_a(T_a^+=\infty)=\tfrac12\). Hence \(r=\tfrac12\), and the criterion classifies \(a\) as transient. The formula \(1/(1-r)=1/(1-\tfrac12)=2\) verifies the return-series sum.

A Common Miscalculation

A tempting but incorrect calculation in the last example is to call \((\tfrac12)^k\) the probability of a first return at time \(2k\), and then sum these quantities to obtain \(1\). The probabilities \((\tfrac12)^k\) are instead \(p_{aa}^{(2k)}\), the probabilities of being at \(a\) at time \(2k\). For \(k\ge2\), paths counted by \(p_{aa}^{(2k)}\) have already returned at time \(2\). The correct first-return probabilities are \(\mathbb{P}_a(T_a^+=2)=\tfrac12\) and \(\mathbb{P}_a(T_a^+=2k)=0\) for \(k\ge2\); their sum is \(\tfrac12\), not \(1\). The return series and the first-return probabilities are related, but they are different sequences and must not be interchanged.

The distinction also explains why the series criterion is useful. It converts a pathwise question—whether a return eventually occurs with probability one—into a test based on the probabilities \(p_{ii}^{(n)}\) at fixed times. The theorem handles periodic returns naturally, and its generating-function proof shows exactly how the first-return probability controls the total expected number of visits, including the initial visit.

Check Your Understanding

For each question, keep the distinction between an n-step return probability and a first-return probability explicit.

If \(p_{ii}^{(n)}=1\) for every even \(n\ge0\) and \(p_{ii}^{(n)}=0\) for every odd \(n\), what does the return-series criterion imply about \(i\)?
Suppose \(\mathbb{P}_i(T_i^+<\infty)=\tfrac13\). What is \(\sum_{n=0}^{\infty}p_{ii}^{(n)}\), and is \(i\) recurrent or transient?
In the three-state example, why is \(p_{aa}^{(4)}=\tfrac14\) not equal to \(\mathbb{P}_a(T_a^+=4)\)?
Why does including the \(n=0\) term change the value of a finite return series but not whether it converges?
In the renewal identity, explain what the factor \(p_{ii}^{(n-k)}\) represents when the first return occurs at time \(k\).

The Return-Series Criterion for Recurrence

What You'll Learn