Truncated Return-Series Diagnostics

Return Probabilities as a Diagnostic

For a Markov chain, the probabilities of being back at a state after $n$ steps can be computed from powers of its transition matrix. Their partial sums offer a useful numerical diagnostic: they show how much return probability has accumulated over the time horizon examined. The key limitation is that recurrence is characterized by an infinite sum. A finite sum, however large, is finite and cannot by itself establish whether the full series converges or diverges.

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})$, with transition matrix $P=(p_{ij})$. Each row of $P$ sums to $1$. Write $\mathbb{P}_i$ for probabilities when $X_0=i$. For a fixed state $i$, define the $n$-step return probability $u_n=p_{ii}^{(n)}=\mathbb{P}_i(X_n=i)$, including $u_0=1$. The truncated positive-time return sum through horizon $N$ is $S_N=\sum_{n=1}^N u_n$. The first return time is $T_i^+=\inf\{n\ge1:X_n=i\}$.

Definition: State $i$ is recurrent if $\mathbb{P}_i(T_i^+<\infty)=1$, and transient if $\mathbb{P}_i(T_i^+<\infty)<1$. The return-series diagnostic concerns the infinite series $\sum_{n=0}^{\infty}p_{ii}^{(n)}$, or equivalently its positive-time part $\sum_{n=1}^{\infty}p_{ii}^{(n)}$, since the two differ only by $u_0=1$.

These two kinds of probabilities answer different questions. The value $u_n$ asks whether the chain is at $i$ at time $n$, allowing earlier visits. The probability $\mathbb{P}_i(T_i^+=n)$ asks whether its first return is exactly at time $n$. One trajectory can return more than once, so adding the $u_n$'s counts visits, not the probability of at least one return.

The Return-Series Criterion

Theorem (Return-series criterion): For a discrete-time Markov chain on a finite or countable state space and a state $i$, let $f_k=\mathbb{P}_i(T_i^+=k)$ for $k\ge1$, and let $f=\sum_{k=1}^{\infty}f_k=\mathbb{P}_i(T_i^+<\infty)$. Then $$ \sum_{n=0}^{\infty}p_{ii}^{(n)} = \begin{cases} \dfrac{1}{1-f},& f<1,\\[4pt] \infty,& f=1. \end{cases} $$ In particular, $i$ is recurrent if and only if $\sum_{n=0}^{\infty}p_{ii}^{(n)}$ diverges; it is transient if and only if this series converges.

Proof. Put $u_n=p_{ii}^{(n)}$, so $u_0=1$. For $n\ge1$, consider the first return to $i$. If the chain is at $i$ at time $n$, its first return must have occurred at some time $k\in\{1,\ldots,n\}$. Given a first return at time $k$, the Markov property implies that the probability of being at $i$ a further $n-k$ steps later is $u_{n-k}$. Summing over the disjoint possibilities for $k$ gives $$ u_n=\sum_{k=1}^n f_k u_{n-k}. $$ For $0\le r<1$, define $U(r)=\sum_{n=0}^{\infty}u_nr^n$ and $F(r)=\sum_{k=1}^{\infty}f_kr^k$. These series converge: $u_n\le1$, $f_k\ge0$, and $\sum_k f_k\le1$. Multiply the convolution equation by $r^n$, sum over $n\ge1$, and collect nonnegative terms. This yields $U(r)-1=F(r)U(r)$. Also $F(r)\le r\sum_k f_k\le r<1$, so division is valid and $U(r)=1/(1-F(r))$.

As $r$ increases to $1$, the nonnegative power series increase to their sums at $1$, possibly infinite. If $f<1$, then $F(r)$ increases to $f$, so $U(r)$ increases to $1/(1-f)$. If $f=1$, then $F(r)$ increases to $1$, and $1/(1-F(r))$ increases without bound. Thus the sum of the return probabilities is finite exactly when $f<1$, and is infinite exactly when $f=1$. By the definitions of transience and recurrence, this proves the stated equivalence and formula. $\square$

