Two Different Switching Probabilities
A two-state chain can move in both directions at different rates. For instance, a process may leave state \(0\) relatively often but leave state \(1\) only rarely. The resulting transition matrix is still small, but its \(n\)-step probabilities are not obtained by raising each entry to the \(n\)th power. They are found by taking a matrix power. In this tutorial, we derive a formula for that power and check it against direct multiplication.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), and let \((X_n)_{n\ge 0}\) be a discrete-time Markov chain with state space \(S=\{0,1\}\). Its natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). Write \(a\) for the probability of switching from \(0\) to \(1\), and \(b\) for the probability of switching from \(1\) to \(0\). Assume \(0\le a,b\le 1\) and \(a\ne b\). The transition rule is defined for both states, including states that may have probability zero under a particular initial distribution.
Each row of \(P\) sums to \(1\): \((1-a)+a=1\) and \(b+(1-b)=1\). Thus the matrix is row-stochastic. If the initial distribution is the row vector \(\mu_0\), the distribution after \(n\) steps is \(\mu_n=\mu_0P^n\). The entries of \(P^n\) give the probabilities of ending in each state conditional on the starting state.
The Closed Form
The two rows of \(P^n\) can be described using the stationary row vector and a single scalar. Define \(r=1-a-b\). Since \(a+b>0\), the row vector \(\pi=(b/(a+b),\,a/(a+b))\) is well-defined. Its entries sum to \(1\), and direct multiplication gives \(\pi P=\pi\). The following result gives every entry of the power, including at \(n=0\).
Proof. Let \(\mathbf{1}\) be the column vector with both entries equal to \(1\), and let \(J=\mathbf{1}\pi\). Thus every row of \(J\) equals \(\pi\). Because \(\pi\mathbf{1}=1\), multiplication gives \(J^2=\mathbf{1}(\pi\mathbf{1})\pi=J\). Also, \(\pi P=\pi\), while \(P\mathbf{1}=\mathbf{1}\) because the rows of \(P\) sum to \(1\). Therefore \(JP=J\) and \(PJ=J\). Entry by entry, \(J+r(I-J)=\begin{bmatrix}b/(a+b)+ar/(a+b)&a/(a+b)-ar/(a+b)\\ b/(a+b)-br/(a+b)&a/(a+b)+br/(a+b)\end{bmatrix}\). Using \(r=1-a-b\), these entries are \(1-a,a,b,1-b\), respectively, so \(P=J+r(I-J)\).
Since \(J^2=J\), we have \(J(I-J)=(I-J)J=0\), and \((I-J)^2=I-J\). For \(n=0\), \(J+r^0(I-J)=I\). If \(P^n=J+r^n(I-J)\), then $$ P^{n+1}=(J+r^n(I-J))(J+r(I-J))=J+r^{n+1}(I-J), $$ because both cross-products are zero and the squares of \(J\) and \(I-J\) equal themselves. Induction proves this identity for every \(n\ge0\). Substituting the entries of \(J\) and \(I-J\) gives the displayed matrix. \(\square\)
A useful companion is the one-step recurrence for the probability of being in state \(1\). It explains why the single factor \(r^n\) controls the changing part of the answer.
Proof. Conditional on \(\mathcal{F}_n\), the probability that \(X_{n+1}=1\) is \(a\) if \(X_n=0\) and \(1-b\) if \(X_n=1\). Taking expectations gives \(x_{n+1}=a(1-x_n)+(1-b)x_n=a+(1-a-b)x_n\). Set \(c=a/(a+b)\). Since \(a+(1-a-b)c=c\), subtracting \(c\) from the recurrence gives \(x_{n+1}-c=r(x_n-c)\). Repeated substitution yields \(x_n-c=r^n(x_0-c)\), which is the asserted formula. The initial case \(n=0\) holds directly, and each subsequent case follows by multiplying the preceding difference by \(r\). \(\square\)
The theorem gives the entries of \(P^n\), while the recurrence gives the distribution from any particular starting distribution. For example, starting in state \(0\) means \(x_0=0\), so \(\mathbb{P}_0(X_n=1)=\frac{a}{a+b}(1-r^n)\), exactly the upper-right entry of the matrix formula.
Computing and Checking the Powers
Worked Example: Three Steps with \(a=\tfrac14\) and \(b=\tfrac12\)
Consider a discrete-time chain on \(S=\{0,1\}\) with these switching probabilities. Its transition matrix is $$ P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac12&\tfrac12\end{bmatrix}. $$ The first row sums to \(\tfrac34+\tfrac14=1\), and the second sums to \(\tfrac12+\tfrac12=1\). Here \(a+b=\tfrac34\), \(r=1-\tfrac34=\tfrac14\), and \(\pi=(\tfrac23,\tfrac13)\). For \(n=3\), \(r^3=\tfrac1{64}\). The formula gives $$ P^3= \begin{bmatrix} \tfrac23+\tfrac13\cdot\tfrac1{64}&\tfrac13(1-\tfrac1{64})\\ \tfrac23(1-\tfrac1{64})&\tfrac13+\tfrac23\cdot\tfrac1{64} \end{bmatrix} = \begin{bmatrix}\tfrac{43}{64}&\tfrac{21}{64}\\[2pt]\tfrac{21}{32}&\tfrac{11}{32}\end{bmatrix}. $$
Check by repeated multiplication. First, $$ P^2= \begin{bmatrix} \tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac12& \tfrac34\cdot\tfrac14+\tfrac14\cdot\tfrac12\\ \tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac12& \tfrac12\cdot\tfrac14+\tfrac12\cdot\tfrac12 \end{bmatrix} = \begin{bmatrix}\tfrac{11}{16}&\tfrac5{16}\\[2pt]\tfrac58&\tfrac38\end{bmatrix}. $$ Multiplying \(P^2P\), the first row is \((\tfrac{11}{16}\cdot\tfrac34+\tfrac5{16}\cdot\tfrac12,\ \tfrac{11}{16}\cdot\tfrac14+\tfrac5{16}\cdot\tfrac12)=(\tfrac{43}{64},\tfrac{21}{64})\). The second row is \((\tfrac58\cdot\tfrac34+\tfrac38\cdot\tfrac12,\ \tfrac58\cdot\tfrac14+\tfrac38\cdot\tfrac12)=(\tfrac{21}{32},\tfrac{11}{32})\). The two methods agree. The row sums are \(\tfrac{43}{64}+\tfrac{21}{64}=1\) and \(\tfrac{21}{32}+\tfrac{11}{32}=1\).
Worked Example: Two Steps with \(a=\tfrac13\) and \(b=\tfrac12\)
Now let the probability of switching from \(0\) be \(\tfrac13\), and from \(1\) be \(\tfrac12\). Then $$ P=\begin{bmatrix}\tfrac23&\tfrac13\\[2pt]\tfrac12&\tfrac12\end{bmatrix}. $$ The row sums are \(\tfrac23+\tfrac13=1\) and \(\tfrac12+\tfrac12=1\). We have \(a+b=\tfrac56\), \(r=\tfrac16\), and \(\pi=(\tfrac35,\tfrac25)\). For \(n=2\), \(r^2=\tfrac1{36}\). Substitution gives $$ P^2= \begin{bmatrix} \tfrac35+\tfrac25\cdot\tfrac1{36}&\tfrac25(1-\tfrac1{36})\\ \tfrac35(1-\tfrac1{36})&\tfrac25+\tfrac35\cdot\tfrac1{36} \end{bmatrix} = \begin{bmatrix}\tfrac{11}{18}&\tfrac7{18}\\[2pt]\tfrac7{12}&\tfrac5{12}\end{bmatrix}. $$
Check by one multiplication. The entries computed from \(P^2=PP\) are \((P^2)_{00}=\tfrac23\cdot\tfrac23+\tfrac13\cdot\tfrac12=\tfrac49+\tfrac16=\tfrac{11}{18}\), \((P^2)_{01}=\tfrac23\cdot\tfrac13+\tfrac13\cdot\tfrac12=\tfrac29+\tfrac16=\tfrac7{18}\), \((P^2)_{10}=\tfrac12\cdot\tfrac23+\tfrac12\cdot\tfrac12=\tfrac13+\tfrac14=\tfrac7{12}\), and \((P^2)_{11}=\tfrac12\cdot\tfrac13+\tfrac12\cdot\tfrac12=\tfrac16+\tfrac14=\tfrac5{12}\). Both rows sum to \(1\): \(\tfrac{11}{18}+\tfrac7{18}=1\) and \(\tfrac7{12}+\tfrac5{12}=1\). These entries match the closed form.
Worked Example: A Negative Factor with \(a=\tfrac34\) and \(b=\tfrac12\)
A negative \(r\) makes the correction to the stationary rows alternate in sign. Here $$ P=\begin{bmatrix}\tfrac14&\tfrac34\\[2pt]\tfrac12&\tfrac12\end{bmatrix}. $$ The row sums are \(\tfrac14+\tfrac34=1\) and \(\tfrac12+\tfrac12=1\). Also \(a+b=\tfrac54\), \(r=-\tfrac14\), and \(\pi=(\tfrac25,\tfrac35)\). For \(n=2\), \(r^2=\tfrac1{16}\), so $$ P^2= \begin{bmatrix} \tfrac25+\tfrac35\cdot\tfrac1{16}&\tfrac35(1-\tfrac1{16})\\ \tfrac25(1-\tfrac1{16})&\tfrac35+\tfrac25\cdot\tfrac1{16} \end{bmatrix} = \begin{bmatrix}\tfrac7{16}&\tfrac9{16}\\[2pt]\tfrac38&\tfrac58\end{bmatrix}. $$
Check by multiplication. The first row of \(P^2\) is \((\tfrac14\cdot\tfrac14+\tfrac34\cdot\tfrac12,\ \tfrac14\cdot\tfrac34+\tfrac34\cdot\tfrac12)=(\tfrac1{16}+\tfrac38,\tfrac3{16}+\tfrac38)=(\tfrac7{16},\tfrac9{16})\). The second row is \((\tfrac12\cdot\tfrac14+\tfrac12\cdot\tfrac12,\ \tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac12)=(\tfrac18+\tfrac14,\tfrac38+\tfrac14)=(\tfrac38,\tfrac58)\). The row sums are \(\tfrac7{16}+\tfrac9{16}=1\) and \(\tfrac38+\tfrac58=1\), verifying the formula and the stochasticity check.
What the Formula Says About Repeated Switching
The quantity \(r=1-a-b\) determines how quickly the \(n\)-step rows differ from \(\pi\). If \(0<a+b<2\), then \(-1<r<1\), so \(r^n\) tends to \(0\). The formula therefore shows, entry by entry, that \(P^n\) tends to the matrix whose two rows are \(\pi\). This statement follows directly from the formula and the elementary limit \(r^n\to0\) for \(|r|<1\); it does not assert that every stochastic matrix has this behavior.
In the unequal-switching setting, \(a+b>0\) by assumption. Also \(a+b<2\): since \(a,b\le1\), equality would require \(a=b=1\), contrary to \(a\ne b\). Thus the unequal-switching chain satisfies \(0<a+b<2\), and its powers converge to the stated rows. If the unequal-switching restriction is dropped, the boundary case \(a=b=1\) shows why the upper inequality matters: \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\), so \(P^{2m}=I\) and \(P^{2m+1}=P\) for every integer \(m\ge0\). These powers alternate and do not converge. At the other boundary, \(a=b=0\) gives \(P=I\); there is no movement between states, and the formula involving \(a+b\) is undefined.
Common mistake: reversing the stationary weights. In the first example, the stationary row is \((\tfrac23,\tfrac13)\), not \((\tfrac13,\tfrac23)\). The latter reversed vector is not stationary: its first coordinate after multiplication by \(P\) is \(\tfrac13\cdot\tfrac34+\tfrac23\cdot\tfrac12=\tfrac14+\tfrac13=\tfrac7{12}\), which is not \(\tfrac13\). The correct first coordinate is \(\tfrac23\cdot\tfrac34+\tfrac13\cdot\tfrac12=\tfrac12+\tfrac16=\tfrac23\). The weight of state \(0\) is proportional to the rate of switching into state \(0\), namely \(b\); the weight of state \(1\) is proportional to \(a\).
A second frequent error is to treat \(P^n\) as if each entry were raised to the \(n\)th power. For example, in the first example this would give \((P^2)_{00}=(\tfrac34)^2=\tfrac9{16}\). But the actual entry is \(\tfrac{11}{16}\), because a two-step path from \(0\) to \(0\) can go through either \(0\) or \(1\): \(\tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac12=\tfrac{11}{16}\). Matrix multiplication sums over the possible intermediate states, as required by the Chapman–Kolmogorov equations.
Check Your Understanding
In each calculation, use row vectors for distributions and check that each transition-matrix row sums to \(1\).
- For \(a=\tfrac14\) and \(b=\tfrac34\), write \(P\), find \(r\) and \(\pi\), and calculate \(P^2\) from the closed form.
- Starting in state \(0\) in the chain with \(a=\tfrac13\) and \(b=\tfrac12\), use the recurrence for \(x_n=\mathbb{P}_0(X_n=1)\) to find \(x_2\).
- Explain why \(P^0=I\) follows from the formula, even when \(r=0\).
- For the chain with \(a=\tfrac34\) and \(b=\tfrac12\), calculate \(r^3\). What does its sign say about the correction to the stationary rows?
- For \(a=b=1\), compute \(P^2\) and \(P^3\). Why does the sequence of powers fail to converge?