From One-Step Transitions to Any Number of Steps
A transition matrix records the probabilities of moving between states in one step. For a two-state chain, diagonalization makes it possible to calculate the probabilities after \(k\) steps without multiplying the transition matrix by itself \(k\) times. The key is that one eigenvector describes the stationary distribution, while a second eigenvector describes how the difference from stationarity changes at each step.
We use column probability vectors: the entry in position \(i\) is the probability of being in state \(i\). Accordingly, the entry in row \(i\), column \(j\) of a transition matrix is the probability of moving from state \(j\) to state \(i\). Each column therefore sums to \(1\). Write the probability of moving from state 1 to state 1 as \(r\), and from state 2 to state 1 as \(s\). Then \(0\le r,s\le1\), and the transition matrix and a starting distribution have the form
After \(k\) steps, the distribution is \(\mathbf{x}_k=\mathbf{P}^k\mathbf{x}_0\), where \(k\) is a nonnegative integer and \(\mathbf{P}^0=\mathbf{I}_2\). The second eigenvalue that controls the iteration is \(\lambda=r-s\). The other eigenvalue is \(1\), corresponding to a stationary distribution.
Why the Formula Follows from Diagonalization
Proof. A stationary distribution is a probability vector \(\boldsymbol{\pi}\) satisfying \(\mathbf{P}\boldsymbol{\pi}=\boldsymbol{\pi}\). Write its first entry as \(q\), so its second entry is \(1-q\). The first entry of \(\mathbf{P}(q,1-q)^{\top}\) is \(rq+s(1-q)\). Thus stationarity requires $$ q=rq+s(1-q), \qquad (1-r+s)q=s. $$ If \(d>0\), this equation has the unique solution \(q=s/d\). Its second entry is \(1-q=(1-r)/d\), and both entries are nonnegative and sum to \(1\). Direct substitution confirms stationarity: the first entry after multiplication by \(\mathbf{P}\) is $$ r\frac{s}{d}+s\frac{1-r}{d}=\frac{s}{d}, $$ and the second entry is \(1-s/d=(1-r)/d\).
Let \(\mathbf{v}_1=\boldsymbol{\pi}\) and \(\mathbf{v}_2=(1,-1)^{\top}\). We have \(\mathbf{P}\mathbf{v}_1=\mathbf{v}_1\). For the second vector, direct multiplication gives $$ \mathbf{P}\mathbf{v}_2= \begin{bmatrix} r-s\\ s-r \end{bmatrix} =\lambda\mathbf{v}_2. $$ The vectors are linearly independent: the entries of \(\mathbf{v}_1\) sum to \(1\), whereas those of \(\mathbf{v}_2\) sum to \(0\), so neither is a scalar multiple of the other. Put these eigenvectors into the columns of \(\mathbf{S}\). Then $$ \mathbf{S}= \begin{bmatrix} q&1\\ 1-q&-1 \end{bmatrix}, \qquad \mathbf{S}^{-1}= \begin{bmatrix} 1&1\\ 1-q&-q \end{bmatrix}, \qquad \mathbf{P}=\mathbf{S} \begin{bmatrix} 1&0\\ 0&\lambda \end{bmatrix} \mathbf{S}^{-1}. $$ The displayed inverse is verified by multiplying it by \(\mathbf{S}\) in either order. Since \(\mathbf{P}\mathbf{S}=\mathbf{S}\operatorname{diag}(1,\lambda)\), multiplying on the right by \(\mathbf{S}^{-1}\) gives the diagonalization.
For any \(k\ge0\), taking the \(k\)th power gives \(\mathbf{P}^k=\mathbf{S}\operatorname{diag}(1,\lambda^k)\mathbf{S}^{-1}\). The first coordinate of \(\mathbf{S}^{-1}\mathbf{x}_0\) is \(u+(1-u)=1\); its second is \((1-q)u-q(1-u)=u-q\). Consequently, $$ \mathbf{x}_k=\mathbf{v}_1+\lambda^k(u-q)\mathbf{v}_2 =\boldsymbol{\pi}+\lambda^k(\mathbf{x}_0-\boldsymbol{\pi}), $$ because \(\mathbf{x}_0-\boldsymbol{\pi}=(u-q)(1,-1)^{\top}\).
It remains to check the exceptional cases and the limit claim. Since \(r,s\in[0,1]\), \(d=0\) forces \(r=1\) and \(s=0\), which makes \(\mathbf{P}=\mathbf{I}_2\). If \(d>0\), then \(\lambda<1\) and \(\lambda\ge-1\). When \(|\lambda|<1\), \(\lambda^k\) tends to zero, so the formula tends to \(\boldsymbol{\pi}\). When \(\lambda=-1\), the difference from \(\boldsymbol{\pi}\) alternates sign; it tends to zero only if it was zero initially, that is, only if \(\mathbf{x}_0=\boldsymbol{\pi}\). This proves all the claims. \(\square\)
Worked Examples
Worked Example: A Symmetric Chain
Consider $$ \mathbf{P}= \begin{bmatrix} \frac34&\frac14\\ \frac14&\frac34 \end{bmatrix}, \qquad \mathbf{x}_0= \begin{bmatrix} 1\\0 \end{bmatrix}. $$ Here \(r=3/4\), \(s=1/4\), \(d=1/2\), and \(\lambda=1/2\). The stationary distribution is \(\boldsymbol{\pi}=(1/2,1/2)^{\top}\). Using \(\mathbf{v}_1=(1/2,1/2)^{\top}\) and \(\mathbf{v}_2=(1,-1)^{\top}\), the eigenvector matrix and its inverse are $$ \mathbf{S}= \begin{bmatrix} \frac12&1\\ \frac12&-1 \end{bmatrix}, \qquad \mathbf{S}^{-1}= \begin{bmatrix} 1&1\\ \frac12&-\frac12 \end{bmatrix}. $$ Indeed, multiplying \(\mathbf{P}\) by the first column of \(\mathbf{S}\) returns that column, and multiplying by the second returns half that column. Therefore $$ \mathbf{x}_k= \begin{bmatrix} \frac12\\ \frac12 \end{bmatrix} +\left(\frac12\right)^k \begin{bmatrix} \frac12\\ -\frac12 \end{bmatrix}. $$ For example, at \(k=2\), this gives \(\mathbf{x}_2=(5/8,3/8)^{\top}\). To check by multiplication, \(\mathbf{P}\mathbf{x}_0=(3/4,1/4)^{\top}\), and then $$ \mathbf{P} \begin{bmatrix} \frac34\\ \frac14 \end{bmatrix} = \begin{bmatrix} \frac{9}{16}+\frac{1}{16}\\ \frac{3}{16}+\frac{3}{16} \end{bmatrix} = \begin{bmatrix} \frac58\\ \frac38 \end{bmatrix}. $$ The formula agrees with the direct two-step calculation.
Worked Example: An Asymmetric Chain from State 2
Let $$ \mathbf{P}= \begin{bmatrix} \frac34&\frac12\\ \frac14&\frac12 \end{bmatrix}, \qquad \mathbf{x}_0= \begin{bmatrix} 0\\1 \end{bmatrix}. $$ Here \(r=3/4\), \(s=1/2\), so \(d=3/4\), \(\lambda=1/4\), and \(\boldsymbol{\pi}=(2/3,1/3)^{\top}\). The exact iteration formula is $$ \mathbf{x}_k= \begin{bmatrix} \frac23\\ \frac13 \end{bmatrix} -\left(\frac14\right)^k \begin{bmatrix} \frac23\\ -\frac23 \end{bmatrix}. $$ At \(k=1\), this gives \((1/2,1/2)^{\top}\). Direct multiplication confirms the result: $$ \mathbf{P}\mathbf{x}_0= \begin{bmatrix} \frac34&\frac12\\ \frac14&\frac12 \end{bmatrix} \begin{bmatrix} 0\\1 \end{bmatrix} = \begin{bmatrix} \frac12\\ \frac12 \end{bmatrix}. $$ At \(k=2\), the formula gives \((5/8,3/8)^{\top}\), since \(2/3-1/6=1/2\) for \(k=1\), and \(2/3-1/24=5/8\) for \(k=2\). Multiplying the one-step distribution gives the same check: $$ \mathbf{P} \begin{bmatrix} \frac12\\ \frac12 \end{bmatrix} = \begin{bmatrix} \frac38+\frac14\\ \frac18+\frac14 \end{bmatrix} = \begin{bmatrix} \frac58\\ \frac38 \end{bmatrix}. $$ The factor \(1/4\) shows how quickly the difference from stationarity shrinks at each step.
Worked Example: Identity and Alternation
Two boundary cases show why the limit condition matters. First, take \(\mathbf{P}=\mathbf{I}_2\). Then \(r=1\), \(s=0\), \(d=0\), and every distribution stays exactly where it starts. For \(\mathbf{x}_0=(1,0)^{\top}\), multiplication gives \(\mathbf{P}\mathbf{x}_0=(1,0)^{\top}\), and hence every iterate is \((1,0)^{\top}\).
Now take the state-switching matrix $$ \mathbf{P}= \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}. $$ Here \(r=0\), \(s=1\), \(\lambda=-1\), and the stationary distribution is \(\boldsymbol{\pi}=(1/2,1/2)^{\top}\). Starting from \(\mathbf{x}_0=(1,0)^{\top}\), the formula gives $$ \mathbf{x}_k= \begin{bmatrix} \frac12\\ \frac12 \end{bmatrix} +(-1)^k \begin{bmatrix} \frac12\\ -\frac12 \end{bmatrix}. $$ For even \(k\) this is \((1,0)^{\top}\); for odd \(k\) it is \((0,1)^{\top}\). Directly, \(\mathbf{P}(1,0)^{\top}=(0,1)^{\top}\) and \(\mathbf{P}(0,1)^{\top}=(1,0)^{\top}\), verifying the alternation. The iterates do not converge for this starting distribution, although the stationary distribution exists. If instead \(\mathbf{x}_0=\boldsymbol{\pi}\), then \(\mathbf{P}\mathbf{x}_0=\boldsymbol{\pi}\), so the iterates are constant.
Common Pitfall: Mixing Up Row and Column Conventions
With the column convention, one-step evolution is \(\mathbf{x}_1=\mathbf{P}\mathbf{x}_0\), not \(\mathbf{x}_0^{\top}\mathbf{P}\). For the asymmetric matrix in the previous example, starting from state 1 means \(\mathbf{x}_0=(1,0)^{\top}\). The correct calculation is $$ \mathbf{P}\mathbf{x}_0= \begin{bmatrix} \frac34\\ \frac14 \end{bmatrix}, $$ which is a probability vector. A mistaken row-vector calculation gives $$ \mathbf{x}_0^{\top}\mathbf{P}= \begin{bmatrix} \frac34&\frac12 \end{bmatrix}. $$ Its entries sum to \(5/4\), not \(1\), so it cannot be the distribution after one step. Always check both the multiplication order and that the entries of the resulting probability vector sum to \(1\).
The diagonalization formula is useful because it separates the persistent part of the distribution from the part that changes with \(k\). When \(|\lambda|<1\), the stationary component remains and the other component decays by the factor \(\lambda\) at every step. The sign and size of that factor are visible in the exact formula, while the boundary examples show why having a stationary distribution alone does not guarantee convergence from every starting state.
Check Your Understanding
Use the column-probability convention and give exact answers.
- For \(\mathbf{P}=\begin{bmatrix}2/3&1/3\\1/3&2/3\end{bmatrix}\), find \(\lambda\), the stationary distribution, and the distribution after \(k\) steps from \((1,0)^{\top}\).
- For \(\mathbf{P}=\begin{bmatrix}1/2&1/4\\1/2&3/4\end{bmatrix}\), find \(d\), \(\lambda\), and the stationary distribution.
- State the exact condition under which the two-state iteration formula converges to the stationary distribution for every starting distribution.
- For the state-switching matrix \(\begin{bmatrix}0&1\\1&0\end{bmatrix}\), which starting distributions have convergent iterates?
- Explain why \(\mathbf{P}=\mathbf{I}_2\) has no unique stationary distribution.
