Every Finite Irreducible Chain Is Recurrent

From Irreducibility to Return

Irreducibility says that every state can be reached from every other state with positive probability. By itself, this describes paths one pair of states at a time. For a finite chain, there are only finitely many starting states, so paths back to a chosen state can be combined into a single, uniform return bound. Repeatedly applying the Markov property to that bound shows that the chain cannot avoid the chosen state forever.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite 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 the Markov property says that the conditional law of the future given \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\) depends on the past only through \(X_n\). Each row of \(P\) sums to \(1\). A chain is irreducible if for every \(x,y\in S\), there is an integer \(r\ge0\) such that \((P^r)_{xy}>0\). The first return time to \(i\), when \(X_0=i\), is \(T_i^+=\inf\{n\ge1:X_n=i\}\), with \(\inf\varnothing=\infty\). State \(i\) is recurrent if \(\mathbb{P}_i(T_i^+<\infty)=1\).

Proof by Uniform Blocks

Proof. Fix a state \(i\). For each \(x\ne i\), irreducibility provides a finite path from \(x\) to \(i\) whose transition probabilities are all positive. Its length is at least \(1\), and the probability of following that particular path is the product of its transition probabilities, which is positive. We also need a positive-length path when the starting state is \(i\), since a path of length zero does not count as a return. If \(S=\{i\}\), row-stochasticity forces \(p_{ii}=1\), so the one-step path from \(i\) to itself has probability \(1\). If \(S\) has another state \(y\), irreducibility supplies a positive-probability path from \(i\) to \(y\) and a positive-probability path from \(y\) to \(i\). Concatenating them gives a positive-length path from \(i\) back to \(i\).

For each \(x\in S\), choose one such positive-length path from \(x\) to \(i\). Write its length as \(m_x\) and its probability as \(a_x>0\). Because \(S\) is finite, \(M=\max_{x\in S}m_x\) is a finite positive integer, and \(\varepsilon=\min_{x\in S}a_x\) is positive. Following the chosen path from \(x\) guarantees a visit to \(i\) within \(M\) steps. Thus, from every starting state \(x\), the probability of a visit to \(i\) at one of times \(1,\ldots,M\) is at least \(\varepsilon\). Also \(0<\varepsilon\le1\).

Now start the chain at \(i\), and let \(H_k=\{T_i^+>kM\}\). At a block boundary \(kM\), conditional on \(\mathcal{F}_{kM}\), the probability of avoiding \(i\) throughout the next \(M\) steps is at most \(1-\varepsilon\), regardless of the current state \(X_{kM}\). Applying the Markov property and taking expectations gives \(\mathbb{P}_i(H_{k+1})\le(1-\varepsilon)\mathbb{P}_i(H_k)\). Since \(\mathbb{P}_i(H_0)=1\), induction yields \(\mathbb{P}_i(T_i^+>kM)\le(1-\varepsilon)^k\).

As \(k\) increases, the events \(\{T_i^+>kM\}\) decrease to \(\{T_i^+=\infty\}\). Their probabilities are bounded by \((1-\varepsilon)^k\), which tends to zero. Therefore \(\mathbb{P}_i(T_i^+=\infty)=0\), or equivalently \(\mathbb{P}_i(T_i^+<\infty)=1\). The choice of \(i\) was arbitrary, so every state is recurrent. \(\square\)

The same bound also controls the mean return time, though it does not give the exact return-time distribution. For a positive integer-valued random variable \(T\), allowing \(T=\infty\), the identity \(T=\sum_{n\ge0}\mathbf{1}_{\{T>n\}}\) gives \(\mathbb{E}[T]=\sum_{n\ge0}\mathbb{P}(T>n)\), with both sides interpreted as extended values. For each \(k\ge0\) and each \(n\) with \(kM\le n<(k+1)M\), monotonicity of the tail gives \(\mathbb{P}_i(T_i^+>n)\le\mathbb{P}_i(T_i^+>kM)\le(1-\varepsilon)^k\). There are \(M\) such indices in each block, so \(\mathbb{E}_i[T_i^+]\le M\sum_{k\ge0}(1-\varepsilon)^k=M/\varepsilon<\infty\). This is an upper bound from the selected paths, not an exact computation of the mean.

Worked Applications of the Bound

Why Finiteness Matters

The finite-state assumption is used at one precise point: taking the minimum of the positive probabilities of the selected paths. A minimum of finitely many positive numbers is positive. For infinitely many states, positive path probabilities can approach zero, so this argument need not produce any uniform \(\varepsilon>0\).

For example, on the integer states \(\mathbb{Z}\), let a chain move one step left or right, each with probability \(\tfrac12\). It is irreducible. For target \(0\), the particular path from \(n>0\) that moves left at every step has length \(n\) and probability \((\tfrac12)^n\), which approaches zero as \(n\) increases. Thus the path probabilities selected state by state do not have a positive lower bound over all starting states. This observation only shows why the finite-path proof cannot be applied with a uniform bound; it does not by itself classify the chain.

Common mistake. A path of length zero from the target state \(i\) to itself has probability \(1\), but it says nothing about a return, which requires at least one step. Using that path to claim a one-step return chance of \(1\) is incorrect. The correction is to choose a positive-length return path from \(i\): in a singleton irreducible chain, row-stochasticity gives \(p_{ii}=1\); with more than one state, concatenate a path from \(i\) to another state with a path back to \(i\). Another tempting error is to infer the exact return distribution from the block bound. The bound controls the tail and proves recurrence; an exact distribution requires more information about the transitions.