This criterion explains what a truncation can and cannot say. A computed $S_N$ is part of an increasing sequence of partial sums. It can reveal a pattern or support a conjecture, but it is not the infinite sum. To prove convergence, one needs a bound controlling the whole tail. To prove divergence, one needs a lower-bound argument or another structural reason forcing the partial sums to grow without bound.

Worked Diagnostics

Worked Example: A Self-Loop Followed by Absorption

Take $S=\{0,1\}$ and $$ P=\begin{bmatrix}\tfrac13&\tfrac23\\0&1\end{bmatrix}. $$ The first row sums to $\tfrac13+\tfrac23=1$, and the second sums to $0+1=1$. Starting at $0$, compute the return probabilities and distinguish the positive-time return sum from the probability of a first return.

To be at $0$ at time $n$, the chain must take the self-loop at every one of the $n$ steps: once it moves to $1$, it stays there. Therefore $u_n=(\tfrac13)^n$. In particular, $u_1=\tfrac13$, $u_2=\tfrac19$, and $u_3=\tfrac1{27}$. The first three positive-time terms sum to $$ S_3=\tfrac13+\tfrac19+\tfrac1{27}=\tfrac9{27}+\tfrac3{27}+\tfrac1{27}=\tfrac{13}{27}. $$ For general $N$, the geometric sum is $S_N=\sum_{n=1}^N(\tfrac13)^n=\tfrac12(1-3^{-N})$. For example, $S_2=\tfrac12(1-\tfrac19)=\tfrac49$, matching $\tfrac13+\tfrac19=\tfrac49$.

The chain returns at all only if its first step is the self-loop, so $\mathbb{P}_0(T_0^+<\infty)=\tfrac13$. Equivalently, $f_1=\tfrac13$ and $f_k=0$ for $k\ge2$. Thus state $0$ is transient. The return-series criterion gives $\sum_{n=0}^{\infty}u_n=1/(1-\tfrac13)=\tfrac32$; directly, $1+\sum_{n=1}^{\infty}(\tfrac13)^n=1+\tfrac12=\tfrac32$, as required.

Worked Example: Periodic Returns in a Two-State Chain

Let $S=\{0,1\}$, with state $0$ moving to $1$ with probability $1$ and state $1$ moving to $0$ with probability $1$: $$ P=\begin{bmatrix}0&1\\1&0\end{bmatrix}. $$ Both rows sum to $1$. Starting at $0$, the chain alternates deterministically: it is at $0$ at each even time and at $1$ at each odd time. Hence $u_n=1$ for positive even $n$, and $u_n=0$ for odd $n$.

Among the first five positive-time terms, only $u_2$ and $u_4$ equal $1$, so $S_5=0+1+0+1+0=2$. Among the first six, $u_6=1$ as well, giving $S_6=3$. In general, $S_N=\lfloor N/2\rfloor$, because exactly $\lfloor N/2\rfloor$ positive even integers are at most $N$. The first return occurs exactly at time $2$, so $f_2=1$ and the state is recurrent. The positive-time partial sums grow without bound, consistent with the criterion.

This example also warns against reading irregular or alternating values as evidence of convergence: here every odd-time return probability is zero, but the even-time terms force divergence.

Worked Example: Return Probabilities Are Not First-Return Probabilities

Consider $S=\{0,1,2\}$ and $$ P=\begin{bmatrix}0&1&0\\ \tfrac12&0&\tfrac12\\0&0&1\end{bmatrix}. $$ The rows sum to $0+1+0=1$, $\tfrac12+0+\tfrac12=1$, and $0+0+1=1$. From state $0$, the chain moves to $1$ with certainty. From $1$, it returns to $0$ with probability $\tfrac12$, or is absorbed at $2$ with probability $\tfrac12$.

A first return can occur only at time $2$, and its probability is $f_2=\tfrac12$. If that return occurs, the same two-step pattern begins again. Consequently $u_{2k}=(\tfrac12)^k$ for $k\ge1$, while $u_{2k+1}=0$. In detail, $u_1=0$, $u_2=\tfrac12$, $u_3=0$, and $u_4=\tfrac14$. Thus $S_4=0+\tfrac12+0+\tfrac14=\tfrac34$. In general, $$ S_N=\sum_{k=1}^{\lfloor N/2\rfloor}(\tfrac12)^k =1-2^{-\lfloor N/2\rfloor}. $$ For $N=4$, this gives $1-2^{-2}=\tfrac34$, agreeing with the direct calculation.

