Choosing a Method to Compute P to the nth Power

Three Ways to Compute an n-Step Transition Matrix

For a Markov chain, the probability of moving from state \(i\) to state \(j\) in \(n\) steps is the entry \(p_{ij}^{(n)}\) of its n-step transition matrix \(P^{(n)}=P^n\). There is no single best way to compute this power in every problem. A small \(n\) often makes a path calculation shortest; repeated multiplication gives a dependable method for moderate \(n\); and diagonalization can make a very large power manageable when the matrix has a suitable eigenstructure. The aim here is to choose among these methods, keep the arithmetic verifiable, and recognize when a method does not apply.

Throughout, \((X_n)_{n\ge0}\) is a discrete-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal F,\mathbb P)\). Its transition matrix \(P=(p_{ij})\) is row-stochastic, and \(p_{ij}^{(n)}=\mathbb P_i(X_n=j)\). In particular, \(P^{(0)}=I\). Chapman–Kolmogorov gives \(P^{(m+n)}=P^mP^n\); equivalently, the distribution row vector evolves by \(\mu_{n+1}=\mu_nP\). These identities let us compute the same quantities in different ways.

Why the Three Methods Work

A path of length \(n\) from \(i\) to \(j\) is a sequence \(i=i_0,i_1,\ldots,i_n=j\) of states. Its probability, conditional on starting at \(i\), is the product of the transition probabilities along that path. Summing over all such paths gives the n-step probability.

Proof. For \(n=1\), the displayed sum has no intermediate states and consists of \(p_{ij}\), as required. Suppose the formula holds for \(n\). Chapman–Kolmogorov gives \(p_{ij}^{(n+1)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj}\). Substitute the length-\(n\) path expansion for each \(p_{ik}^{(n)}\). Each term then corresponds to a length-\((n+1)\) path whose penultimate state is \(k\), and its product includes the final factor \(p_{kj}\). As \(k\) ranges over \(S\), these are exactly all length-\((n+1)\) paths, each counted once. For \(n=0\), the chain is in its starting state with probability one and in any different state with probability zero, which is the identity matrix. \(\square\)

Recursive multiplication is the same combination of intermediate states written as matrix arithmetic. Compute \(P^{(0)}=I\), then \(P^{(r+1)}=P^{(r)}P\). In each matrix product, the entry for \(i,j\) is \(\sum_k p_{ik}^{(r)}p_{kj}\), precisely the final-step conditioning in Chapman–Kolmogorov. A second route to a large power is to express a diagonalizable matrix as \(P=V D V^{-1}\), where \(D\) is diagonal.

Proof. For \(n=0\), \(P^0=I=VIV^{-1}=VD^0V^{-1}\). For \(n\ge1\), multiply \(P=VDV^{-1}\) by itself \(n\) times. Each adjacent factor \(V^{-1}V\) equals \(I\), leaving \(V D^n V^{-1}\). This proves the formula for every nonnegative integer \(n\). \(\square\)

This identity does not say that every matrix can be diagonalized. If \(P\) has too few linearly independent eigenvectors, this route is unavailable; recursive multiplication remains valid. The following examples show how the choice affects the work.

Choosing Efficiently—and Avoiding a Common Error

For a small exponent and a single requested entry, path enumeration may avoid calculating entries that are not needed. Its cost grows with the number of possible paths, however: if every state can transition to every state, there can be \(|S|^{n-1}\) intermediate-state sequences for one entry. Recursive multiplication organizes those sums systematically and is usually clearer when several entries are required. For a very large exponent, diagonalization can replace many multiplications by raising eigenvalues to the \(n\)th power, but only if a full eigenvector basis exists and the resulting arithmetic is manageable. The result must still be checked against the probability structure.

Common mistake: adding transition probabilities along a path. In the first example, the path \(1\to2\to3\) has probability \(\tfrac12+\tfrac12=1\) if its two transition probabilities are incorrectly added. The probability of the path is instead their product, \(\tfrac12\cdot\tfrac12=\tfrac14\), because both transitions must occur. Then probabilities of distinct paths are added. For \(p_{13}^{(2)}\), the only positive-probability path contributes \(\tfrac14\), not \(1\).

Another limitation is that diagonalization is not guaranteed. For example, consider the matrix below on \(S=\{1,2,3\}\), where \((X_n)\) is again a discrete-time chain on a probability space:

Its row sums are \(1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(\tfrac12+0+\tfrac12=1\). The characteristic polynomial is \((1-\lambda)(\tfrac12-\lambda)^2\). For eigenvalue \(\tfrac12\), the equation \((R-\tfrac12I)x=0\) forces \(x_1=0\) from the first row and \(x_3=0\) from the second row; \(x_2\) is free. Thus this eigenvalue has only one linearly independent eigenvector, despite having algebraic multiplicity two, so \(R\) is not diagonalizable. Do not force the diagonalization method in this case; recursive multiplication is still justified by Chapman–Kolmogorov.

For any computed power, row sums provide a basic check: if \(P\) is row-stochastic, then \(P^n\) is row-stochastic for every \(n\ge0\). Indeed, if a row vector \(x\) has nonnegative entries summing to one, then the \(i\)th row of \(P^{n+1}=P^nP\) is a nonnegative weighted sum of rows of \(P\), with weights from row \(i\) of \(P^n\); those weights sum to one, so the resulting row also sums to one. This check detects many arithmetic errors, though it does not by itself verify every entry.