Deriving the Two-State n-Step Formula

From One-Step Switching to n-Step Probabilities

For a two-state chain, each step either keeps the chain in its current state or switches it to the other state. Repeating that one-step rule $n$ times produces probabilities that can be computed by matrix multiplication, but the entries of $P^n$ need not be found by multiplying $P$ by itself repeatedly. A closed-form expression separates the long-run balance between the states from the way an initial state’s effect changes with the number of steps.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain with state space $S=\{1,2\}$, and natural filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. Its transition probabilities satisfy $\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)=p_{X_nj}$ almost surely. Suppose the probability of switching from state 1 to state 2 is $a$, and the probability of switching from state 2 to state 1 is $b$, where $0\le a\le1$, $0\le b\le1$, and $a+b>0$. Set $s=a+b$. The row-stochastic transition matrix is

P= \begin{bmatrix} 1-a & a\\ b & 1-b \end{bmatrix}.

Each row sums to one: $(1-a)+a=1$ and $b+(1-b)=1$. Write $P^n=(p_{ij}^{(n)})$, where $p_{ij}^{(n)}=\mathbb{P}_i(X_n=j)$, and define $\lambda=1-a-b=1-s$. By the Chapman–Kolmogorov equations, $P^n$ gives all transition probabilities over $n$ steps. The condition $s>0$ lets us divide by $s$ in the formula below.

Theorem (Two-state n-step formula): For every integer $n\ge0$, let $\lambda^0=1$. Then $$ P^n= \begin{bmatrix} \frac{b}{s}+\frac{a}{s}\lambda^n & \frac{a}{s}(1-\lambda^n)\\[4pt] \frac{b}{s}(1-\lambda^n) & \frac{a}{s}+\frac{b}{s}\lambda^n \end{bmatrix}, \qquad s=a+b>0,\quad \lambda=1-s. $$

The two ingredients in this expression have distinct roles. The row vector $\pi=(b/s,a/s)$ is an invariant distribution: direct multiplication gives $\pi P=\pi$. The other eigenvalue is $\lambda$, and its contribution is multiplied by $\lambda^n$. In particular, the formula describes finite-step transition probabilities; it does not require making a separate assumption about convergence.

Proof by a Projection Decomposition

Make a matrix whose two rows both equal $\pi$:

\Pi= \begin{bmatrix} b/s & a/s\\ b/s & a/s \end{bmatrix}.

The row entries sum to $(a+b)/s=1$. As a result, multiplying $\Pi$ by itself leaves it unchanged: $\Pi^2=\Pi$. This makes $\Pi$ a projection. Direct comparison of entries gives $P=\Pi+\lambda(I-\Pi)$, where $I$ is the two-by-two identity matrix. The decomposition separates the projection onto the invariant part from the remaining component.

Proof. Since $\Pi^2=\Pi$, we have $\Pi(I-\Pi)=\Pi-\Pi^2=0$ and $(I-\Pi)\Pi=\Pi-\Pi^2=0$. Also, $(I-\Pi)^2=I-2\Pi+\Pi^2=I-\Pi$. We prove by induction that $P^n=\Pi+\lambda^n(I-\Pi)$. For $n=0$, the right side is $\Pi+(I-\Pi)=I=P^0$. Suppose the identity holds for an integer $n\ge0$. Then $$ P^{n+1}=[\Pi+\lambda^n(I-\Pi)][\Pi+\lambda(I-\Pi)] =\Pi+\lambda^{n+1}(I-\Pi), $$ because the two cross-products are zero and each of $\Pi$ and $I-\Pi$ is unchanged by squaring. This proves the identity for every $n\ge0$, including when $\lambda=0$. Substituting the entries of $\Pi$ and $I-\Pi$ gives the four displayed entries of the theorem. $\square$

For example, the top-right entry is $a/s-(a/s)\lambda^n=(a/s)(1-\lambda^n)$. The bottom-left entry is $b/s-(b/s)\lambda^n=(b/s)(1-\lambda^n)$. The diagonal entries retain their corresponding entries of $\Pi$ and add the remaining terms $(a/s)\lambda^n$ and $(b/s)\lambda^n$, respectively. This also shows why the same power of $\lambda$ appears in every entry, but is multiplied by different weights.

An Independent Recurrence Derivation

The top-right entry can also be obtained from a scalar recurrence. Let $x_n=p_{12}^{(n)}$, the probability of being in state 2 after $n$ steps when the chain starts in state 1. To be in state 2 at step $n+1$, the chain must either be in state 1 at step $n$ and switch with probability $a$, or be in state 2 and remain there with probability $1-b$. Thus $x_0=0$ and $x_{n+1}=a(1-x_n)+(1-b)x_n=a+\lambda x_n$.

