Classification of States: Communication and Recurrence

Communicating classes and recurrence classification underlie almost every applied use of Markov chains. In queueing theory and operations research, recurrence of a queue-length chain determines system stability: a transient queue-length process signals an overloaded system that drifts to infinite backlog, while recurrence signals a system that empties out infinitely often. In Markov Chain Monte Carlo (MCMC) methods used throughout Bayesian statistics and computational physics, one must first check irreducibility of the proposed chain — otherwise the sampler may be confined to a proper communicating class and never explore the full target distribution. In genetics, the Wright–Fisher and Moran models of allele frequency use absorbing (closed, recurrent, finite) states to model fixation and extinction of alleles. In PageRank and web-graph algorithms, the "random surfer" Markov chain's communicating-class structure (and the damping factor's role in forcing irreducibility) is precisely what guarantees a well-defined stationary ranking. In branching processes and population dynamics, extinction corresponds to absorption into a recurrent singleton state (population = 0), while transient classes describe unsustainable growth trajectories. In cryptographic random number generators built on Markov structures, verifying irreducibility and recurrence ensures the generator's state space is fully and repeatedly explored rather than trapped in a degenerate cycle. This classification is also the precise launching point for the next layer of theory: Periodicity and Positive Recurrence refines recurrent classes further by cycle length and expected return time, which in turn determines the existence and uniqueness of a Stationary Distribution.

Ask the tutor: Can you show me how to determine, step by step, the communicating classes and recurrence type of a chain from its full transition matrix?

Picture the state space as a directed graph: draw an arrow $i \to j$ whenever $p_{ij} > 0$. Accessibility $i \to j$ means there is a directed path (of any length, including a trivial length-0 path when $i=j$) from $i$ to $j$ in this graph. Communication $i \leftrightarrow j$ means $i$ and $j$ lie on a common directed cycle (or are equal). Communicating classes are exactly the strongly connected components of this graph. Some classes have arrows leading out but none leading back in — these are transient, doomed to be abandoned eventually. Other classes are "closed": once entered, the chain can never leave. A closed class is a candidate for recurrence, though closedness alone is not sufficient in infinite state spaces (an infinite closed class can still be transient, as with an asymmetric random walk drifting to $+\infty$). The return-time picture: from state $i$, watch the sequence of visits to $i$ over time. Each time the chain leaves $i$, it returns with the same probability $f_i$ (this is the Markov property doing the work), independently of the past. So the number of returns to $i$, given it starts there, is a geometric-type counting process: if $f_i = 1$ the chain returns forever (infinitely many visits, recurrent); if $f_i < 1$ the number of visits to $i$ is a genuine (finite, geometric) random variable, and eventually the chain leaves $i$ forever (transient). This dichotomy is exactly like asking whether a biased coin, flipped for "will I return," eventually shows tails permanently or is destined to show heads at every attempt.

We now connect the graph-theoretic notion of communication to the probabilistic notion of recurrence. The key tool is a clean series criterion.

Example 1: A three-state chain with one transient and one recurrent class (asymmetric transitions). Let $S = \{1,2,3\}$ with transition matrix

Read off accessibility: $1 \to 1$ ($p_{11}=0.5>0$), $1\to 2$ ($p_{12}=0.5>0$), $2\to1$ ($p_{21}=0.2>0$), $2\to 2$, $2\to 3$ ($p_{23}=0.5>0$), $3 \to 3$ ($p_{33}=1$), and $3 \to 1$? We need $p_{31}^{(n)}$ for some $n$: since $p_{31}=0$ and $p_{32}=0$ and $p_{33}=1$, by induction $p_{31}^{(n)} = 0$ for all $n\ge0$ (once at 3, always at 3). So $3 \not\to 1$ and $3 \not\to 2$. Check $1 \leftrightarrow 2$: we have $1\to2$ directly and $2\to1$ directly, so yes, $1\leftrightarrow2$. Does $1 \to 3$? Yes, via $1\to2\to3$ ($p_{13}^{(2)} \ge p_{12}p_{23} = 0.5 \times 0.5 = 0.25>0$). But $3 \to 1$ fails as shown. So $1 \not\leftrightarrow 3$ and $2\not\leftrightarrow3$. Communicating classes: $\{1,2\}$ and $\{3\}$. Class $\{3\}$ is closed (state 3 only transitions to itself) and finite, hence recurrent by the corollary above — indeed $f_3 = \Pr(T_3<\infty\mid X_0=3)=1$ trivially since $p_{33}=1$. Class $\{1,2\}$ is not closed, since $p_{23} = 0.5 > 0$ leaks out to state 3, which is outside $\{1,2\}$. We show directly that $1$ (hence, by solidarity, also $2$) is transient. Started at state 1, at each visit to $\{1,2\}$ there is a fixed positive probability of eventually being routed to state 2 and then absorbed into state 3, never to return. Precisely, let $u = \Pr(\text{absorbed in } 3 \text{ eventually} \mid X_0=1)$ and $v = \Pr(\text{absorbed in }3\mid X_0=2)$. Conditioning on the first step,

