Positive Recurrence and Finite Mean Return Times

Return Times and Positive Recurrence

For a countable-state Markov chain, it is possible to return to a state with probability one and still take an infinite expected amount of time to do so. Positive recurrence distinguishes states for which the mean return time is finite. This distinction matters for stationary probability distributions: in an irreducible chain, positive recurrence is the condition associated with the existence of such a distribution. It does not, however, ensure that the distribution of the chain at time \(n\) converges to stationarity.

Let \((X_n)_{n\ge 0}\) 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})\). Thus \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\), and each row of \(P\) sums to \(1\). We use the natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). Write \(\mathbb{P}_i\) and \(\mathbb{E}_i\) for probability and expectation when \(X_0=i\).

Positive recurrence implies recurrence: if \(\mathbb{E}_i[T_i^+]<\infty\), then \(T_i^+\) cannot be infinite with positive probability. The converse does not hold: an almost-sure return can have infinite expectation. For example, the simple symmetric random walk on the integers is recurrent but null recurrent; this is a standard result from recurrence classification. In a countable irreducible chain, the recurrence classification is shared by all states: either all are transient, all are null recurrent, or all are positive recurrent. We use this standard classification result here without reproving it.

Proof. If \(S=\{i\}\), then \(p_{ii}=1\), so \(T_i^+=1\) with probability one and its expectation is finite. Now suppose \(S\) has at least two states and fix \(i\in S\). By irreducibility, for each \(x\ne i\) there is a finite path from \(x\) to \(i\) whose transition probabilities have a positive product. Let \(n_x\) be the path length and \(a_x>0\) its probability. Since there are finitely many \(x\ne i\), choose \(N=\max_{x\ne i}n_x\) and \(\varepsilon=\min_{x\ne i}a_x>0\). Starting from any \(x\ne i\), the probability of hitting \(i\) within the next \(N\) steps is at least \(\varepsilon\).

Starting at \(i\), consider the chain after its first step. If it has returned by time \(1\), there is nothing further to bound. Otherwise its state is some \(x\ne i\). Given that it has not returned by a later block endpoint, the Markov property and the bound just obtained show that its conditional probability of avoiding \(i\) throughout the next \(N\) steps is at most \(1-\varepsilon\). Applying this bound at each block gives, for every integer \(k\ge0\),

For a positive integer-valued random variable, including one that may be infinite, its expectation equals \(\sum_{n\ge0}\mathbb{P}(T_i^+>n)\). Grouping this sum into blocks of length \(N\), the displayed geometric bound makes the sum finite: the initial terms contribute at most \(1+N\), and the subsequent block contributions are bounded by \(N\sum_{k\ge0}(1-\varepsilon)^k=N/\varepsilon\). Hence \(\mathbb{E}_i[T_i^+]<\infty\). The state \(i\) was arbitrary, proving the result. \(\square\)

This argument gives more than almost-sure return: in a finite irreducible chain, repeated blocks have a uniformly positive chance of containing a return. The resulting geometric tail bound forces a finite mean. On an infinite state space, there need not be a uniform positive lower bound of this kind.

Why Finite Mean Return Time Matters

For an irreducible chain on a countable state space, positive recurrence is precisely the condition for a stationary probability distribution to exist. A stationary distribution is a probability row vector \(\pi\) satisfying \(\pi P=\pi\). This existence characterization is a standard theorem; its proof through return cycles comes later in the course. The present point is the role of the finite mean: recurrent states return eventually, but if their mean return time is infinite, there is no stationary probability distribution for the irreducible chain. For a finite irreducible chain, the preceding theorem guarantees positive recurrence, and hence the condition needed for stationary existence is met.

Stationarity and convergence are separate properties. If the initial distribution is \(\pi\), then the marginal distribution remains \(\pi\): for every \(n\), \(\mu_n=\pi P^n=\pi\). This follows by induction, since \(\pi P=\pi\) implies \(\pi P^{n+1}=(\pi P^n)P=\pi P=\pi\). But this statement concerns a chain started in stationarity. It does not say that a chain started from an arbitrary distribution approaches \(\pi\).

Finite Mean Does Not Ensure Marginal Convergence

A chain can have finite mean return times and a stationary probability distribution while its marginals oscillate forever. Periodicity is one reason convergence can fail. The next example verifies this directly, so no general convergence theorem is needed.

Common mistake. It is incorrect to argue that a finite expected return time forces the marginals to converge to a stationary distribution. In the alternating-chain example, the return mean is exactly \(2\), yet the marginals alternate between \((1,0)\) and \((0,1)\). Finite mean return time is the positive-recurrence condition that supports stationary probability existence in an irreducible countable chain; convergence requires additional conditions, such as aperiodicity in the usual irreducible positive-recurrent setting.

When classifying a chain, keep three questions separate: does it return with probability one, is its mean return time finite, and do its marginals converge? Recurrence addresses the first, positive recurrence addresses the second, and convergence involves further features of the chain, including its period.