Recurrence Does Not Require a Finite Mean Return Time

Certain Return and Mean Return Time Are Different

For a finite irreducible chain, return to a state occurs with probability one and has finite expected time. In countably infinite state spaces, the first conclusion need not imply the second. A chain can return eventually with certainty while making excursions whose durations are long enough, on average, to give an infinite mean. This distinction matters because “the chain comes back” is a probability statement; “the chain comes back in finite expected time” is a stronger statement about the distribution of how long the return takes.

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a countable state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Its transition matrix is $P=(p_{ij})$, with rows summing to $1$. When the chain starts at $i$, write $\mathbb{P}_i$ and $\mathbb{E}_i$. The filtration is $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. For a state $i$, the first return time is $T_i^+=\inf\{n\ge1:X_n=i\}$, with $\inf\varnothing=\infty$.

Definition: A state $i$ is recurrent if $\mathbb{P}_i(T_i^+<\infty)=1$. It is positive recurrent if it is recurrent and $\mathbb{E}_i[T_i^+]<\infty$. It is null recurrent if it is recurrent and $\mathbb{E}_i[T_i^+]=\infty$. A transient state has $\mathbb{P}_i(T_i^+<\infty)<1$.

Expectations here are extended expectations, so they may equal infinity. The return-time distribution records both the probabilities of finite return times and any probability of never returning. Keeping that possible mass at infinity in view is essential when computing an expectation.

Result (tail-sum identity): For any random time $T$ taking values in $\{0,1,2,\ldots\}\cup\{\infty\}$, $$ \mathbb{E}[T]=\sum_{m=0}^{\infty}\mathbb{P}(T>m), $$ where either side may be infinite. If $\mathbb{P}(T=\infty)>0$, then $\mathbb{E}[T]=\infty$. If $\mathbb{P}(T<\infty)=1$, then also $\mathbb{E}[T]=\sum_{k=0}^{\infty}k\,\mathbb{P}(T=k)$.

Proof. For each outcome with $T<\infty$, the number of integers $m\ge0$ satisfying $T>m$ is exactly $T$. For an outcome with $T=\infty$, every indicator $\mathbf{1}_{\{T>m\}}$ equals $1$, so their sum is infinity, also equal to $T$. Thus, pointwise, $T=\sum_{m\ge0}\mathbf{1}_{\{T>m\}}$. Taking expectations of the increasing finite partial sums and passing to their limit by monotone convergence gives the tail-sum identity. If $T=\infty$ has positive probability, the tail probabilities are at least $\mathbb{P}(T=\infty)>0$ for every $m$, so their sum is infinite. In the almost-surely finite case, partitioning according to the possible values $k$ gives $T=\sum_{k\ge0}k\mathbf{1}_{\{T=k\}}$ pointwise, and taking expectations of the nonnegative terms gives the stated probability-mass formula. $\square$

A Chain That Returns with Probability One but Has Infinite Mean

We now construct a chain whose return time can be read directly from its transitions. The state space is $S=\{0,1,2,\ldots\}$. From state $0$, the chain chooses a positive integer $n$ with probability $1/[n(n+1)]$, and from any state $n\ge1$, it moves deterministically to $n-1$. Thus, after choosing $n$, the chain descends one state at each step until it reaches $0$.

Worked Example: Certain Return with Infinite Mean

Start the chain at $0$. First check the transition probabilities. For the row at $0$, the probability of moving to $0$ is $p_{00}=0$, and for every $n\ge1$, $p_{0n}=1/[n(n+1)]$. Since $$ \frac{1}{n(n+1)}=\frac1n-\frac{1}{n+1}, $$ the sum of the row is $\sum_{n=1}^{\infty}(1/n-1/(n+1))=1$. For each $n\ge1$, $p_{n,n-1}=1$ and all other entries in that row are $0$, so each such row also sums to $1$.

If the first move is to $n$, the subsequent states are $n-1,n-2,\ldots,1,0$. The first return to $0$ therefore occurs after $n+1$ steps: the initial move from $0$ to $n$, followed by $n$ downward moves. Consequently, for each $k\ge2$, $$ \mathbb{P}_0(T_0^+=k)=\frac{1}{(k-1)k}. $$ The return probability is $$ \mathbb{P}_0(T_0^+<\infty)=\sum_{k=2}^{\infty}\frac{1}{(k-1)k} =\sum_{n=1}^{\infty}\left(\frac1n-\frac{1}{n+1}\right)=1. $$ So state $0$ is recurrent.

