37.05.02 · probability / 05-markov-chains

Class Structure, Irreducibility, and Periodicity

shipped3 tiersLean: none

Anchor (Master): Norris 1997 *Markov Chains* (Cambridge) §1.2-1.3, §1.8; Levin-Peres 2017 *Markov Chains and Mixing Times* 2e §1.3 (irreducibility, period); Seneta 2006 *Non-negative Matrices and Markov Chains* 2e Ch. 1 (Perron-Frobenius and cyclic structure)

Intuition Beginner

A Markov chain moves among states one step at a time, and the very first thing to ask about it is a question of geography: starting from one state, which other states can the chain ever reach? Some states can be visited from the start; others are walled off and can never be entered once you leave; still others, once entered, can never be escaped. Sorting the states by who-can-reach-whom is the single most useful thing you can do before computing any probabilities.

Say a state $j$ is reachable from a state $i$ if there is some sequence of allowed one-step moves that carries the chain from $i$ to $j$ . If $i$ can reach $j$ and $j$ can reach $i$ , the two states communicate: each is accessible from the other. Communicating is an all-or-nothing partnership, and it splits the states into groups, called classes, where everyone inside a group communicates with everyone else in the group. A chain where the whole state space is one single class — everyone can get to everyone — is called irreducible, and irreducible chains are the clean, indecomposable building blocks of the theory.

There is a second, more delicate rhythm hidden inside a class: timing. Suppose that whenever the chain leaves a state it can only return after a number of steps that is always a multiple of three. Then the state has a built-in beat of three, and the chain visits it only on steps three, six, nine, and so on. That beat is the period of the state. When the only common rhythm is a beat of one — the chain can return after some run of consecutive step-counts with no forced gap — the state is called aperiodic, and the chain mixes freely instead of marching in lockstep.

These two features, who-reaches-whom and the hidden beat, are exactly what decide whether a chain settles into a single steady pattern or splits and cycles. The remarkable fact is that the beat is shared by everyone in a class: all states that communicate march to the same period.

The one-sentence takeaway: before computing anything, sort the states into communicating classes and find each class's period, because irreducibility (one class) and aperiodicity (beat one) are the two conditions that let a chain settle to a single long-run pattern.

Visual Beginner

Picture five states drawn as labeled circles with one-way arrows showing which one-step moves are allowed.

Left: the three dashed boxes are the communicating classes. The two-circle clusters ${A, B}$ and ${D, E}$ are classes where both members reach each other; the lone state $C$ is its own class because nothing returns to it. The ${D, E}$ box is closed: once you enter it you cannot leave. Right: two states with different beats — one revisited only on multiples of three, one revisited on a run of consecutive step counts — show what the period measures.

Worked example Beginner

Take a chain on four states ${1, 2, 3, 4}$ with these allowed one-step moves: from $1$ you go to $2$ ; from $2$ you go to $1$ or to $3$ ; from $3$ you go to $4$ ; from $4$ you go to $3$ . We classify the states.

Step 1. Check whether $1$ and $2$ communicate. From $1$ you can reach $2$ in one step. From $2$ you can reach $1$ in one step. Each reaches the other, so $1$ and $2$ communicate and sit in the same class.

Step 2. Check whether $3$ and $4$ communicate. From $3$ you reach $4$ in one step, and from $4$ you reach $3$ in one step. So $3$ and $4$ communicate and form a class.

Step 3. Can the two pairs reach each other? From $2$ you can step to $3$ , so ${1, 2}$ can reach ${3, 4}$ . But from $3$ and $4$ the only moves stay inside ${3, 4}$ — there is no arrow back to $1$ or $2$ . So ${3, 4}$ cannot reach ${1, 2}$ . The two pairs do not communicate, and there are two classes: ${1, 2}$ and ${3, 4}$ .

Step 4. Decide which classes are closed. From ${3, 4}$ every move stays inside ${3, 4}$ , so it is closed — the chain gets trapped there. From ${1, 2}$ there is an escape (the move $2 \to 3$ ), so ${1, 2}$ is not closed.

Step 5. Find the beat of the closed class ${3, 4}$ . Starting at $3$ , you return to $3$ after $3 \to 4 \to 3$ , which takes two steps, and any return uses an even number of steps because each visit to $3$ alternates with a visit to $4$ . So the period of $3$ (and of $4$ ) is two.

