Markov chains: transition matrices, stationary distributions and absorption

Worked solutions

Problem 1

1. $P = \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5\end{pmatrix}$, states in the order S, RRow $i$ is the distribution of tomorrow given today is $i$; each row sums to $1$.
2. $\Pr(X_2 = R \mid X_0 = S) = P_{SS}P_{SR} + P_{SR}P_{RR}$Condition on tomorrow's weather: sunny then rainy, or rainy then rainy.
3. $= 0.9\cdot0.1 + 0.1\cdot0.5 = 0.09 + 0.05 = 0.14$The two paths are disjoint, so their probabilities add.
4. $P^2 = \begin{pmatrix} 0.86 & 0.14 \\ 0.70 & 0.30\end{pmatrix}$Step 2 is the $(S, R)$ entry of $P^2$: row $S$ of $P$ times column $R$. Its rows still sum to $1$.
5. $P = \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5\end{pmatrix}$; the probability of rain two days after a sunny day is $0.14$After a rainy day it is $0.30$: the chain still remembers the start after two steps, but less than after one ($0.1$ against $0.5$).

Problem 2

1. $\pi_0 = (1, 0, 0)$Certain to be in state $1$; a row vector.
2. $\pi_1 = \pi_0P = (0.5, 0.5, 0)$Multiplying a one-hot row vector by $P$ picks out a row of $P$.
3. $\pi_2 = 0.5\,(0.5, 0.5, 0) + 0.5\,(0.25, 0.5, 0.25) = (0.375, 0.5, 0.125)$$\pi_1P$ is the mixture of the rows of $P$, weighted by $\pi_1$.
4. $\pi_3 = 0.375\,(0.5, 0.5, 0) + 0.5\,(0.25, 0.5, 0.25) + 0.125\,(0, 0.5, 0.5) = (0.3125, 0.5, 0.1875)$Each entry is still a sum of nonnegative terms, and the total stays $1$.
5. $\pi_1 = (\tfrac12, \tfrac12, 0)$, $\pi_2 = (\tfrac38, \tfrac12, \tfrac18)$, $\pi_3 = (\tfrac{5}{16}, \tfrac12, \tfrac{3}{16})$Writing $P$ times the column $(1, 0, 0)^\top$ instead gives the first column of $P$, which is not a distribution (Mistake 1).

Problem 3

1. $\pi_1 = 0.5\pi_1 + 0.25\pi_2$, $\pi_2 = 0.5\pi_1 + 0.5\pi_2 + 0.5\pi_3$, $\pi_3 = 0.25\pi_2 + 0.5\pi_3$$\pi P = \pi$ entry by entry: column $j$ of $P$ gives the equation for $\pi_j$. Here $\pi_i$ are the entries of $\pi$.
2. $\pi_2 = 2\pi_1$ and $\pi_2 = 2\pi_3$From the first and third equations; the middle one then holds automatically, since one equation of $\pi P = \pi$ is always redundant.
3. $\pi_1 + 2\pi_1 + \pi_1 = 1$, so $\pi_1 = \tfrac14$The normalization replaces the redundant equation.
4. $\pi_0P - \pi = (\tfrac14, 0, -\tfrac14)$, $\pi_0P^2 - \pi = (\tfrac18, 0, -\tfrac18)$, $\pi_0P^3 - \pi = (\tfrac{1}{16}, 0, -\tfrac{1}{16})$The distributions of Problem 2 minus the stationary one. The gap halves at every step.
5. $\pi = (\tfrac14, \tfrac12, \tfrac14)$; the distance from it halves each stepThe eigenvalues of $P$ are $1$, $\tfrac12$ and $0$, and the halving is $\lambda_2 = \tfrac12$. The eigenvector that np.linalg.eig(P) returns for $\lambda = 1$ is $(1, 1, 1)$, which is not $\pi$ (Mistake 2).

Problem 4

