Return-Time Sets and the Period of a State

Return Lengths and Period

A transition graph records which moves a Markov chain can make, but it also records timing information: a directed path that starts and ends at the same state is a possible return, and its length is the number of steps taken. The collection of possible return lengths, rather than any one selected path, determines the period of the state.

Throughout, let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its transition matrix is \(P=(p_{ij})\), with \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\). The transition graph has a directed edge from \(i\) to \(j\) exactly when \(p_{ij}>0\). A path of length \(n\) is a sequence \(i=x_0,x_1,\ldots,x_n=j\) whose consecutive pairs are edges. A path may repeat states or edges.

The restriction \(n\ge1\) matters. At time zero the chain is already at \(i\), so including \(n=0\) would add a length that says nothing about a return. Also, a return time means any positive number of steps at which the chain can be back at \(i\); it does not require that the chain avoid \(i\) at intermediate times.

Proof. For any fixed \(n\), the \(n\)-step transition probability is the sum over intermediate states of the products of the transition probabilities along each length-\(n\) path from \(i\) to \(i\). Each product is nonnegative. If such a path exists, every edge on it has positive probability, so its product is positive and contributes a positive term to \(p_{ii}^{(n)}\). Conversely, if \(p_{ii}^{(n)}>0\), the sum of these nonnegative terms is positive, so at least one term is positive. This is true for a finite or countable sum: a sum of nonnegative terms with every term zero is zero. A positive term comes from a path whose every transition has positive probability, which is a directed path in the transition graph. Thus the return lengths are exactly the lengths of directed closed walks from \(i\). If two transition matrices have the same positive-probability edges, they have the same such walks, hence the same \(R_i\) and \(d(i)\) whenever \(R_i\) is nonempty. \(\square\)

Reading Return Lengths Carefully

The proposition makes a graph the right object for identifying candidate return lengths. Starting at \(i\), follow directed edges and count every edge traversed. The path must finish at \(i\), but it may visit \(i\) before its final step. A path that returns to some other state is not by itself a return to \(i\), and an edge traversed in the wrong direction is not available.

It is useful to distinguish all return lengths from first-return lengths. Define \(T_i^+=\inf\{n\ge1:X_n=i\}\), with \(\inf\varnothing=\infty\). A first-return length is an \(n\ge1\) for which \(\mathbb{P}_i(T_i^+=n)>0\). The paths corresponding to these lengths have no intermediate visit to \(i\). Every return path can be split at its intermediate visits to \(i\) into first-return paths; conversely, first-return paths can be concatenated to form a return path.

Proof. Suppose there is a positive-probability return path of length \(n\) from \(i\) to \(i\). List, in increasing order, the times at which this path visits \(i\), including time zero and time \(n\). Consecutive times in this list differ by a positive first-return length: the path does not visit \(i\) between them. The sum of these differences is \(n\). In the other direction, take any finite list of positive first-return paths at \(i\). Concatenating them gives a directed path from \(i\) back to \(i\) whose length is the sum of their lengths. Every edge on the concatenated path has positive probability, so the path has positive probability and its length is in \(R_i\). \(\square\)

This distinction can change how a graph is read. The shortest return may be a first return, but other return lengths can be sums of first-return lengths. To find the period, the definition uses the entire set \(R_i\), including returns that revisit \(i\) along the way. In practice, finding some return lengths can identify a candidate common divisor, but a few paths alone do not establish the complete return-time set.

When There Is No Return, and a Common Mistake

The definition also has an important boundary case. For example, on \(S=\{1,2\}\), let \(P=\begin{bmatrix}0&1\\0&1\end{bmatrix}\). The row sums are \(0+1=1\) and \(0+1=1\). From state \(1\), the chain moves to \(2\) and stays there, so there is no directed path of positive length from \(1\) back to \(1\). Thus \(R_1\) is empty, and its greatest common divisor is not defined under the definition given here. Do not silently treat an absent return path as a return of length zero.

Common mistake: treating the transition graph as undirected. In the three-state directed cycle above, one might incorrectly claim there is a two-step return \(1\to2\to1\), by assuming that the edge \(1\to2\) can be followed backward. But the matrix entry \(p_{21}\) is \(0\), so \(2\to1\) is not an edge. The actual two-step path is \(1\to2\to3\), which ends at \(3\), not \(1\). The correction is to follow only directed edges: the first return from \(1\) has length three, and the return lengths are \(3,6,9,\ldots\).

The period is a feature of possible return timing, not of the probabilities’ exact magnitudes. Once an edge has positive probability, changing its value to another positive number does not remove the paths using it. Setting that transition probability to zero does remove those paths and may change the return-time set. For any graph-based calculation, first identify the positive-probability directed edges, then list or characterize the closed-walk lengths at the state in question. Use the whole return-time set in the definition; do not confuse it with just the length of one cycle or just the first-return lengths.