Return Probabilities from Matrix Powers
For a discrete-time Markov chain, the probability of being back at a chosen state after \(n\) steps is encoded directly in a transition-matrix power. This gives a systematic way to compute return probabilities at specific times. Examining their partial sums then connects those calculations to recurrence and transience. The key distinction is that being at a state at time \(n\) allows for earlier visits as well; it does not mean the first return occurs at time \(n\).
Let \((X_n)_{n\ge0}\) be a Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The entries are \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\), and each row sums to \(1\). Write \(P^{(n)}=P^n\), with entries \(p_{ij}^{(n)}\). Under \(\mathbb{P}_i\), the chain starts at \(i\); its return time is \(T_i^+=\inf\{n\ge1:X_n=i\}\).
The matrix-power calculation follows from the Chapman–Kolmogorov equations: to get from \(i\) to \(j\) in \(n+1\) steps, the chain must be at some intermediate state \(k\) after \(n\) steps and then move from \(k\) to \(j\). In particular, the diagonal entry sums the probabilities of all possible \(n\)-step paths that start and end at \(i\).
Proof. At \(n=1\), the assertion is the definition of \(p_{ij}\). Suppose \(p_{ik}^{(n)}=\mathbb{P}_i(X_n=k)\) for every \(k\). The events \(\{X_n=k\}\), \(k\in S\), partition the sample space, so conditioning on \(X_n\) gives \(\mathbb{P}_i(X_{n+1}=j)=\sum_{k\in S}\mathbb{P}_i(X_n=k)\mathbb{P}_i(X_{n+1}=j\mid X_n=k)\). By the Markov property, the conditional probability in the sum is \(p_{kj}\); substituting the induction hypothesis yields \(\mathbb{P}_i(X_{n+1}=j)=\sum_{k\in S}p_{ik}^{(n)}p_{kj}\). This is the \((i,j)\) entry of \(P^{n+1}\) by matrix multiplication. The countable sum is valid because its terms are nonnegative and their total is a probability. Induction proves the identity for every \(n\), and setting \(j=i\) gives the return-probability statement. \(\square\)
Why the Partial Sums Classify a State
The return-series criterion turns the sequence of diagonal entries into a classification tool. A finite partial sum is useful for calculation, but recurrence or transience is determined by whether the entire infinite series converges or diverges.
Proof. Let \(V=\sum_{n\ge0}\mathbf{1}_{\{X_n=i\}}\) be the total number of visits to \(i\), including the visit at time \(0\), when the chain starts at \(i\). Since the summands are nonnegative, taking expectations of the increasing finite partial sums gives \(\mathbb{E}_i[V]=\sum_{n\ge0}\mathbb{P}_i(X_n=i)=\sum_{n\ge0}p_{ii}^{(n)}\), where \(p_{ii}^{(0)}=1\).
Write \(f=\mathbb{P}_i(T_i^+<\infty)\). By the Markov property at successive return times, the probability of at least \(r\) returns is \(f^r\) for each integer \(r\ge1\): after each return, the probability of another return is again \(f\). This uses the standard strong Markov property for a discrete-time chain at stopping times. If \(f<1\), the number \(K=V-1\) of returns after time \(0\) therefore satisfies \(\mathbb{E}_i[K]=\sum_{r\ge1}\mathbb{P}_i(K\ge r)=\sum_{r\ge1}f^r=f/(1-f)\). Thus \(\mathbb{E}_i[V]=1/(1-f)<\infty\), and the return-probability series with its \(n=0\) term removed is finite. If \(f=1\), then \(\mathbb{P}_i(K\ge r)=1\) for every \(r\), so \(\mathbb{E}_i[K]=\sum_{r\ge1}1=\infty\). The series including its \(n=0\) term diverges, and removing that finite term does not change divergence. By definition, \(f=1\) means recurrent and \(f<1\) means transient. \(\square\)
In practice, calculate successive powers by multiplication and read the relevant diagonal entries. For a finite matrix, each multiplication is a finite sum. For a countable state space, matrix multiplication may involve an infinite sum, so the series identity remains valid but a finite matrix calculation may not be available. In either case, partial sums increase as more nonnegative terms are added. A large partial sum is not, by itself, proof that the limit is infinite.
Worked Example: A Chain That Returns Only at Even Times
Consider a chain on \(S=\{1,2,3\}\) with transition matrix
Each row sums to \(1\): the three row sums are \(0+1+0=1\), \(\tfrac12+0+\tfrac12=1\), and \(0+1+0=1\). Starting from state \(1\), multiply rows by columns to obtain
For example, the \((1,1)\) entry of \(P^2\) is \(0\cdot0+1\cdot\tfrac12+0\cdot0=\tfrac12\); its \((1,3)\) entry is \(0\cdot0+1\cdot\tfrac12+0\cdot0=\tfrac12\). The middle row of \(P^2\) is \((\tfrac12,0,\tfrac12)\), and the third row is \((\tfrac12,0,\tfrac12)\). Multiplying \(P^2P\) gives \(P^3=P\); for instance, its first row is \((\tfrac12,0,\tfrac12)P=(0,1,0)\). Since \(P^3=P\), successive powers alternate: \(P^{2k}=P^2\) and \(P^{2k+1}=P\) for \(k\ge1\). Thus \(p_{11}^{(2k)}=\tfrac12\) and \(p_{11}^{(2k+1)}=0\). The partial sum through time \(2m\) is \(\sum_{n=1}^{2m}p_{11}^{(n)}=m/2\), which diverges as \(m\) increases. The return-series criterion classifies state \(1\) as recurrent. The same computation gives \(p_{22}^{(2k)}=1\) and \(p_{22}^{(2k+1)}=0\), so the return series at state \(2\) also diverges.
Worked Example: A Transient State with a Geometric Return Series
On \(S=\{1,2\}\), let
The row sums are \(\tfrac12+\tfrac12=1\) and \(0+1=1\), so this is a transition matrix. State \(2\) is absorbing. For \(n\ge1\), the powers are
For \(n=1\), this gives the displayed \(P\). If the formula holds at \(n\), the upper-left entry of \(P^nP\) is \(2^{-n}\cdot\tfrac12+(1-2^{-n})\cdot0=2^{-(n+1)}\), and the upper-right entry is \(2^{-n}\cdot\tfrac12+(1-2^{-n})\cdot1=1-2^{-(n+1)}\). The bottom row remains \((0,1)\). This proves the formula by induction; its rows sum to \(2^{-n}+1-2^{-n}=1\) and \(0+1=1\).
Starting at state \(1\), \(p_{11}^{(n)}=2^{-n}\), since the chain must stay at \(1\) at every one of the \(n\) steps. The partial sum through time \(N\) is \(\sum_{n=1}^N2^{-n}=1-2^{-N}\): multiplying the sum by \(2\) and subtracting the original sum gives \(1-2^{-N}\). Its limit is \(1\), so the return series is finite and state \(1\) is transient. In contrast, \(p_{22}^{(n)}=1\) at every \(n\ge1\), and state \(2\) is recurrent. A single chain can therefore contain states of different recurrence types.
Worked Example: Identical Transition Rows
Consider \(S=\{1,2,3\}\) and
Each row sums to \(\tfrac12+\tfrac13+\tfrac16=1\). Every row of \(P^2\) is the row vector \((\tfrac12,\tfrac13,\tfrac16)P\). Its entries are \(\tfrac12\cdot\tfrac12+\tfrac13\cdot\tfrac12+\tfrac16\cdot\tfrac12=\tfrac12\), \(\tfrac12\cdot\tfrac13+\tfrac13\cdot\tfrac13+\tfrac16\cdot\tfrac13=\tfrac13\), and \(\tfrac12\cdot\tfrac16+\tfrac13\cdot\tfrac16+\tfrac16\cdot\tfrac16=\tfrac16\). Hence \(P^2=P\), and multiplying by \(P\) again shows \(P^n=P\) for every \(n\ge1\).
The diagonal entries are therefore \(p_{11}^{(n)}=\tfrac12\), \(p_{22}^{(n)}=\tfrac13\), and \(p_{33}^{(n)}=\tfrac16\) for every \(n\ge1\). Their partial sums through time \(N\) are respectively \(N/2\), \(N/3\), and \(N/6\), each of which diverges as \(N\) increases. The return-series criterion classifies all three states as recurrent. As a check, at time \(1\) the diagonal entries of the displayed matrix are exactly \(\tfrac12,\tfrac13,\tfrac16\), and the identity \(P^n=P\) confirms that these values persist at every positive time.
Common Pitfall: Confusing a Return with a First Return
The entry \(p_{ii}^{(n)}\) asks whether the chain is at \(i\) at time \(n\). It does not ask whether time \(n\) is the first time it has returned. For a concrete check, take \(S=\{1,2\}\) and \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\). Both row sums are \(1\), and \(P^2=I\), so \(P^4=I\) and \(p_{11}^{(4)}=1\). It would be wrong to conclude that the first return occurs at time \(4\) with probability \(1\): the chain follows \(1,2,1,2,1\), so its first return is at time \(2\). In fact, \(\mathbb{P}_1(T_1^+=4)=0\), even though \(p_{11}^{(4)}=1\). A diagonal entry counts all paths ending at the state at the specified time, including those that returned earlier.
Another important limitation is that any finite collection of return probabilities gives only a partial sum. The return-series criterion is an infinite-series test; observing several positive terms or a growing partial sum does not prove divergence. To establish recurrence from calculations, one needs an argument valid for arbitrarily large \(N\), such as an exact formula showing that partial sums grow without bound. To establish transience, one needs a finite bound on the full series, not merely a finite computed sum.
Check Your Understanding
Use matrix powers and the return-series criterion where appropriate. State whether each claim concerns a return probability at a specified time or a first-return probability.
- For \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\), calculate \(p_{11}^{(1)},p_{11}^{(2)},p_{11}^{(3)}\), and \(p_{11}^{(4)}\). What is \(\mathbb{P}_1(T_1^+=4)\)?
- For the two-state chain in the transient example, calculate the partial sum \(\sum_{n=1}^{3}p_{11}^{(n)}\). Does this finite sum alone classify state \(1\)?
- Suppose \(P^2=P\) and \(p_{ii}=\tfrac14\). What are \(p_{ii}^{(n)}\) and the partial sum through time \(N\), for \(N\ge1\)?
- Explain why the diagonal entries of \(P^n\) are return probabilities rather than first-return probabilities.
- State the return-series criterion for recurrence and transience, including which term of the series corresponds to time \(0\).