Proposition: Under the same assumptions, $p_{12}^{(n)}=\frac{a}{s}(1-\lambda^n)$ and $p_{21}^{(n)}=\frac{b}{s}(1-\lambda^n)$ for all $n\ge0$.

Proof. For $x_n=p_{12}^{(n)}$, the formula gives $x_0=(a/s)(1-1)=0$, as required. If $x_n=(a/s)(1-\lambda^n)$, then the recurrence gives $$ x_{n+1}=a+\lambda\frac{a}{s}(1-\lambda^n) =\frac{a}{s}(s+\lambda-\lambda^{n+1}) =\frac{a}{s}(1-\lambda^{n+1}), $$ because $s+\lambda=1$. This proves the expression for $p_{12}^{(n)}$ by induction. Starting in state 2, let $y_n=p_{21}^{(n)}$. The same conditioning gives $y_0=0$ and $y_{n+1}=b+\lambda y_n$. Substituting $y_n=(b/s)(1-\lambda^n)$ into this recurrence gives $y_{n+1}=(b/s)(s+\lambda-\lambda^{n+1})=(b/s)(1-\lambda^{n+1})$, proving the second expression as well. $\square$

Once the off-diagonal probabilities are known, the diagonal entries follow from the fact that each row of $P^n$ sums to one. For example, $p_{11}^{(n)}=1-p_{12}^{(n)}=1-(a/s)(1-\lambda^n)=b/s+(a/s)\lambda^n$. The same calculation gives $p_{22}^{(n)}=a/s+(b/s)\lambda^n$. This recurrence argument checks the projection derivation by a different route.

Worked Calculations

Worked Example: Unequal Switching Probabilities

Take $a=\tfrac14$, $b=\tfrac12$, and find $P^3$. First check that these are valid switching probabilities and that each row of the transition matrix sums to one: $$ P= \begin{bmatrix} \tfrac34 & \tfrac14\\ \tfrac12 & \tfrac12 \end{bmatrix}, \qquad \tfrac34+\tfrac14=1,\quad \tfrac12+\tfrac12=1. $$ Here $s=\tfrac14+\tfrac12=\tfrac34$, $\lambda=1-\tfrac34=\tfrac14$, and $\lambda^3=(\tfrac14)^3=\tfrac1{64}$. The weights are $b/s=(\tfrac12)/(\tfrac34)=\tfrac23$ and $a/s=(\tfrac14)/(\tfrac34)=\tfrac13$. Therefore $$ \begin{aligned} p_{11}^{(3)}&=\tfrac23+\tfrac13\cdot\tfrac1{64} =\tfrac{128}{192}+\tfrac1{192}=\tfrac{129}{192}=\tfrac{43}{64},\\ p_{12}^{(3)}&=\tfrac13(1-\tfrac1{64}) =\tfrac13\cdot\tfrac{63}{64}=\tfrac{21}{64},\\ p_{21}^{(3)}&=\tfrac23(1-\tfrac1{64}) =\tfrac23\cdot\tfrac{63}{64}=\tfrac{21}{32},\\ p_{22}^{(3)}&=\tfrac13+\tfrac23\cdot\tfrac1{64} =\tfrac{64}{192}+\tfrac2{192}=\tfrac{66}{192}=\tfrac{11}{32}. \end{aligned} $$ Thus $P^3=\begin{bmatrix}\tfrac{43}{64}&\tfrac{21}{64}\\[2pt]\tfrac{21}{32}&\tfrac{11}{32}\end{bmatrix}$. Check the rows: $\tfrac{43}{64}+\tfrac{21}{64}=1$, and $\tfrac{21}{32}+\tfrac{11}{32}=1$.

Worked Example: A Symmetric Chain

Take $a=b=\tfrac13$, and calculate $P^4$. The one-step matrix has rows $(\tfrac23,\tfrac13)$ and $(\tfrac13,\tfrac23)$; each sums to one. Now $s=\tfrac23$, $\lambda=\tfrac13$, and $\lambda^4=(\tfrac13)^4=\tfrac1{81}$. Both weights $a/s$ and $b/s$ equal $(\tfrac13)/(\tfrac23)=\tfrac12$. The formula gives $$ p_{11}^{(4)}=p_{22}^{(4)} =\tfrac12+\tfrac12\cdot\tfrac1{81} =\tfrac{41}{81}, \qquad p_{12}^{(4)}=p_{21}^{(4)} =\tfrac12(1-\tfrac1{81}) =\tfrac{40}{81}. $$ Hence $P^4=\begin{bmatrix}\tfrac{41}{81}&\tfrac{40}{81}\\[2pt]\tfrac{40}{81}&\tfrac{41}{81}\end{bmatrix}$. To check by multiplication, $P^2$ has diagonal entries $\tfrac49+\tfrac19=\tfrac59$ and off-diagonal entries $\tfrac29+\tfrac29=\tfrac49$. Squaring $P^2$, the diagonal entries are $\tfrac{25}{81}+\tfrac{16}{81}=\tfrac{41}{81}$, and the off-diagonal entries are $\tfrac{20}{81}+\tfrac{20}{81}=\tfrac{40}{81}$, as in the formula. Each row of both $P$ and $P^4$ sums to one.

