What a Period Counts
A state’s period is determined by the times at which the chain can return to that same state with positive probability. Small chains can make this calculation look deceptively simple: a return path may have several possible lengths, and an \(n\)-step return probability may combine multiple paths. The key is to count positive-probability returns, not the times when returns are impossible, and to follow paths back to the state rather than inspect its outgoing transitions in isolation.
Throughout, a discrete-time Markov chain \((X_n)_{n\ge0}\) is defined on a probability space \((\Omega,\mathcal F,\mathbb P)\), with a finite state space \(S\) and transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\). Write \(P^n=(p_{ij}^{(n)})\) for the \(n\)-step transition matrix.
The definition uses strict positivity. A possible path contributes to \(p_{ii}^{(n)}\) only if every transition on that path has positive probability. Conversely, \(p_{ii}^{(n)}>0\) if at least one length-\(n\) path from \(i\) back to \(i\) has positive probability. If there is no positive return time, \(R_i\) is empty and this greatest-common-divisor calculation does not assign a period.
Proof. Fix \(i\) and \(n\ge1\). Repeated use of the transition rule gives \(p_{ii}^{(n)}=\sum_{i_1,\ldots,i_{n-1}\in S}p_{ii_1}p_{i_1i_2}\cdots p_{i_{n-1}i}\), with the sum interpreted as \(p_{ii}\) when \(n=1\). Every summand is nonnegative. A summand is positive exactly when all the transitions in its corresponding path have positive probability. A finite sum of nonnegative numbers is positive exactly when at least one summand is positive. Thus \(p_{ii}^{(n)}>0\) exactly when at least one such return path exists. Taking the greatest common divisor over \(n\ge1\) proves the stated characterization. \(\square\)
This result justifies a useful calculation method: identify the positive-probability return-path lengths, then take their greatest common divisor. A path length is counted when it ends back at the starting state; an edge leaving that state is only the first part of a path.
Worked Calculations and the Errors They Prevent
Worked Example: Nonreturn Times Do Not Determine the Period
Consider a chain on \(S=\{a,b\}\), defined on a probability space \((\Omega,\mathcal F,\mathbb P)\), with transition matrix
Each row sums to \(1\): the first row is \(0+1=1\), and the second is \(1+0=1\). From \(a\), the chain alternates deterministically between \(a\) and \(b\). Hence \(p_{aa}^{(n)}=1\) for positive even \(n\), and \(p_{aa}^{(n)}=0\) for odd \(n\). In particular, the positive return times begin \(R_a=\{2,4,6,\ldots\}\), so \(d(a)=\gcd(2,4,6,\ldots)=2\).
Common mistake: taking the greatest common divisor of the times with no return gives \(\gcd(1,3,5,\ldots)=1\), and incorrectly suggests period \(1\). Those times are not in \(R_a\): their return probabilities are zero. The definition takes the gcd of positive return times, not nonreturn times.
Check: At time \(2\), the path \(a\to b\to a\) has probability \(1\), so \(p_{aa}^{(2)}=1>0\). At time \(3\), the chain is at \(b\) with probability \(1\), so \(p_{aa}^{(3)}=0\). These values agree with the even-return calculation.
Worked Example: Count Every Path Contributing to a Return Probability
Let \(S=\{a,b,c,d\}\), and use the transition matrix
Every row sums to \(1\): \(0+1+0+0=1\), \(\tfrac12+0+\tfrac12+0=1\), \(0+0+0+1=1\), and \(1+0+0+0=1\). Starting at \(a\), the first step must be to \(b\). From \(b\), the chain moves to \(a\) with probability \(\tfrac12\), or to \(c\) with probability \(\tfrac12\); from \(c\) it moves to \(d\), and from \(d\) to \(a\), each with probability \(1\).
There is a length-\(2\) return path \(a\to b\to a\), with probability \(1\cdot\tfrac12=\tfrac12\), so \(p_{aa}^{(2)}=\tfrac12\). At length \(4\), there are two distinct returning paths. The path \(a\to b\to a\to b\to a\) has probability \(1\cdot\tfrac12\cdot1\cdot\tfrac12=\tfrac14\). The path \(a\to b\to c\to d\to a\) has probability \(1\cdot\tfrac12\cdot1\cdot1=\tfrac12\). Adding both contributions gives
In particular, \(\tfrac12\) is the probability of the four-step path through \(c,d\), not the total four-step return probability. To find the period, partition the states as \(\{a,c\}\) and \(\{b,d\}\). Every positive-probability transition goes from one part to the other. A return to \(a\) must therefore take an even number of steps. Lengths \(2\) and \(4\) both occur, so the gcd of all possible return lengths divides both \(2\) and \(4\), while every return length is even. Thus \(d(a)=2\).
Check: The two paths listed exhaust the length-\(4\) possibilities: after the forced first step to \(b\), the second step either returns to \(a\), forcing \(b,a\) for the last two steps, or goes to \(c\), forcing \(d,a\). Their probabilities sum to \(\tfrac14+\tfrac12=\tfrac34\), as calculated.
Worked Example: Outgoing Choices Are Not Return Times
Consider a chain on \(S=\{a,b,c,d\}\), on a probability space \((\Omega,\mathcal F,\mathbb P)\), with transition matrix
The row sums are \(0+\tfrac12+\tfrac12+0=1\), \(1+0+0+0=1\), \(0+0+0+1=1\), and \(1+0+0+0=1\). From \(a\), there are two choices for the first step, but neither choice returns to \(a\) immediately: \(p_{aa}=0\). The path \(a\to b\to a\) returns in \(2\) steps and has probability \(\tfrac12\cdot1=\tfrac12\). The path \(a\to c\to d\to a\) returns in \(3\) steps and has probability \(\tfrac12\cdot1\cdot1=\tfrac12\). Therefore \(p_{aa}^{(2)}=\tfrac12>0\), \(p_{aa}^{(3)}=\tfrac12>0\), and \(d(a)=\gcd(2,3)=1\).
The outgoing probabilities \(\tfrac12,\tfrac12\) describe only the first step. They are not return probabilities and do not, by themselves, give return lengths. The return paths must be followed until they reach \(a\) again.
Check: There is no one-step return because the \(a,a\) matrix entry is \(0\). The two listed paths have different lengths \(2\) and \(3\), whose gcd is \(1\); thus a state can have two possible first steps and still have period \(1\).
Why Longer Paths and Concatenation Matter
Finding a few short return paths is often enough to settle the gcd, but it is important to know what that argument does and does not show. If two positive return lengths have gcd \(1\), the period is \(1\) immediately. If their gcd is \(d>1\), they do not by themselves prove that the period is \(d\): there may be another return path with a length not divisible by \(d\). The full return-time set, or a structural argument that constrains every return path, is needed.
Proof. Since \(m,n\in R_i\), \(p_{ii}^{(m)}>0\) and \(p_{ii}^{(n)}>0\). By the Chapman–Kolmogorov equation, \(p_{ii}^{(m+n)}=\sum_{j\in S}p_{ij}^{(m)}p_{ji}^{(n)}\). The term with \(j=i\) is \(p_{ii}^{(m)}p_{ii}^{(n)}>0\), and all other terms are nonnegative. Consequently \(p_{ii}^{(m+n)}>0\), so \(m+n\in R_i\). Equivalently, the two positive-probability return paths can be followed one after the other, with positive product probability. \(\square\)
This proposition explains why a return probability at a longer time may include several paths, including concatenations of shorter returns. It does not say that every possible path of a given length has the same probability, or that one path’s probability is the entire \(n\)-step return probability. The matrix-power formula sums the probabilities of all such paths.
A practical calculation can be organized as follows:
Confirm that each row of \(P\) sums to \(1\), then record only the directed edges with \(p_{ij}>0\).
Count a length \(n\) only when a positive-probability path starts at \(i\) and ends at \(i\).
If computing \(p_{ii}^{(n)}\), add the probabilities of every length-\(n\) path from \(i\) to \(i\).
Use lengths with strictly positive return probability, and justify any claim that rules out other lengths.
Common Pitfalls
The most frequent errors are variations on confusing a path with a return, or a particular path with the full transition probability:
- Using nonreturn times. A zero value of \(p_{ii}^{(n)}\) does not belong in \(R_i\). In the alternating two-state chain, odd times are nonreturns, while the positive return times are even.
- Stopping after one path. A path of length \(n\) gives one nonnegative contribution to \(p_{ii}^{(n)}\), not necessarily the whole probability. In the four-state example, both a repeated two-step path and a longer route contribute to \(p_{aa}^{(4)}\).
- Reading the answer from outgoing edges. The row indexed by \(i\) describes one step from \(i\). Period concerns complete paths that start and end at \(i\), so the path must be traced back.
- Inferring the gcd from too few lengths. Return lengths \(4\) and \(6\) have gcd \(2\), but that alone does not rule out a length-\(3\) return. Every claimed restriction on the gcd needs a reason that covers all possible return paths.
- Including time zero. Although \(p_{ii}^{(0)}=1\), the definition uses \(n\ge1\). Including \(0\) in the gcd would not define the intended period.
These checks are useful because period is a property of return behavior, not simply of the number of outgoing choices or the appearance of a transition matrix. A reliable calculation names the state, identifies positive return lengths, accounts for all paths when computing a return probability, and explains why omitted lengths cannot alter the gcd.
Check Your Understanding
For each question, distinguish positive return times from nonreturn times and show the path or probability calculation that supports your answer.
- In the two-state alternating chain, what are \(p_{aa}^{(1)}\), \(p_{aa}^{(2)}\), and \(d(a)\)? Which set of times must be used in the gcd?
- In the four-state example, list both length-\(4\) paths from \(a\) back to \(a\), and calculate their separate probabilities and their sum.
- In the last example, why does \(p_{aa}=0\) despite two possible outgoing transitions from \(a\)? What positive return lengths establish \(d(a)=1\)?
- If a state has positive return paths of lengths \(4\) and \(6\), what additional fact would be needed before concluding that its period is \(2\)?
- Explain why \(m,n\in R_i\) implies \(m+n\in R_i\), using the Chapman–Kolmogorov equation.