Extracting n-Step Probabilities from Eigenvectors

From a Matrix Power to One Transition Probability

A diagonalization can make $P^n$ compact, but many questions ask for one entry: the probability of moving from a particular state $i$ to a particular state $j$ in exactly $n$ steps. To extract that entry correctly, it matters which eigenvector coordinates belong to the starting state and which inverse-matrix coordinates belong to the destination. Their products, together with the corresponding eigenvalue powers, give the answer.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, and let $(X_n)_{n\ge0}$ be a discrete-time Markov chain with finite state space $S=\{1,\ldots,m\}$. Its transition matrix $P=(p_{ij})$ is row-stochastic, meaning $p_{ij}\ge0$ and each row sums to $1$. The filtration is $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. The $n$-step transition probability is $p_{ij}^{(n)}=\mathbb{P}(X_n=j\mid X_0=i)$, and the Chapman–Kolmogorov equations give $P^{(n)}=P^n$.

Definition: Suppose $P$ is diagonalizable, so $P=VDV^{-1}$, where $D=\operatorname{diag}(\lambda_1,\ldots,\lambda_m)$, the columns of $V$ are right eigenvectors $v_1,\ldots,v_m$, and $V$ is invertible. Then, for states $i,j$ and integer $n\ge0$,\n$$ p_{ij}^{(n)}=(P^n)_{ij}=\sum_{r=1}^{m}V_{ir}\lambda_r^n(V^{-1})_{rj}. $$\nHere $V_{ir}$ is coordinate $i$ of eigenvector $v_r$, while $(V^{-1})_{rj}$ is entry $j$ of row $r$ of the inverse matrix. At $n=0$, use $D^0=I$, so the formula means $\lambda_r^0=1$, including when $\lambda_r=0$.

The formula separates the contribution to a transition probability into three parts: the eigenvector’s coordinate at the starting state, the eigenvalue raised to the number of steps, and the inverse-matrix coordinate at the destination. The rows of $V^{-1}$ are the left-coordinate functionals dual to the columns of $V$. Thus the formula is not generally obtained by multiplying two eigenvector coordinates or by using the same eigenvector at both states.

Why the Entry Formula Works

Theorem: If $P=VDV^{-1}$, then for every integer $n\ge0$, the entry of $P^n$ in row $i$, column $j$ is $\sum_{r=1}^{m}V_{ir}\lambda_r^n(V^{-1})_{rj}$.

Proof. For $n\ge0$, multiplying $P=VDV^{-1}$ repeatedly and using $V^{-1}V=I$ gives $P^n=VD^nV^{-1}$; when $n=0$, both sides equal $I$. The $(i,j)$ entry of a product of three matrices is the sum over the two intermediate indices. Since $D^n$ is diagonal, its $(r,s)$ entry is zero unless $r=s$, and its $(r,r)$ entry is $\lambda_r^n$. Therefore $$ (P^n)_{ij}=\sum_{r=1}^{m}\sum_{s=1}^{m}V_{ir}(D^n)_{rs}(V^{-1})_{sj} =\sum_{r=1}^{m}V_{ir}\lambda_r^n(V^{-1})_{rj}. $$ This is the stated formula. $\square$

A repeated eigenvalue does not make the entry formula ambiguous. Different bases for the same eigenspace may change the individual coordinates, but not the total contribution of that eigenspace.

Proposition: The contribution to $P^n$ from an eigenspace with eigenvalue $\lambda$ is independent of the chosen basis of that eigenspace.

Proof. Group the columns of $V$ for this eigenspace into a matrix $V_\lambda$, and group the corresponding rows of $V^{-1}$ into a matrix $W_\lambda$. The eigenspace’s contribution is $\lambda^n V_\lambda W_\lambda$. If its basis is changed by an invertible matrix $C$, the new columns are $V_\lambda C$. To preserve the identity $VV^{-1}=I$, the corresponding inverse rows become $C^{-1}W_\lambda$. The new contribution is $$ \lambda^n(V_\lambda C)(C^{-1}W_\lambda) =\lambda^n V_\lambda(CC^{-1})W_\lambda =\lambda^n V_\lambda W_\lambda. $$ Thus the contribution is unchanged. This argument also applies at $n=0$, when $\lambda^0=1$. $\square$

Worked Examples

Worked Example: Extracting an Entry from a Three-State Diagonalization