The full positive-time return sum is $1$, since $\sum_{k=1}^{\infty}(\tfrac12)^k=1$, but the probability of ever returning is only $\tfrac12$. The state is transient. Including $u_0=1$, the full return series sums to $2$, which also equals $1/(1-f)=1/(1-\tfrac12)=2$. This example makes the distinction exact: the sum of return probabilities counts expected visits after time zero, whereas a first-return probability measures the chance of at least one return.

Why No Finite Truncation Settles the Classification

Proposition: For every integer $N\ge1$, there are two chains whose return probabilities $u_1,\ldots,u_N$ at a specified state are identical, although that state is recurrent in one chain and transient in the other.

Proof. In the first chain, use states $\{0,1,\ldots,N\}$ and deterministic transitions $0\to1$, $1\to2$, continuing through $N-1\to N$, and $N\to0$. Every row has exactly one transition of probability $1$, so each row sums to $1$. Starting at $0$, the first return occurs at time $N+1$; hence $u_n=0$ for $1\le n\le N$, and the state is recurrent.

In the second chain, use the same states and transitions $0\to1$, $1\to2$, continuing through $N-1\to N$, but make $N$ absorbing. Again every row sums to $1$. Starting at $0$, the chain never returns to $0$, so $u_n=0$ for every $n\ge1$, and $0$ is transient. The two chains therefore have the same first $N$ return probabilities, all zero, but different classifications. Since $N$ was arbitrary, no finite prefix alone determines recurrence or transience. $\square$

The proposition is a logical limitation, not a claim that return calculations are useless. In an actual problem, structure may provide additional information: an exact formula for $u_n$, a comparison with a known series, or bounds on the uncomputed tail. Numerical values can guide which argument to seek, but the classification must ultimately concern the infinite series or the probability of ever returning.

Common Mistake and Practical Workflow

Common mistake. In the self-loop example, one might write $\sum_{n=1}^{\infty}(\tfrac13)^n=\tfrac12$ and call $\tfrac12$ the probability of a first return. This is wrong: $(\tfrac13)^n$ is $u_n=\mathbb{P}_0(X_n=0)$, the probability of being at $0$ at time $n$, not the probability that the first return occurs then. The correct first-return calculation is $f_1=\tfrac13$, $f_n=0$ for $n\ge2$, and therefore $\mathbb{P}_0(T_0^+<\infty)=\sum_{n\ge1}f_n=\tfrac13$. The value $\tfrac12$ is instead the sum of positive-time return probabilities.

When using truncated return sums, keep the following steps separate:

Compute $u_n=p_{ii}^{(n)}$, the $n$-step probability of being at $i$, and check the transition rows sum to $1$.
Form $S_N=\sum_{n=1}^N u_n$ using exact values where possible; state the horizon $N$.
Do not label $S_N$ a first-return probability. First-return probabilities are $f_n=\mathbb{P}_i(T_i^+=n)$.
Use the infinite-series criterion only when an argument controls all terms, not just the computed prefix.

The return-series diagnostic is useful because it connects matrix-power calculations to the long-run question of whether a state is revisited with probability one. Its practical role is to reveal patterns and check formulas. Its mathematical limitation is equally important: finite data describe only a finite horizon, while recurrence is an infinite-time property.

Check Your Understanding

For each question, distinguish carefully between being at a state at time $n$ and making a first return at time $n$.

For the two-state self-loop chain, calculate $S_4$ and $\mathbb{P}_0(T_0^+<\infty)$. Why are these not the same quantity?
In the alternating two-state chain, calculate $S_7$. Does the zero value of $u_7$ indicate transience?
For the three-state chain with $0\to1$ and $1\to0$ or $2$, what are $f_2$, $u_2$, and $u_4$?
State the return-series criterion in terms of $f=\mathbb{P}_i(T_i^+<\infty)$, and explain what it implies when $f<1$.
Why can two chains agree on $u_1,\ldots,u_N$ but have different recurrence classifications?