From the first equation, $0.5 u = 0.5 v \Rightarrow u = v$. Substituting into the second: $v = 0.2v + 0.3v + 0.5 = 0.5v + 0.5 \Rightarrow 0.5v = 0.5 \Rightarrow v=1$, hence $u=1$. So absorption into $\{3\}$ is certain from either state 1 or 2 — the class $\{1,2\}$ is abandoned with probability 1, confirming transience: $f_1 < 1$ (in fact the chain visits $\{1,2\}$ only a random finite number of times before leaving forever), matching the theorem that non-closed finite classes are transient (a fact one proves the same way: any state with a positive-probability path leading out of its class and never returning is transient, since $u=v=1$ shows the class is left with probability 1, so in particular the return probability to state 1 restricted to using only within-class steps forever is impossible; a fully rigorous version follows the series test, and one can check directly $p_{11}^{(n)} \to 0$ geometrically fast here since the substochastic sub-block on $\{1,2\}$ has spectral radius $<1$).

Example 2: Simple random walk on $\mathbb{Z}$ with parameter $p \ne 1/2$ (asymmetric case) — a transient irreducible chain. Let $S = \mathbb{Z}$, and let $X_n$ be the position after $n$ steps of a walk that moves $+1$ with probability $p$ and $-1$ with probability $q=1-p$, independently at each step, $0<p<1$. This chain is irreducible: from any $i$ one can reach any $j$ (if $j>i$, take $j-i$ steps of $+1$, each with positive probability $p^{j-i}>0$; if $j<i$, symmetric argument with $q$). By solidarity, all states share the same recurrence type, so it suffices to test state $0$. We compute $p_{00}^{(n)}$. A return to $0$ after $n$ steps requires $n=2k$ even (an odd number of $\pm1$ steps cannot sum to zero, by a parity/parity-of-sum argument: the sum of $n$ terms each $\pm1$ has the same parity as $n$). For $n=2k$, a return to $0$ requires exactly $k$ up-steps and $k$ down-steps, in any order, so

We must determine whether $\sum_{k=1}^\infty \binom{2k}{k}(pq)^k$ converges or diverges. Use Stirling's approximation: $\binom{2k}{k} \sim \dfrac{4^k}{\sqrt{\pi k}}$ as $k\to\infty$ (a standard consequence of Stirling's formula $n! \sim \sqrt{2\pi n}\,(n/e)^n$, applied to $(2k)!/(k!)^2$). Hence

Since $p \ne 1/2$, by AM–GM we have $pq = p(1-p) < 1/4$ strictly (with equality only at $p=1/2$), so $r := 4pq \in [0,1)$ is a fixed number strictly less than $1$. Then $\binom{2k}{k}(pq)^k \sim r^k/\sqrt{\pi k}$, and since $r<1$ this is the general term of a convergent series (geometric decay dominates the sub-exponential $1/\sqrt{k}$ factor; formally, $r^k/\sqrt{\pi k} \le r^k$ for $k\ge1$, and $\sum r^k <\infty$ for $r<1$, and the ratio test on the asymptotic equivalence confirms convergence of the original series). Therefore

By the series criterion, state $0$ — and, by solidarity, every state — is transient whenever $p \ne 1/2$. (For contrast, at $p=1/2$, $\binom{2k}{k}(1/4)^k \sim 1/\sqrt{\pi k}$, and $\sum 1/\sqrt{k}$ diverges, so the symmetric random walk on $\mathbb{Z}$ is recurrent — the celebrated Pólya recurrence result, foreshadowing finer classification of recurrence strength.) This example is instructive: irreducibility alone says nothing about recurrence — the same irreducible graph structure (nearest-neighbor walk on $\mathbb{Z}$) is recurrent at $p=1/2$ and transient for every $p \ne 1/2$, illustrating that recurrence is a genuinely probabilistic (not purely combinatorial) property, decided by the quantitative series test rather than by connectivity alone.