What this tells us: the chain is not irreducible — it has two classes — and it eventually falls into the closed class ${3, 4}$ , where it oscillates with period two forever. We learned the whole long-run shape of the chain purely from the arrow pattern, before assigning a single probability.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $(X_{n})_{n \geq 0}$ is a time-homogeneous Markov chain on a countable state space $I$ with stochastic transition matrix $P = (p_{ij})$ and $n$ -step matrix $P^{n} = (p_{ij}^{(n)})$ , in the sense of 37.05.01. Write $p_{ij}^{(0)} = δ_{ij}$ .

Definition (accessibility). State $j$ is accessible from state $i$ , written $i \to j$ , if $p_{ij}^{(n)} > 0$ for some $n \geq 0$ . Equivalently, $i \to j$ iff there is a path $i = i_{0}, i_{1}, \dots, i_{n} = j$ with $p_{i_{r} i_{r + 1}} > 0$ for each $r$ . Because $p_{ii}^{(0)} = 1$ , one always has $i \to i$ .

Definition (communication). States $i$ and $j$ communicate, written $i \leftrightarrow j$ , if $i \to j$ and $j \to i$ .

Definition (communicating class). The relation $\leftrightarrow$ is an equivalence relation on $I$ (see the Key theorem). Its equivalence classes are the communicating classes of the chain. A class $C$ is closed if $i \in C$ and $i \to j$ together imply $j \in C$ — once entered, the chain cannot leave $C$ . A singleton closed class ${i}$ , equivalently a state with $p_{ii} = 1$ , is absorbing. A class that is not closed is open (the chain can escape it).

Definition (irreducibility). The chain (or its matrix $P$ ) is irreducible if $I$ is a single communicating class, i.e. $i \leftrightarrow j$ for all $i, j \in I$ .

Definition (period). For a state $i$ with $R_{i} := {n \geq 1 : p_{ii}^{(n)} > 0} \neq = \emptyset$ , the period of $i$ is $d (i) := g cd R_{i} = g cd {n \geq 1 : p_{ii}^{(n)} > 0} .$ A state $i$ is aperiodic if $d (i) = 1$ and periodic if $d (i) > 1$ . If $R_{i} = \emptyset$ (the chain started at $i$ never returns to $i$ with positive probability) the period is left undefined; this can only happen in an open class. A chain is called aperiodic when every state has period $1$ ; for an irreducible chain this is a property of the single class.

Definition (cyclic / periodic subclasses). Let $C$ be a communicating class of common period $d$ . Fix a reference state $i_{0} \in C$ and, for each $j \in C$ , set $r (j) := (any n with p_{i_{0} j}^{(n)} > 0) mod d .$ The Key theorem shows $r (j)$ is well-defined. The periodic subclasses (or cyclic classes) are $C_{0}, C_{1}, \dots, C_{d - 1}$ with $C_{s} = {j \in C : r (j) = s}$ ; they partition $C$ , and $P$ maps $C_{s}$ into $C_{s + 1 mod d}$ .

Counterexamples to common slips Intermediate+

Accessibility is not symmetric; communication is. In the worked example $2 \to 3$ but not $3 \to 2$ , so $2 \to 3$ holds while $2 \leftrightarrow 3$ fails. The relation $\to$ is a preorder (reflexive and transitive); only the symmetrized relation $\leftrightarrow$ partitions $I$ .
A closed class need not be all of a finite chain, but a finite chain must contain at least one closed class. On a finite state space the chain cannot escape forever, so the accessibility preorder has a maximal class with no outward edge. An infinite chain can have every class open — the simple random walk on $Z$ is irreducible (one open-by-default class, here the whole space) with no proper closed subclass.
Period is about the support of returns, not their probability. $d (i) = g cd {n : p_{ii}^{(n)} > 0}$ counts which return times are possible, ignoring how likely they are. A self-loop $p_{ii} > 0$ forces $1 \in R_{i}$ and hence $d (i) = 1$ ; a single self-loop anywhere in an irreducible chain makes the whole chain aperiodic.
Periodicity is not the same as never returning quickly. A state can have period $1$ yet typically take many steps to return; aperiodicity asserts only that the gcd of the possible return lengths is $1$ , e.g. because both a length- $2$ and a length- $3$ return exist, since $g cd (2, 3) = 1$ .

Key theorem with proof Intermediate+

Theorem (class structure and period invariance). Let $(X_{n})$ be a Markov chain on $I$ with matrix $P$ .

(a) The relation $\leftrightarrow$ is an equivalence relation on $I$ , so $I$ partitions into communicating classes.

(b) The period is constant on each communicating class: if $i \leftrightarrow j$ and both periods are defined, then $d (i) = d (j)$ .