Nevertheless, its mean return time is infinite. The return time is finite with probability one, so its expectation can be calculated from its probability mass function: $$ \mathbb{E}_0[T_0^+] =\sum_{k=2}^{\infty}k\frac{1}{(k-1)k} =\sum_{r=1}^{\infty}\frac1r =\infty. $$ For completeness, the harmonic series diverges: in each block $2^j\le r<2^{j+1}$, there are $2^j$ terms, each at least $1/2^{j+1}$. Each block therefore contributes at least $1/2$, and infinitely many such blocks make the partial sums unbounded. This verifies that $0$ is null recurrent.

Check: The return probabilities sum to $1$, but the terms in the mean sum reduce to $1/r$. These are different calculations: summing probabilities establishes certain return, while weighting each return time by its probability gives the mean.

The example proves the central distinction directly. Every excursion ends at $0$, but the first move can select an arbitrarily large state. The probability of selecting a large state is small; nevertheless, the resulting duration contributes enough to make the expected return time infinite.

Proposition: For the chain just defined, state $0$ is recurrent but not positive recurrent.

Proof. The transition row at $0$ assigns total probability $1$ to positive integers, as shown by the telescoping sum. Conditional on choosing any finite $n\ge1$, the deterministic downward path reaches $0$ after $n$ further steps. Since the chain chooses a finite $n$ with probability $1$, it returns to $0$ with probability $1$, which is recurrence. The first return time has probability $1/[n(n+1)]$ of being $n+1$, so its mean is $\sum_{n\ge1}(n+1)/[n(n+1)]=\sum_{n\ge1}1/n=\infty$. Thus the state is not positive recurrent and, by the definition, is null recurrent. $\square$

Truncation Makes the Infinite Mean Visible

Although the full mean is infinite, every bounded truncation has a finite expectation. These truncated means give a useful way to check the calculation and see how the divergence accumulates. The tail-sum identity gives, for a positive integer $M$, $$ \mathbb{E}_0[\min(T_0^+,M)]=\sum_{m=0}^{M-1}\mathbb{P}_0(T_0^+>m). $$ The strict inequality in the tail event is important: for an integer-valued time, the event in the $m$th term is $T_0^+>m$, not $T_0^+\ge m$.

Worked Example: A Truncated Mean

Use the same chain, whose transition row at $0$ sums to $1$ by the telescoping calculation above and whose other rows each have a single entry equal to $1$. For $m\ge1$, the event $T_0^+>m$ means that the initial choice satisfies $n+1>m$, or equivalently $n\ge m$. Therefore $$ \mathbb{P}_0(T_0^+>m)=\sum_{n=m}^{\infty}\frac{1}{n(n+1)}=\frac1m, $$ whereas $\mathbb{P}_0(T_0^+>0)=1$. Taking $M=5$ gives $$ \mathbb{E}_0[\min(T_0^+,5)] =1+1+\frac12+\frac13+\frac14 =\frac{12+12+6+4+3}{12} =\frac{37}{12}. $$

Check by summing the truncated distribution. The finite return probabilities are $\mathbb{P}_0(T_0^+=2)=1/2$, $\mathbb{P}_0(T_0^+=3)=1/6$, $\mathbb{P}_0(T_0^+=4)=1/12$, and $\mathbb{P}_0(T_0^+=5)=1/20$. The probability of $T_0^+\ge6$ is the probability of choosing $n\ge5$, namely $\sum_{n=5}^{\infty}1/[n(n+1)]=1/5$. Hence $$ \mathbb{E}_0[\min(T_0^+,5)] =2\cdot\frac12+3\cdot\frac16+4\cdot\frac1{12} +5\cdot\frac1{20}+5\cdot\frac15 =1+\frac12+\frac13+\frac14+1 =\frac{37}{12}. $$ Both methods give the same value.

As the truncation level grows, the tail-sum expression contains longer partial sums of the harmonic series. In particular, $\mathbb{E}_0[\min(T_0^+,M)]$ increases without bound as $M$ increases. This is consistent with the infinite mean and shows why a collection of finite truncated expectations does not imply a finite expectation without a uniform bound on them.