1. $\pi_1a = \pi_2b$, so $\pi = \Big(\dfrac{b}{a + b}, \dfrac{a}{a + b}\Big)$In a two-state chain the flow from $1$ to $2$ must equal the flow back.
2. $\lambda_1 = 1$ and $\lambda_2 = \operatorname{tr}P - 1 = 1 - a - b$Every stochastic matrix has $P\mathbf 1 = \mathbf 1$, so $1$ is an eigenvalue, and the two eigenvalues add to the trace $2 - a - b$.
3. $P^n = \dfrac{1}{a + b}\begin{pmatrix} b & a \\ b & a\end{pmatrix} + \dfrac{\lambda_2^n}{a + b}\begin{pmatrix} a & -a \\ -b & b\end{pmatrix}$The first matrix has both rows equal to $\pi$; the second is the part that decays. At $n = 0$ the sum is $I$, and multiplying by $P$ multiplies the second part by $\lambda_2$.
4. $(P^n)_{12} = \dfrac{a}{a + b}\big(1 - \lambda_2^n\big)$The $(1, 2)$ entry of step 3.
5. $\pi = \big(\tfrac{b}{a+b}, \tfrac{a}{a+b}\big)$, eigenvalues $1$ and $1 - a - b$, $(P^n)_{12} = \tfrac{a}{a+b}(1 - (1 - a - b)^n)$Problem 1 has $a = 0.1$, $b = 0.5$: $\pi = (\tfrac56, \tfrac16)$, $\lambda_2 = 0.4$, and $(P^2)_{SR} = \tfrac16(1 - 0.16) = 0.14$. At $a = b = 1$ the chain alternates, $\lambda_2 = -1$, and $P^n$ never settles (Mistake 3).

Problem 5

1. From sunny: $(P^n)_{SR} - \tfrac16 = -\tfrac16(0.4)^n$Problem 4, step 4, with $\lambda_2 = 0.4$.
2. $\tfrac16(0.4)^n < 0.001$ needs $0.4^n < 0.006$, so $n > \dfrac{\ln 0.006}{\ln 0.4} \approx 5.58$Dividing by $\ln 0.4 < 0$ flips the inequality.
3. From rainy: $(P^n)_{RR} - \tfrac16 = \tfrac56(0.4)^n$The $(2, 2)$ entry of Problem 4, step 3: $\tfrac{a}{a+b} + \tfrac{b}{a+b}\lambda_2^n$.
4. $\tfrac56(0.4)^n < 0.001$ needs $0.4^n < 0.0012$, so $n > \dfrac{\ln 0.0012}{\ln 0.4} \approx 7.34$A larger starting gap, the same rate.
5. $6$ days from a sunny start, $8$ days from a rainy startCheck: $\tfrac16(0.4)^6 \approx 0.00068$ and $\tfrac56(0.4)^8 \approx 0.00055$, while $\tfrac16(0.4)^5 \approx 0.0017$ and $\tfrac56(0.4)^7 \approx 0.0014$ are still too big. Each day multiplies the gap by $|\lambda_2| = 0.4$.

Problem 6

1. Return time to R $= 1/\pi_R = 6$ daysThe chain spends a fraction $\tfrac16$ of its days in R, so visits are $6$ days apart on average.
2. From S, each day is rainy with probability $0.1$, independently, until the first one: $h_{S \to R} = 1/0.1 = 10$The number of steps until the first success is geometric with mean $1/p$.
3. Return time to R $= 1 + 0.5\cdot0 + 0.5\cdot h_{S \to R}$One step, then either it rains again at once (probability $0.5$) or the chain is in S and must still reach R.
4. $= 1 + 0.5\cdot10 = 6$Agrees with step 1.
5. $6$ days between rainy days; $10$ days from a sunny day to the first rain$1/\pi_R$ is a return time, not the time to get there from somewhere else: using $6$ for the trip from S is Mistake 4. Likewise the return time to S is $1/\pi_S = \tfrac65 = 1 + 0.1\cdot 2$.

Problem 7

1. $Q = \begin{pmatrix} 0 & \tfrac12 & 0 \\ \tfrac12 & 0 & \tfrac12 \\ 0 & \tfrac12 & 0\end{pmatrix}$, $R = \begin{pmatrix} \tfrac12 & 0 \\ 0 & 0 \\ 0 & \tfrac12\end{pmatrix}$Rows of $Q$ are moves among $1, 2, 3$ chips; the columns of $R$ are absorption at $0$ and at $4$.
2. $N = (I - Q)^{-1} = \begin{pmatrix} 1.5 & 1 & 0.5 \\ 1 & 2 & 1 \\ 0.5 & 1 & 1.5\end{pmatrix}$Check: $(I - Q)N = I$; for example row $1$ of $I - Q$ is $(1, -\tfrac12, 0)$, and with the first column of $N$ it gives $1.5 - 0.5 = 1$.
3. $N\mathbf 1 = (3, 4, 3)$Expected number of bets. It matches the formula $k(4 - k)$ for a fair game.
4. $B = NR = \begin{pmatrix} 0.75 & 0.25 \\ 0.5 & 0.5 \\ 0.25 & 0.75\end{pmatrix}$Row $k$ is (ruin, reach $4$) from $k$ chips; each row sums to $1$.
5. From $1$ chip: $3$ bets on average and probability $\tfrac14$ of reaching $4$; from $2$: $4$ bets and $\tfrac12$; from $3$: $3$ bets and $\tfrac34$A fair game keeps the expected fortune constant: $\tfrac14\cdot4 = 1$. Three straight wins, $\tfrac18$, is only one of the ways to get there (Mistake 5).