Proof. The engine is the multiplicativity inequality for the $n$ -step probabilities. For all states $a, b, c$ and all $m, n \geq 0$ , the Chapman-Kolmogorov identity of 37.05.01 gives $p_{a c}^{(m + n)} = \sum_{k} p_{ak}^{(m)} p_{k c}^{(n)} \geq p_{ab}^{(m)} p_{b c}^{(n)}$ , since all terms are nonnegative and the right-hand side is the single term $k = b$ . Thus $p_{ab}^{(m)} > 0 and p_{b c}^{(n)} > 0 ⟹ p_{a c}^{(m + n)} > 0. (*)$

Part (a). Reflexivity: $p_{ii}^{(0)} = 1 > 0$ gives $i \to i$ , hence $i \leftrightarrow i$ . Symmetry: $i \leftrightarrow j$ means $i \to j$ and $j \to i$ , which is exactly $j \leftrightarrow i$ . Transitivity: suppose $i \leftrightarrow j$ and $j \leftrightarrow k$ . Then $i \to j$ and $j \to k$ give, by $(*)$ , $i \to k$ ; symmetrically $k \to j$ and $j \to i$ give $k \to i$ . Hence $i \leftrightarrow k$ . So $\leftrightarrow$ is an equivalence relation and its classes partition $I$ .

Part (b). Let $i \leftrightarrow j$ with $i \neq = j$ (the case $i = j$ is immediate). Since $i \to j$ and $j \to i$ , choose $r, s \geq 1$ with $p_{ij}^{(r)} > 0$ and $p_{j i}^{(s)} > 0$ . By $(*)$ , $p_{ii}^{(r + s)} \geq p_{ij}^{(r)} p_{j i}^{(s)} > 0$ , so $r + s \in R_{i}$ and therefore $d (i) ∣ (r + s)$ .

Now take any $n \in R_{j}$ , i.e. $p_{j j}^{(n)} > 0$ . Concatenating the three legs $i \to j$ (length $r$ ), $j \to j$ (length $n$ ), $j \to i$ (length $s$ ) and applying $(*)$ twice, $p_{ii}^{(r + n + s)} \geq p_{ij}^{(r)} p_{j j}^{(n)} p_{j i}^{(s)} > 0,$ so $r + n + s \in R_{i}$ and hence $d (i) ∣ (r + n + s)$ . Subtracting the relation $d (i) ∣ (r + s)$ gives $d (i) ∣ n$ . As $n \in R_{j}$ was arbitrary, $d (i)$ is a common divisor of $R_{j}$ , so $d (i) ∣ g cd R_{j} = d (j)$ . Interchanging the roles of $i$ and $j$ yields $d (j) ∣ d (i)$ . Two positive integers dividing each other are equal, so $d (i) = d (j)$ . $□$

Bridge. This theorem builds toward the entire equilibrium theory of 37.05.03 and appears again in every convergence statement for Markov chains, because the partition into classes and the class-period are precisely the invariants that decide whether a chain has a unique stationary distribution and whether its powers $P^{n}$ converge. The foundational reason the proof is so short is the path-concatenation inequality $(*)$ : accessibility is transitive because positive-probability paths compose, and that one fact gives both the equivalence relation and the divisibility bookkeeping behind period invariance. This is exactly the combinatorial shadow of the matrix identity $P^{m + n} = P^{m} P^{n}$ from 37.05.01; the support pattern of the nonnegative matrix $P$ is all that the class structure sees. Restricting $P$ to a single closed communicating class produces an irreducible stochastic matrix, and the central insight is that an irreducible aperiodic matrix is exactly the class to which the Perron-Frobenius convergence theorem applies — putting these together, class decomposition reduces every finite chain to its irreducible closed blocks, and the bridge is that period one in each such block is the precise gateway to $P^{n}$ converging to a rank-one limit.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

Let $C$ be a communicating class of period $d$ and fix $i_{0} \in C$ . Show that the residue $r (j) = n mod d$ for any $n$ with $p_{i_{0} j}^{(n)} > 0$ is independent of the chosen $n$ , so the periodic subclasses $C_{s}$ are well-defined.

Hint

If $p_{i_{0} j}^{(m)} > 0$ and $p_{i_{0} j}^{(n)} > 0$ , append a return path $j \to i_{0}$ to each and use that the resulting closed loops at $i_{0}$ are multiples of $d$ .

Answer