Consider the transition matrix on $S=\{1,2,3\}$ $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac14&\tfrac12&\tfrac14\\ 0&\tfrac12&\tfrac12 \end{bmatrix}. $$ Its rows sum to $\tfrac12+\tfrac12+0=1$, $\tfrac14+\tfrac12+\tfrac14=1$, and $0+\tfrac12+\tfrac12=1$. Right eigenvectors are $v_1=(1,1,1)^{\mathsf T}$, $v_2=(1,0,-1)^{\mathsf T}$, and $v_3=(1,-1,1)^{\mathsf T}$, with eigenvalues $1,\tfrac12,0$, respectively. For example, multiplying $P$ by $v_2$ gives $(\tfrac12,0,-\tfrac12)^{\mathsf T}=\tfrac12v_2$, and multiplying by $v_3$ gives the zero vector.

With these columns, $$ V=\begin{bmatrix}1&1&1\\1&0&-1\\1&-1&1\end{bmatrix}, \qquad V^{-1}=\begin{bmatrix} \tfrac14&\tfrac12&\tfrac14\\ \tfrac12&0&-\tfrac12\\ \tfrac14&-\tfrac12&\tfrac14 \end{bmatrix}. $$ For instance, the first row of $V^{-1}$ gives $a=\tfrac14x_1+\tfrac12x_2+\tfrac14x_3$, and the other two give $b=\tfrac12(x_1-x_3)$ and $c=\tfrac14(x_1+x_3)-\tfrac12x_2$, so $V^{-1}V=I$.

Find $p_{13}^{(2)}$. Row 1 of $V$ is $(1,1,1)$, and column 3 of $V^{-1}$ is $(\tfrac14,-\tfrac12,\tfrac14)^{\mathsf T}$. Therefore $$ p_{13}^{(2)} =1\cdot1^2\cdot\tfrac14 +1\cdot(\tfrac12)^2\cdot(-\tfrac12) +1\cdot0^2\cdot\tfrac14 =\tfrac14-\tfrac18+0 =\tfrac18. $$ Check: column 3 of $P$ is $(0,\tfrac14,\tfrac12)^{\mathsf T}$. Row 1 of $P$ dotted with that column gives $\tfrac12\cdot0+\tfrac12\cdot\tfrac14+0\cdot\tfrac12=\tfrac18$, agreeing with the eigenvector calculation.

Worked Example: A Sign Check for a Two-Step Probability

On $S=\{1,2,3\}$, take $$ P=\begin{bmatrix} 1&0&0\\ 0&\tfrac14&\tfrac34\\ 0&0&1 \end{bmatrix}. $$ The row sums are $1+0+0=1$, $0+\tfrac14+\tfrac34=1$, and $0+0+1=1$. Use the eigenvectors $v_1=(1,0,0)^{\mathsf T}$, $v_2=(0,1,1)^{\mathsf T}$, and $v_3=(0,1,0)^{\mathsf T}$. Their eigenvalues are $1,1,\tfrac14$: in particular, $Pv_2=v_2$ and $Pv_3=\tfrac14v_3$.

The resulting matrices and inverse are $$ V=\begin{bmatrix}1&0&0\\0&1&1\\0&1&0\end{bmatrix}, \qquad D=\operatorname{diag}(1,1,\tfrac14), \qquad V^{-1}=\begin{bmatrix}1&0&0\\0&0&1\\0&1&-1\end{bmatrix}. $$ For the entry $p_{23}^{(n)}$, row 2 of $V$ is $(0,1,1)$ and column 3 of $V^{-1}$ is $(0,1,-1)^{\mathsf T}$. Hence, for $n\ge1$, $$ p_{23}^{(n)} =0\cdot1^n\cdot0 +1\cdot1^n\cdot1 +1\cdot(\tfrac14)^n\cdot(-1) =0+1-(\tfrac14)^n =1-(\tfrac14)^n. $$ At $n=2$, this is $1-\tfrac1{16}=\tfrac{15}{16}$.

Check: From state 2, after two steps the chain is in state 3 either by going directly there and then remaining there, with probability $\tfrac34\cdot1$, or by staying in state 2 and then moving to state 3, with probability $\tfrac14\cdot\tfrac34$. The sum is $\tfrac34+\tfrac3{16}=\tfrac{12}{16}+\tfrac3{16}=\tfrac{15}{16}$. The sign matters: replacing the negative final term by a positive one would give $\tfrac{17}{16}$, which cannot be a probability and does not match the direct calculation.

Worked Example: A Repeated Eigenvalue and All Entries at Once