Problem 8

1. $Q = \begin{pmatrix} 0.5 & 0.3 \\ 0.2 & 0\end{pmatrix}$, $R = \begin{pmatrix} 0 & 0.2 \\ 0.5 & 0.3\end{pmatrix}$Transient states Browse, Cart; absorbing states Buy, Leave. Each row of $(Q \mid R)$ sums to $1$.
2. $I - Q = \begin{pmatrix} 0.5 & -0.3 \\ -0.2 & 1\end{pmatrix}$, $\det = 0.5 - 0.06 = 0.44$A $2\times2$ inverse needs the determinant.
3. $N = \dfrac{1}{0.44}\begin{pmatrix} 1 & 0.3 \\ 0.2 & 0.5\end{pmatrix} \approx \begin{pmatrix} 2.273 & 0.682 \\ 0.455 & 1.136\end{pmatrix}$Swap the diagonal, negate the off-diagonal, divide by the determinant.
4. $\Pr(\text{Buy}) = N_{11}R_{11} + N_{12}R_{21} = 0 + \dfrac{0.3}{0.44}\cdot0.5 = \dfrac{15}{44}$First column of $B = NR$. Only Cart leads to Buy, so the answer is the expected number of Cart visits times $0.5$.
5. $\Pr(\text{Buy}) = \tfrac{15}{44} \approx 0.341$; expected time $\tfrac{1 + 0.3}{0.44} = \tfrac{65}{22} \approx 2.95$ minutesThe leave probability is $\tfrac{29}{44} \approx 0.659$, and the two add to $1$. A user who has reached the cart buys with probability $\tfrac{25}{44} \approx 0.568$, which is the number to optimize.

Problem 9

1. Degrees $A{:}\ 3$, $B{:}\ 2$, $C{:}\ 3$, $D{:}\ 2$, and $2|E| = 10$, so the candidate is $\pi = (0.3, 0.2, 0.3, 0.2)$Each edge adds $1$ to two degrees.
2. For an edge $uv$: $\pi_uP_{uv} = \dfrac{\deg u}{10}\cdot\dfrac{1}{\deg u} = \dfrac{1}{10} = \pi_vP_{vu}$The degree cancels; for non-neighbors both sides are $0$.
3. Detailed balance implies $\pi P = \pi$Sum $\pi_iP_{ij} = \pi_jP_{ji}$ over $i$: the right side gives $\pi_j\sum_iP_{ji} = \pi_j$.
4. Return time to $A$ $= 1/0.3 = \tfrac{10}{3}$The busier vertices are visited more often.
5. Detailed balance holds with $\pi = (0.3, 0.2, 0.3, 0.2)$ and the return time to $A$ is $\tfrac{10}{3}$; the rotating chain has $\pi = (\tfrac13, \tfrac13, \tfrac13)$ but $\pi_1P_{12} = \tfrac29 \ne \tfrac19 = \pi_2P_{21}$Its columns also sum to $1$, so the uniform $\pi$ is stationary, yet probability circulates $1 \to 2 \to 3 \to 1$ on net. Detailed balance is sufficient for stationarity, not necessary; MCMC samplers are built to satisfy it because it is easy to check one pair at a time.

Problem 10

1. $P = \begin{pmatrix} 0 & 0.5 & 0.5 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{pmatrix}$Page $1$ splits its probability over two links.
2. $\pi_j = 0.05 + 0.85\sum_i\pi_iP_{ij}$$\pi\,\tfrac{1-d}{3}\mathbf 1\mathbf 1^\top = 0.05\,\mathbf 1^\top$ because $\sum_i\pi_i = 1$.
3. $\pi_1 = 0.05 + 0.85\pi_3$, $\pi_2 = 0.05 + 0.425\pi_1$, $\pi_3 = 0.05 + 0.85(0.5\pi_1 + \pi_2)$Column by column.
4. Substitute $\pi_2$ and $\pi_3 = (\pi_1 - 0.05)/0.85$ into $\pi_1 + \pi_2 + \pi_3 = 1$: $2.21125\,\pi_1 = 0.8575$Multiply through by $0.85$ first.
5. $\pi \approx (0.388, 0.215, 0.397)$, exactly $\tfrac{1}{1769}(686, 380, 703)$; without damping $\pi = (0.4, 0.2, 0.4)$Page $3$ ranks first because it collects links from both other pages. The jumps pull every score toward $\tfrac13$, and they make the chain converge at the rate $0.85\cdot|\lambda_2(P)| = 0.85\cdot0.707 \approx 0.601$ per step, since $P$'s other eigenvalues are $-\tfrac12 \pm \tfrac12 i$.