Suppose $p_{i_{0} j}^{(m)} > 0$ and $p_{i_{0} j}^{(n)} > 0$ . Since $j \to i_{0}$ (same class), pick $s$ with $p_{j i_{0}}^{(s)} > 0$ . By path concatenation $p_{i_{0} i_{0}}^{(m + s)} > 0$ and $p_{i_{0} i_{0}}^{(n + s)} > 0$ , so $m + s$ and $n + s$ both lie in $R_{i_{0}}$ and are divisible by $d = d (i_{0})$ . Subtracting, $d ∣ (m + s) - (n + s) = m - n$ , so $m \equiv n (mod d)$ . Hence $r (j)$ is the same residue for every admissible $n$ , and $C_{s} = {j : r (j) = s}$ partitions $C$ . Finally, if $p_{j k} > 0$ with $j \in C_{s}$ , then any path of length $n \equiv s$ into $j$ extends to length $n + 1 \equiv s + 1$ into $k$ , so $P$ maps $C_{s}$ into $C_{s + 1 mod d}$ .

Exercise 6 (medium, multiple choice).

For an irreducible chain of period $d$ , the matrix $P^{d}$ restricted to a single periodic subclass $C_{s}$ is:

A. The zero matrix B. Irreducible and aperiodic on $C_{s}$ C. Periodic of period $d$ on $C_{s}$ D. Not stochastic

Hint

$P$ cycles $C_{0} \to C_{1} \to \dots \to C_{d - 1} \to C_{0}$ , so $P^{d}$ maps each $C_{s}$ back into itself in $d$ steps.

Answer

B. Irreducible and aperiodic on $C_{s}$ . Since $P$ sends $C_{s} \to C_{s + 1 mod d}$ , the $d$ -step matrix $P^{d}$ maps $C_{s}$ into itself, and the restriction $P^{d} ∣_{C_{s}}$ is an irreducible stochastic matrix on $C_{s}$ whose return times are multiples of $1$ in the rescaled clock (gcd of ${n : (P^{d})_{j j}^{(n)} > 0}$ is $1$ ), hence aperiodic. This is the standard reduction: the cyclic decomposition turns a period- $d$ chain into $d$ aperiodic sub-chains run on the slowed clock $P^{d}$ , to which the convergence theory applies directly.

Exercise 7 (hard, symbolic).

Prove the numerical-semigroup lemma needed for periodicity: if $A \subseteq Z_{\geq 1}$ is closed under addition with $g cd A = d$ , then there is $N$ such that $A$ contains every multiple $k d$ with $k \geq N$ . Deduce that for an aperiodic state $i$ , $p_{ii}^{(n)} > 0$ for all sufficiently large $n$ .

Hint

By Bezout, finitely many elements of $A$ have gcd $d$ ; write $d$ as an integer combination of them and clear signs using that $A$ is closed under addition. Treat $d = 1$ first.

Answer

Rescale by $d$ : replacing each $a \in A$ by $a / d$ we may assume $g cd A = 1$ , and it suffices to show $A$ contains all large integers. Since $g cd A = 1$ , by Bezout there are finitely many $a_{1}, \dots, a_{r} \in A$ and integers $c_{1}, \dots, c_{r}$ with $\sum c_{ℓ} a_{ℓ} = 1$ . Split into positive and negative coefficients: $\sum_{c_{ℓ} > 0} c_{ℓ} a_{ℓ} - \sum_{c_{ℓ} < 0} (- c_{ℓ}) a_{ℓ} = 1$ , i.e. $u - v = 1$ where $u, v$ are both sums of elements of $A$ (with repetition), hence $u, v \in A$ by addition-closure, and $u = v + 1$ . Now for any $m \geq v^{2}$ write $m = q v + t$ with $0 \leq t < v$ and $q \geq v > t$ by the size of $m$ ; then $m = q v + t (u - v) = (q - t) v + t u$ , a sum of $(q - t) \geq 0$ copies of $v$ and $t \geq 0$ copies of $u$ , all in $A$ , so $m \in A$ . Thus $A$ contains every integer $\geq v^{2}$ ; taking $N = v^{2}$ and rescaling gives the claim for general $d$ . For an aperiodic state, $d (i) = 1$ and $A = R_{i}$ is addition-closed (Exercise 3), so $R_{i} \supseteq {n : n \geq N}$ for some $N$ , i.e. $p_{ii}^{(n)} > 0$ for all $n \geq N$ .

Exercise 8 (hard, symbolic).

Let $P$ be irreducible and aperiodic on a finite state space $I$ . Prove there is $M$ with $p_{ij}^{(n)} > 0$ for all $i, j$ and all $n \geq M$ (the matrix $P^{n}$ is strictly positive eventually — primitivity).

Hint