Worked Example: A Negative Second Eigenvalue

Take $a=\tfrac34$, $b=\tfrac12$, and calculate $P^3$. The transition matrix is $$ P=\begin{bmatrix}\tfrac14&\tfrac34\\[2pt]\tfrac12&\tfrac12\end{bmatrix}, $$ whose rows sum to $\tfrac14+\tfrac34=1$ and $\tfrac12+\tfrac12=1$. Here $s=\tfrac34+\tfrac12=\tfrac54$, so $\lambda=1-\tfrac54=-\tfrac14$ and $\lambda^3=-\tfrac1{64}$. The weights are $b/s=(\tfrac12)/(\tfrac54)=\tfrac25$ and $a/s=(\tfrac34)/(\tfrac54)=\tfrac35$. Substitution gives $$ \begin{aligned} p_{11}^{(3)}&=\tfrac25-\tfrac35\cdot\tfrac1{64} =\tfrac{128}{320}-\tfrac3{320}=\tfrac{25}{64},\\ p_{12}^{(3)}&=\tfrac35(1+\tfrac1{64}) =\tfrac35\cdot\tfrac{65}{64}=\tfrac{39}{64},\\ p_{21}^{(3)}&=\tfrac25(1+\tfrac1{64}) =\tfrac25\cdot\tfrac{65}{64}=\tfrac{13}{32},\\ p_{22}^{(3)}&=\tfrac35-\tfrac25\cdot\tfrac1{64} =\tfrac{192}{320}-\tfrac2{320}=\tfrac{19}{32}. \end{aligned} $$ The first row sums to $\tfrac{25}{64}+\tfrac{39}{64}=1$; the second sums to $\tfrac{13}{32}+\tfrac{19}{32}=1$. The negative sign in $\lambda$ matters: for odd $n$, its power is negative, so replacing $\lambda^n$ by $|\lambda|^n$ would give incorrect entries.

Using the Formula Carefully

If the initial distribution is the row vector $\mu_0=(u,1-u)$, then the distribution after $n$ steps is $\mu_n=\mu_0P^n$. The matrix formula can be used directly: each component is a weighted combination of the entries in the corresponding column of $P^n$. No new transition rule is needed for a different initial distribution.

Common mistake. Unequal switching probabilities do not give equal weights for the two off-diagonal entries. In the first worked example, the incorrect symmetric shortcut $p_{12}^{(3)}=\tfrac12(1-\lambda^3)$ would give $\tfrac12(1-\tfrac1{64})=\tfrac{63}{128}$. But the correct weight is $a/s=\tfrac13$, so the formula gives $p_{12}^{(3)}=\tfrac13(1-\tfrac1{64})=\tfrac{21}{64}=\tfrac{42}{128}$. The shortcut is wrong because it assumes equal switching probabilities, which this chain does not have.

Three checks help catch errors: set $n=0$ and verify that the formula gives the identity matrix; verify that every computed row sums to one; and, for a small $n$, compare with direct multiplication. At $n=0$, for example, $p_{11}^{(0)}=b/s+a/s=1$, $p_{12}^{(0)}=p_{21}^{(0)}=0$, and $p_{22}^{(0)}=a/s+b/s=1$. These checks test different parts of the calculation: the initial condition, the probability normalization, and the multiplication rule.

Check Your Understanding

Use $P=\begin{bmatrix}1-a&a\\b&1-b\end{bmatrix}$ and the condition $a+b>0$ where needed.

For $a=\tfrac12$, $b=\tfrac14$, compute $\lambda$, $a/s$, and $b/s$. Then write $p_{12}^{(2)}$ as an exact fraction.
Explain why the formula at $n=0$ must produce the identity matrix, and verify its four entries.
Starting from state 1, derive the one-step recurrence for $p_{12}^{(n)}$. Where does the coefficient $\lambda$ come from?
For $a=b$, what relationship between the two off-diagonal entries does the formula imply? Explain which weights make it hold.
For $a=\tfrac34$, $b=\tfrac12$, why does using $|\lambda|^3$ instead of $\lambda^3$ give the wrong result?