Recurrence Does Not Force an Infinite Mean Either

The example with a harmonic tail establishes that recurrence does not guarantee a finite mean. The converse comparison is also useful: a recurrent chain can have a finite mean return time. Changing only the distribution of the initial upward move will show that recurrence alone determines neither whether the mean is finite nor its value.

Worked Example: A Recurrent Chain with Finite Mean

Keep the same state space and deterministic downward transitions, but now let the transition probabilities from $0$ be $p_{0n}=2^{-n}$ for $n\ge1$, with $p_{00}=0$. This row sums to $1$, because $\sum_{n=1}^{\infty}2^{-n}=1$. For $n\ge1$, the row still has $p_{n,n-1}=1$ and all other entries $0$, so every row is stochastic.

Again, choosing any finite $n\ge1$ leads back to $0$, so the return probability is $\sum_{n\ge1}2^{-n}=1$. The first return time is $n+1$ when the first move selects $n$, and thus $$ \mathbb{E}_0[T_0^+] =\sum_{n=1}^{\infty}(n+1)2^{-n} =\sum_{n=1}^{\infty}n2^{-n}+\sum_{n=1}^{\infty}2^{-n}. $$

To evaluate the first sum, use the tail-sum formula for the positive-integer-valued choice $N$, where $\mathbb{P}(N=n)=2^{-n}$. For $m\ge0$, $\mathbb{P}(N>m)=\sum_{n=m+1}^{\infty}2^{-n}=2^{-m}$. Therefore $\mathbb{E}[N]=\sum_{m=0}^{\infty}2^{-m}=2$, and $\mathbb{E}_0[T_0^+]=\mathbb{E}[N]+1=3$.

Check: The first-step choice has mean $2$, so the return takes that initial choice plus one step, giving $3$. Equivalently, $\sum_{n\ge1}(n+1)2^{-n}=2+1=3$. Thus this state is positive recurrent, unlike state $0$ in the harmonic-tail example.

Common Mistakes and Practical Interpretation

Common mistake: omitting mass at infinity. If a return time has positive probability of being infinite, the expression $\sum_{k\ge1}k\,\mathbb{P}(T_i^+=k)$ does not by itself give the extended expectation; it omits the outcomes on which the time is infinite. For example, if $\mathbb{P}(T_i^+=\infty)>0$, that sum could be finite even though $\mathbb{E}_i[T_i^+]=\infty$. The correction is to account for the mass at infinity: any positive probability of $T_i^+=\infty$ makes the extended expectation infinite. If return is almost sure, the probability-mass formula applies, and the tail-sum formula applies whether or not return is almost sure.

Common mistake: losing a term in a truncated mean. In the truncated example, $1+1+\tfrac12+\tfrac13+\tfrac14$ has denominator-$12$ numerator $12+12+6+4+3=37$, not $49$. Computing the tail probabilities individually and then checking by summing the truncated distribution helps detect such arithmetic errors.

The distinction is useful whenever conclusions depend on the average time between returns. A recurrence probability of $1$ says that return eventually happens almost surely; it does not provide a finite time scale for that return. In the harmonic-tail chain, every selected excursion ends, but increasingly long excursions make the average return time diverge. In the geometric-tail chain, long excursions are sufficiently unlikely to keep that average finite. Thus, when a problem asks about a return, first identify whether it asks for its probability or its expected duration, and calculate the relevant quantity rather than inferring one from the other.

Check Your Understanding

Use the definitions and calculations above to answer the following questions.

For the chain with $p_{0n}=1/[n(n+1)]$, what value of $n$ gives a first return at time $7$, and what is the probability of that return time?
For that same chain, calculate $\mathbb{P}_0(T_0^+>3)$ using the strict tail event and the telescoping sum.
Explain why $\mathbb{P}_0(T_0^+<\infty)=1$ does not imply $\mathbb{E}_0[T_0^+]<\infty$ in the harmonic-tail example.
For the chain with $p_{0n}=2^{-n}$, verify the probability of choosing $n\ge3$ and state the resulting event in terms of the first return time.
When $\mathbb{P}_i(T_i^+=\infty)>0$, why is the sum over finite return times alone insufficient to compute the extended mean?