Combine Exercise 7 (each diagonal entry is eventually positive) with finite reach-times $r (i, j)$ from $i$ to $j$ , then take a maximum over the finite state space.

Answer

By Exercise 7, for each $i$ there is $N_{i}$ with $p_{ii}^{(n)} > 0$ for all $n \geq N_{i}$ ; set $N = max_{i} N_{i}$ , finite since $I$ is finite. By irreducibility, for each ordered pair $(i, j)$ pick $r (i, j) \geq 0$ with $p_{ij}^{(r (i, j))} > 0$ ; let $R = max_{i, j} r (i, j)$ , again finite. Fix $i, j$ and $n \geq M := N + R$ . Write $n = (n - r (i, j)) + r (i, j)$ ; since $n - r (i, j) \geq N \geq N_{i}$ , we have $p_{ii}^{(n - r (i, j))} > 0$ , and by path concatenation $p_{ij}^{(n)} \geq p_{ii}^{(n - r (i, j))} p_{ij}^{(r (i, j))} > 0$ . As $i, j$ were arbitrary, $P^{n}$ is strictly positive for every $n \geq M$ . Such a $P$ is called primitive, and primitivity is precisely the hypothesis of the Perron-Frobenius convergence theorem guaranteeing $P^{n} \to 1 π$ with $π$ the unique stationary distribution.

Advanced results Master

The class structure refines into a triangular block form for the matrix, the cyclic decomposition rewrites an irreducible periodic chain as a permutation of aperiodic blocks, and the entire combinatorial picture is the nonnegative-matrix shadow of Perron-Frobenius theory.

Theorem 1 (canonical block decomposition). Order the states of a finite chain so that the open classes precede the closed classes and the accessibility preorder is respected. Then $P$ takes the block-upper-triangular form $P = (Q 0 R S), S = diag (S_{1}, \dots, S_{c}),$ where each $S_{t}$ is the irreducible stochastic matrix of a closed class, $Q$ collects the transient open classes, and $R$ records escapes from open into closed classes. The closed-class blocks $S_{t}$ are the indecomposable units: every long-run quantity factors through them, while $Q^{n} \to 0$ entrywise because the chain leaves the transient part with probability one (on a finite space). Restricting attention to one closed class is thus exactly the passage to an irreducible chain.

Theorem 2 (cyclic decomposition of an irreducible class). Let $P$ be irreducible of period $d$ on $I$ , with periodic subclasses $C_{0}, \dots, C_{d - 1}$ defined by the residue map. With states ordered by subclass, $P$ has the cyclic block form $P = 00 ⋮ 0 P_{d - 1} P_{0} 000 0 P_{1} 00 \dots \dots ⋱ \dots \dots 00 ⋮ P_{d - 2} 0,$ where $P_{s}$ is the (stochastic) block carrying $C_{s}$ to $C_{s + 1 mod d}$ . Consequently $P^{d} = diag (P_{0} P_{1} \dots P_{d - 1}, \dots)$ is block-diagonal, and each diagonal block is an irreducible aperiodic stochastic matrix on its subclass. The period- $d$ chain is therefore $d$ aperiodic chains glued by a cyclic shift, and $P^{n d} ∣_{C_{s}}$ converges while $P^{n}$ itself rotates through the subclasses without settling.

Theorem 3 (Perron-Frobenius for the irreducible aperiodic case). Let $P$ be a finite irreducible stochastic matrix. Its spectral radius is $1$ , attained by the simple eigenvalue $1$ with strictly positive left eigenvector $π$ (the unique stationary distribution) and right eigenvector $1$ . The peripheral spectrum — eigenvalues of modulus $1$ — is exactly ${e^{2 π i s / d} : s = 0, \dots, d - 1}$ , the $d$ -th roots of unity, where $d$ is the period; these are simple, and apart from them every eigenvalue has modulus $< 1$ . When $d = 1$ (aperiodic, equivalently primitive by Exercise 8), $1$ is the only peripheral eigenvalue and $P^{n} \to 1 π$ geometrically with rate the second-largest modulus $∣ λ_{2} ∣ < 1$ . When $d > 1$ , the $d$ unimodular eigenvalues encode the rotation of mass through the cyclic subclasses, and convergence holds only along the subsequence $P^{n d}$ .

Theorem 4 (canonical form is invariant). The partition into communicating classes, the closed/open dichotomy, and each class period are intrinsic to $P$ — invariant under relabeling of states — because they are defined through the support pattern ${(i, j) : p_{ij} > 0}$ and its transitive closure alone. Two stochastic matrices with the same directed support graph have identical class structure and periods, regardless of the numerical values of the positive entries; the probabilities enter only at the level of stationary distributions and mixing rates, not at the level of the combinatorial skeleton.

