Periods in Cyclic Decompositions

Why Period Creates a Cycle of Classes

In an irreducible chain, states can communicate but need not be reachable at every number of steps. A chain may, for example, alternate between two groups of states: one step always moves from the first group to the second, and the next step returns to the first. The period records this timing constraint. The cyclic decomposition makes the constraint visible by partitioning the states into subclasses that transitions visit in a fixed order.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a nonempty finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its transition matrix \(P=(p_{ij})\) is row-stochastic, so \(\sum_{j\in S}p_{ij}=1\) for every \(i\in S\). A path of length \(n\) from \(i\) to \(j\) is a sequence \(i=i_0,i_1,\ldots,i_n=j\) for which each transition has positive probability. In an irreducible chain, for every pair \(i,j\in S\), there is such a path from \(i\) to \(j\).

For a state \(i\), its period is \(d(i)=\gcd\{n\ge1:p_{ii}^{(n)}>0\}\), where \(P^{(n)}=P^n\). Thus the set inside the greatest common divisor consists of the possible positive return times to \(i\). In an irreducible chain this set is nonempty: if there is more than one state, irreducibility gives a positive-length path from \(i\) to another state and back; if \(S=\{i\}\), row-stochasticity gives \(p_{ii}=1\). We use the standard result from the earlier material on periods that communicating states have the same period. Write this common positive integer as \(d\).

The definition uses path lengths, not probabilities of being at a state at a particular time. Its key requirement is that every path from \(o\) to a fixed state has the same length modulo \(d\). The theorem below establishes this and the main properties of the resulting classes.

Proof. First we show that every path from \(o\) to a fixed state \(j\) has the same length modulo \(d\). If \(j=o\), every positive-length path from \(o\) to itself is a return path, so its length is divisible by \(d\); the length-zero path is also congruent to zero. If \(j\ne o\), take any two paths from \(o\) to \(j\), of lengths \(m\) and \(n\). By irreducibility, choose a path from \(j\) back to \(o\) of some positive length \(\ell\). Appending that same path to each of the two paths produces positive return paths from \(o\) with lengths \(m+\ell\) and \(n+\ell\). By the definition of \(d\), both lengths are divisible by \(d\). Their difference \(m-n\) is therefore divisible by \(d\). This proves that the residue used to define \(C_r\) is independent of the chosen path.

Every state belongs to some \(C_r\), because irreducibility provides a path from \(o\) to that state, whose length has a residue modulo \(d\). The path-length property just proved means a state cannot belong to two different subclasses, so the subclasses are pairwise disjoint and their union is \(S\). To prove nonemptiness, choose a positive return path from \(o\) to \(o\), of length \(L\). Its length is divisible by \(d\), so \(L\ge d\). For each \(r\in\{0,\ldots,d-1\}\), take the endpoint of the first \(r\) steps of this path, taking the endpoint to be \(o\) when \(r=0\). This state is reachable from \(o\) in exactly \(r\) steps, so it belongs to \(C_r\). Finally, suppose \(i\in C_r\) and \(p_{ij}>0\). A path from \(o\) to \(i\), followed by the positive transition from \(i\) to \(j\), is a path from \(o\) to \(j\) whose length is one more. Thus \(j\in C_{r+1\pmod d}\). All assertions follow. \(\square\)

What the Transition Rule Says

The theorem asserts that every positive-probability transition advances one subclass, including transitions that cross from \(C_{d-1}\) back to \(C_0\). It does not say that every state in \(C_r\) can transition to every state in \(C_{r+1\pmod d}\); it specifies where a transition may go, not which transitions must exist.

The same rule applies to paths of any length. If \(i\in C_r\) and a path of length \(n\) from \(i\) to \(j\) has positive probability, then \(j\in C_{r+n\pmod d}\). This follows by applying the one-step rule successively along the path: after the first step the class index has increased by one, after the second by two, and after \(n\) steps by \(n\), with indices taken modulo \(d\). In particular, if \(p_{ij}^{(n)}>0\), then \(j\in C_{r+n\pmod d}\). For a countable state space, a positive \(n\)-step transition probability is a sum of nonnegative probabilities over length-\(n\) paths; if that sum is positive, at least one path in the sum has positive probability.

A Pitfall About Residues

A tempting but incorrect argument says that because the greatest common divisor of the return times is \(d\), their residues modulo \(d\) generate every residue modulo \(d\). This cannot be right: each positive return time is divisible by \(d\), so each has residue \(0\) modulo \(d\). For example, if the return times are \(2,4,6,\ldots\), their residues modulo \(2\) are all \(0\); those residues do not generate the residue \(1\).

The correct nonemptiness argument uses a return path, not the residues of return times. Choose a positive return path of length \(L\). Since \(d\) divides \(L\), \(L\ge d\). For each \(r\in\{0,\ldots,d-1\}\), the endpoint after the first \(r\) steps is reachable from the reference state in \(r\) steps, and hence lies in \(C_r\). This directly supplies a state in every subclass. In the two-step return path \(o\to x\to o\) when \(d=2\), the prefix of length one reaches \(x\in C_1\), while \(o\in C_0\).

Another useful discipline is to distinguish what the construction proves from what it does not. Every positive transition must advance one class, but the theorem does not assert that all transitions between consecutive classes have positive probability. Nor does it assert that the chain’s distribution is stationary or converges; the cyclic partition is a structural statement about possible paths.