Consider the three-state matrix with diagonal entries $\tfrac23$ and off-diagonal entries $\tfrac16$: $$ P=\begin{bmatrix} \tfrac23&\tfrac16&\tfrac16\\ \tfrac16&\tfrac23&\tfrac16\\ \tfrac16&\tfrac16&\tfrac23 \end{bmatrix}. $$ Each row sums to $\tfrac23+\tfrac16+\tfrac16=1$. The vector $\mathbf{1}=(1,1,1)^{\mathsf T}$ has eigenvalue $1$. Every vector $x$ whose coordinates sum to zero has eigenvalue $\tfrac12$, since $P=\tfrac12I+\tfrac16\mathbf{1}\mathbf{1}^{\mathsf T}$ and $\mathbf{1}\mathbf{1}^{\mathsf T}x=0$. Thus the eigenvalue $\tfrac12$ has a two-dimensional eigenspace.

The projection onto the span of $\mathbf{1}$ is $J/3$, where $J=\mathbf{1}\mathbf{1}^{\mathsf T}$; the projection onto the sum-zero subspace is $I-J/3$. Applying the eigenvalues to these two parts gives $$ P^n=\frac{J}{3}+(\tfrac12)^n\left(I-\frac{J}{3}\right). $$ For a diagonal entry, this yields $\tfrac13+(\tfrac12)^n(\tfrac23)$; for an off-diagonal entry, it yields $\tfrac13-(\tfrac12)^n(\tfrac13)$. At $n=2$, the diagonal entries are $\tfrac13+\tfrac14\cdot\tfrac23=\tfrac13+\tfrac16=\tfrac12$, and the off-diagonal entries are $\tfrac13-\tfrac14\cdot\tfrac13=\tfrac13-\tfrac1{12}=\tfrac14$.

Check: The $(1,1)$ entry of $P^2$ is $(\tfrac23)^2+(\tfrac16)^2+(\tfrac16)^2=\tfrac49+\tfrac1{36}+\tfrac1{36}=\tfrac12$. The $(1,2)$ entry is $\tfrac23\cdot\tfrac16+\tfrac16\cdot\tfrac23+\tfrac16\cdot\tfrac16=\tfrac2{18}+\tfrac2{18}+\tfrac1{36}=\tfrac14$. These checks also show that each row of $P^2$ sums to $\tfrac12+\tfrac14+\tfrac14=1$.

Reading and Checking the Formula

For a fixed pair $i,j$, each eigenvalue contributes a term of the form $c_r\lambda_r^n$, where $c_r=V_{ir}(V^{-1})_{rj}$. The coefficients may be negative even though the final transition probability cannot be negative. Cancellation between terms is part of the calculation, as the second example demonstrates. An eigenvalue of zero contributes zero for $n\ge1$, but contributes according to $D^0=I$ when $n=0$; the formula must still return $p_{ij}^{(0)}=1$ if $i=j$ and $0$ otherwise.

The formula requires an actual diagonalization: $V$ must be invertible and its columns must be a full eigenvector basis. If a matrix is not diagonalizable, this particular formula cannot be applied as written. Also, an eigenvalue’s contribution is not itself a probability. The probability is the sum of all the contributions for the specified starting and destination states.

Common mistake. A frequent error is to use the right eigenvector coordinate at the destination instead of the entry in the corresponding row of $V^{-1}$, or to lose a minus sign in that inverse. In the second example, the three terms for $p_{23}^{(n)}$ are $0$, $1$, and $-(\tfrac14)^n$, so the result is $1-(\tfrac14)^n$, not $1+(\tfrac14)^n$. A reliable check is to compute $P^n$ directly for one small $n$ and compare the selected entry, while also confirming that the answer lies between $0$ and $1$.

Check Your Understanding

Use the entry formula and verify at least one answer by direct multiplication.

In the first worked example, compute $p_{31}^{(2)}$ from the displayed eigenvectors and inverse matrix.
In the second example, evaluate $p_{23}^{(1)}$ and compare it with the corresponding entry of $P$.
Explain why the inverse matrix appears in the formula for $p_{ij}^{(n)}$, rather than a second copy of $V$.
For the repeated-eigenvalue example, find the diagonal and off-diagonal entries of $P^3$.
What does the entry formula give at $n=0$, and why must zero eigenvalues be handled using $D^0=I$?

Extracting n-Step Probabilities from Eigenvectors

What You'll Learn