Synthesis. The foundational reason the whole subject organizes itself is that the support graph of the nonnegative matrix $P$ carries all the class information, and putting these together, accessibility is the reachability preorder of that graph while communication is its symmetrization into the strongly-connected components — the communicating classes. This is exactly the combinatorial content of the semigroup law $P^{m + n} = P^{m} P^{n}$ inherited from 37.05.01: path concatenation makes accessibility transitive, which gives both the equivalence relation and, through addition-closure of return times, the class-invariance of the period. The central insight is that an irreducible chain is dual to a single strongly connected component, and its period — the gcd of return lengths — is dual to the greatest common cyclic length of that component, so the cyclic decomposition of Theorem 2 is the graph-theoretic statement that a strongly connected digraph of index $d$ partitions into $d$ cyclically-ordered levels. The bridge to analysis is Perron-Frobenius (Theorem 3): irreducibility makes the eigenvalue $1$ simple, aperiodicity makes it the only unimodular eigenvalue, and these two combinatorial conditions are exactly what the convergence theorem $P^{n} \to 1 π$ of 37.05.03 requires. The block decomposition reduces every finite chain to its irreducible closed blocks, the cyclic decomposition reduces every periodic block to aperiodic sub-blocks on the slowed clock $P^{d}$ , and the foundational reason this two-step reduction terminates is that irreducible aperiodic — primitive — is the indecomposable atom of the theory, the precise object on which long-run behavior is a single stationary law.

Full proof set Master

Proposition 1 (accessibility is a preorder; communication its symmetrization). The relation $\to$ on $I$ is reflexive and transitive, and $i \leftrightarrow j$ iff $i \to j$ and $j \to i$ defines the associated equivalence relation.

Proof. Reflexivity: $p_{ii}^{(0)} = 1 > 0$ . Transitivity: if $i \to j$ and $j \to k$ , take $m, n$ with $p_{ij}^{(m)} > 0$ , $p_{j k}^{(n)} > 0$ ; then $p_{ik}^{(m + n)} \geq p_{ij}^{(m)} p_{j k}^{(n)} > 0$ , so $i \to k$ . The symmetrization of any preorder $R$ via " $x R y$ and $y R x$ " is reflexive (from reflexivity of $R$ ), symmetric (by construction), and transitive (compose in both directions), hence an equivalence relation; applying this to $\to$ gives $\leftrightarrow$ . $□$

Proposition 2 (period is well-defined and class-invariant). If $R_{i} \neq = \emptyset$ then $d (i) = g cd R_{i} \geq 1$ exists, and $i \leftrightarrow j$ implies $d (i) = d (j)$ .

Proof. Existence is the gcd of a nonempty set of positive integers. For invariance, choose $r, s \geq 1$ with $p_{ij}^{(r)}, p_{j i}^{(s)} > 0$ . Then $r + s \in R_{i}$ , so $d (i) ∣ r + s$ . For any $n \in R_{j}$ , concatenation gives $r + n + s \in R_{i}$ , so $d (i) ∣ r + n + s$ ; subtracting, $d (i) ∣ n$ . Hence $d (i)$ divides every element of $R_{j}$ , so $d (i) ∣ d (j)$ , and symmetrically $d (j) ∣ d (i)$ , giving equality. $□$

Proposition 3 (return set is a numerical semigroup; eventual positivity). $R_{i}$ is closed under addition, and if $d (i) = d$ then $R_{i} \supseteq {k d : k \geq N}$ for some $N$ .

Proof. Addition-closure: $p_{ii}^{(m + n)} \geq p_{ii}^{(m)} p_{ii}^{(n)} > 0$ for $m, n \in R_{i}$ . For the eventual-positivity claim, rescale by $d$ so $g cd = 1$ . By Bezout choose finitely many elements with integer combination equal to $1$ ; separating positive and negative coefficients exhibits $u, v \in ⟨ R_{i} ⟩$ (the additive span, contained in $R_{i}$ by closure) with $u = v + 1$ . For $m \geq v^{2}$ , division $m = q v + t$ ( $0 \leq t < v \leq q$ ) gives $m = (q - t) v + t u \in R_{i}$ . Rescaling restores the multiples of $d$ . $□$

Proposition 4 (well-definedness of periodic subclasses). For an irreducible class $C$ of period $d$ and fixed $i_{0} \in C$ , the residue $r (j) = n mod d$ over admissible $n$ (those with $p_{i_{0} j}^{(n)} > 0$ ) is independent of $n$ , and $P (C_{s}) \subseteq C_{s + 1 mod d}$ .

Proof. If $p_{i_{0} j}^{(m)}, p_{i_{0} j}^{(n)} > 0$ , pick $s$ with $p_{j i_{0}}^{(s)} > 0$ (since $j \to i_{0}$ ). Then $m + s, n + s \in R_{i_{0}}$ are both divisible by $d$ , so $d ∣ (m - n)$ , giving $m \equiv n (mod d)$ . If $j \in C_{s}$ and $p_{j k} > 0$ , then a length- $n$ path into $j$ with $n \equiv s$ extends to a length- $(n + 1)$ path into $k$ , so $r (k) \equiv s + 1$ , i.e. $k \in C_{s + 1 mod d}$ . $□$

Proposition 5 (cyclic blocks and aperiodicity of $P^{d}$ on a subclass). With the cyclic block form of Theorem 2, $P^{d}$ is block-diagonal and each block $P^{d} ∣_{C_{s}}$ is irreducible and aperiodic on $C_{s}$ .

Proof. Since $P (C_{s}) \subseteq C_{s + 1 mod d}$ , iterating $d$ times returns $C_{s}$ to itself, so $P^{d}$ leaves each $C_{s}$ invariant and is block-diagonal. Irreducibility on $C_{s}$ : for $j, k \in C_{s}$ , irreducibility of $P$ gives a path $j \to k$ of some length $m$ ; since $j, k$ share residue $s$ , $m \equiv 0 (mod d)$ , so $m = ℓ d$ and $(P^{d})_{j k}^{(ℓ)} > 0$ , i.e. $j$ reaches $k$ under $P^{d}$ . Aperiodicity: the $P^{d}$ -return times of $j$ are ${n : p_{j j}^{(n d)} > 0} = R_{j} / d$ , whose gcd is $d (j) / d = 1$ . $□$

Proposition 6 (finite irreducible aperiodic implies primitive). A finite irreducible aperiodic stochastic $P$ satisfies $p_{ij}^{(n)} > 0$ for all $i, j$ once $n \geq M$ , for some finite $M$ .

Proof. By Proposition 3 each diagonal entry is eventually positive: $p_{ii}^{(n)} > 0$ for $n \geq N_{i}$ ; set $N = max_{i} N_{i} < \infty$ . By irreducibility pick $r (i, j)$ with $p_{ij}^{(r (i, j))} > 0$ and let $R = max_{i, j} r (i, j) < \infty$ . For $n \geq M := N + R$ , write $n = (n - r (i, j)) + r (i, j)$ with $n - r (i, j) \geq N \geq N_{i}$ , so $p_{ij}^{(n)} \geq p_{ii}^{(n - r (i, j))} p_{ij}^{(r (i, j))} > 0$ . $□$

Connections Master

The Markov property, transition matrices, and Chapman-Kolmogorov 37.05.01 are the substrate: the inequality $p_{a c}^{(m + n)} \geq p_{ab}^{(m)} p_{b c}^{(n)}$ that powers every proof here is the single-term lower bound of the Chapman-Kolmogorov sum, and the $n$ -step matrix $P^{n}$ whose support defines accessibility is the matrix power established there. Class structure is exactly what the support pattern of those powers records, with the numerical probabilities suppressed.
The stationary distribution and convergence theory of irreducible aperiodic chains 37.05.03 consumes this unit's output directly: the existence and uniqueness of a stationary $π$ with $π P = π$ requires a single closed communicating class, and the convergence $P^{n} \to 1 π$ requires that class to be aperiodic; the period- $d$ case is handled there by passing to $P^{d}$ on each cyclic subclass, exactly the decomposition of Theorem 2.
The operator-semigroup and discrete-generator viewpoint introduced via 37.05.01 reappears spectrally: the period $d$ of an irreducible chain is the number of unimodular eigenvalues of $P$ (the $d$ -th roots of unity), so periodicity is the eigenvalue-on-the-unit-circle obstruction to convergence, and aperiodicity is precisely the spectral-gap condition that makes the discrete generator $P - I_{d}$ have $0$ as a simple, isolated eigenvalue.
The elementary probability and named-distribution layer 26.02.01 supplies the concrete instances on which class structure is read off — the gambler's-ruin walk with two absorbing classes, the cyclic random walk on $Z / d Z$ of period $d$ , and the two-state chain whose single self-loop makes it irreducible and aperiodic — each a worked classification of the kind this unit formalizes.

Historical & philosophical context Master

The decomposition of a chain into communicating classes and the notion of period were already implicit in Andrei A. Markov's founding 1906 paper ^{[Markov 1906]}, where the finite chains he studied to extend the law of large numbers were tacitly irreducible, so that the limit theorems he sought would hold uniformly; the systematic separation of the combinatorial class skeleton from the analytic limit behavior came only with the later matrix formulation.

The decisive analytic input is the theory of nonnegative matrices begun by Oskar Perron and completed for the reducible and periodic cases by Georg Frobenius. Frobenius's 1912 memoir on matrices with nonnegative entries ^{[Frobenius 1912]} introduced irreducibility (in the matrix sense of no nontrivial invariant coordinate subspace), proved that an irreducible nonnegative matrix has a simple positive Perron eigenvalue with a positive eigenvector, and identified the index of imprimitivity — the number of eigenvalues of maximal modulus — as the integer that organizes the cyclic block structure. Translated into the language of Markov chains, Frobenius's index of imprimitivity is exactly the period $d$ , his irreducibility is the single-communicating-class condition, and his cyclic normal form is the periodic-subclass decomposition. The modern textbook treatment on countable state spaces, with accessibility and communication defined through the $n$ -step probabilities and the period as the gcd of return times, follows Norris ^{[Norris 1997]} and the matrix-theoretic account of Seneta ^{[Seneta 2006]}, who makes the Perron-Frobenius-to-Markov-chain dictionary explicit.

Bibliography Master

@book{Norris1997,
  author    = {Norris, James R.},
  title     = {Markov Chains},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@article{Markov1906,
  author  = {Markov, Andrei A.},
  title   = {Rasprostranenie zakona bol'shih chisel na velichiny, zavisyashchie drug ot druga},
  journal = {Izvestiya Fiziko-matematicheskogo obshchestva pri Kazanskom universitete (2)},
  volume  = {15},
  year    = {1906},
  pages   = {135--156}
}

@article{Frobenius1912,
  author  = {Frobenius, Georg},
  title   = {\"Uber {M}atrizen aus nicht negativen {E}lementen},
  journal = {Sitzungsberichte der K\"oniglich Preussischen Akademie der Wissenschaften zu Berlin},
  year    = {1912},
  pages   = {456--477}
}

@book{Durrett2019mc,
  author    = {Durrett, Rick},
  title     = {Probability: Theory and Examples},
  edition   = {5},
  publisher = {Cambridge University Press},
  year      = {2019}
}

@book{LevinPeres2017,
  author    = {Levin, David A. and Peres, Yuval},
  title     = {Markov Chains and Mixing Times},
  edition   = {2},
  publisher = {American Mathematical Society},
  year      = {2017}
}

@book{Seneta2006,
  author    = {Seneta, Eugene},
  title     = {Non-negative Matrices and Markov Chains},
  edition   = {2},
  series    = {Springer Series in Statistics},
  publisher = {Springer},
  year      = {2006}
}

Prerequisites

37.05.01

Tier anchors

beginner: Norris 1997 *Markov Chains* (Cambridge) §1.2; informal picture of which weather states can eventually reach which others, drawn as arrows on a map
intermediate: Norris 1997 *Markov Chains* (Cambridge) §1.2-1.3; Durrett 2019 *Probability: Theory and Examples* 5e §5.2-5.3
master: Norris 1997 *Markov Chains* (Cambridge) §1.2-1.3, §1.8; Levin-Peres 2017 *Markov Chains and Mixing Times* 2e §1.3 (irreducibility, period); Seneta 2006 *Non-negative Matrices and Markov Chains* 2e Ch. 1 (Perron-Frobenius and cyclic structure)

References

Norris — Markov Chains · Cambridge University Press 1997, §1.2-1.3, §1.8
Markov — Rasprostranenie zakona bol'shih chisel na velichiny, zavisyashchie drug ot druga · Izvestiya Fiziko-matematicheskogo obshchestva pri Kazanskom universitete (2) 15 (1906), 135-156
Frobenius — Uber Matrizen aus nicht negativen Elementen · Sitzungsberichte der Koniglich Preussischen Akademie der Wissenschaften (1912), 456-477
Durrett — Probability: Theory and Examples, 5e · §5.2-5.3 (recurrence, class structure)
Levin-Peres — Markov Chains and Mixing Times, 2e · American Mathematical Society 2017, §1.3
Seneta — Non-negative Matrices and Markov Chains, 2e · Springer 2006, Ch. 1 (Perron-Frobenius theory, cyclic classes)

Estimated time

beginner: 18m
intermediate: 50m
master: 85m