The Lumenary · Advanced undergraduate

Markov chains

Name: ______________________

Date: ______________________

You will learn to

Model processes with transition matrices and compute $n$ -step transition probabilities and distributions $\lambda P^n$
Compute hitting probabilities and expected hitting times by first-step analysis, including gambler's ruin
Classify states into communicating classes, as recurrent or transient, and by period, and prove the recurrence criterion $\sum_n p_{ii}^{(n)} = \infty$
Prove that an irreducible finite chain has a unique stationary distribution, and use detailed balance to find it
Prove convergence to equilibrium for irreducible aperiodic finite chains, with a geometric rate
State Pólya's theorem and prove recurrence of simple random walk in dimensions one and two

1.
A Markov chain $X_0, X_1, \dots$ is often called memoryless. Which statement captures the Markov property?
- A. $X_{n+1}$ is independent of $X_0, \dots, X_n$ .
- B.Given $X_n$ , the next state $X_{n+1}$ is conditionally independent of $X_0, \dots, X_{n-1}$ .
- C.From every state, all next states are equally likely.
- D.The distribution of $X_n$ does not change with $n$ .
2.
A weather chain on (dry, cloudy, rainy) has transition matrix $P = \begin{pmatrix} 0.6 & 0.3 & 0.1 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.3 & 0.5 \end{pmatrix}$ . Today is dry. What is the probability, in percent, that the day after tomorrow is dry?
3.
Find the stationary distribution of $P = \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{pmatrix}$ .
- A. $\big(\tfrac56, \tfrac16\big)$
- B. $\big(\tfrac16, \tfrac56\big)$
- C. $\big(\tfrac12, \tfrac12\big)$
- D. $(0.9, 0.5)$
4.
In the fair gambler's ruin game you start with $3$ coins and play one-coin fair bets until you have $0$ or $10$ coins. What is the expected number of bets?
5.
A chain on $\{1, 2, 3, 4\}$ has $p_{12} = 1$ ; $p_{21} = p_{23} = \tfrac12$ ; $p_{33} = p_{34} = \tfrac12$ ; $p_{43} = 1$ . Which statements are true? (Choose all that apply.)
- A. $\{3, 4\}$ is a closed class, and its states are recurrent.
- B.States $1$ and $2$ are transient.
- C.State $1$ has period $2$ .
- D.The chain is irreducible.
- E.The stationary distribution gives positive probability to state $1$ .
6.
The lesson proves uniqueness of the stationary distribution by showing that every harmonic function ( $Ph = h$ ) is constant. Where exactly is irreducibility used?
- A.To show that $h$ attains a maximum.
- B.To pass from " $h_j = M$ for every $j$ reachable in one step from a maximiser" to " $h_j = M$ for every state $j$ ".
- C.To show that $h_i = \sum_j p_{ij}h_j$ is an average of the values $h_j$ .
- D.To show that $P - I$ and its transpose have the same rank.
7.
A walker moves on the $6$ vertices of a hexagon, stepping to each of the two neighbouring vertices with probability $\tfrac12$ . What is the period of the chain?
8.
Which statement about simple random walk is correct?
- A.On $\Z^3$ the walk returns to the origin with probability $1$ , but the expected return time is infinite.
- B.On $\Z^2$ the expected number of returns to the origin is infinite, so the walk returns with probability $1$ .
- C.On $\Z$ the walk has a stationary distribution, because it is recurrent.
- D.Computing $\sum_{n \le 10^6} P(S_{2n} = 0)$ in $\Z^2$ proves the series diverges.
9.
Which Lean statement formalises "detailed balance implies stationarity"? (π ᵥ* P is the row vector $\pi P$ .)
- A.(hrow : ∀ i, ∑ j, P i j = 1) (hdb : ∀ i j, π i * P i j = π j * P j i) : π ᵥ* P = π
- B.(hrow : ∀ i, ∑ j, P i j = 1) (hst : π ᵥ* P = π) : ∀ i j, π i * P i j = π j * P j i
- C.(hdb : ∀ i j, π i * P i j = π j * P j i) : π ᵥ* P = π
- D.(hrow : ∀ i, ∑ j, P i j = 1) (hdb : ∀ i j, π i * P i j = π j * P j i) : P *ᵥ π = π
10.
Write step(mu, P) returning the row vector $\mu P$ (lists of Fractions), and power_iterate(mu, P, n) applying step $n$ times. Then write is_stationary(pi, P). The tests use the two-state chain with $a = \tfrac14$ , $b = \tfrac12$ and check that $\mu P^n$ approaches $\pi = (\tfrac23, \tfrac13)$ at the rate $|1 - a - b|^n = 4^{-n}$ .
Computational — Practice

Answer key — Markov chains

1.
The Markov property: $P(X_{n+1} = j \mid X_0, \dots, X_n) = p_{X_n j}$ . The chain's whole memory is its current state; given that, the earlier history adds nothing. Unconditionally, $X_{n+1}$ usually depends on $X_0$ .
2.
$(P^2)_{11} = 0.6 \cdot 0.6 + 0.3 \cdot 0.3 + 0.1 \cdot 0.2 = 0.36 + 0.09 + 0.02 = 0.47$ , i.e. $47\%$ . (In the long run the chance of a dry day is $\pi_1 = 7/18 \approx 39\%$ .)
3.
$0.1\pi_1 = 0.5\pi_2$ (detailed balance across the single edge) and $\pi_1 + \pi_2 = 1$ give $\pi = (5/6, 1/6)$ . Check: $\frac56 \cdot 0.9 + \frac16 \cdot 0.5 = 0.75 + 0.0833 = \frac56$ .
4.
$m(i) = i(N - i)$ solves the first-step equations with the boundary conditions (on a finite set the solution is unique), so $m(3) = 3 \cdot 7 = 21$ bets. The probability of reaching $10$ is $3/10$ .
5.
Classes: $\{1, 2\}$ (not closed: $2 \to 3$ ) and $\{3, 4\}$ (closed). So $1, 2$ are transient and $3, 4$ recurrent. Returns to $1$ have even length, so $d(1) = 2$ ; state $3$ is aperiodic because $p_{33} > 0$ . On $\{3, 4\}$ , $\pi_3 \cdot \tfrac12 = \pi_4 \cdot 1$ gives $\pi = (0, 0, \tfrac23, \tfrac13)$ , the unique stationary distribution.
6.
Irreducibility is used only to spread the maximum: from a maximiser, the maximum propagates along every positive transition, and irreducibility guarantees that this reaches every state. For the reducible chain $P = I$ on two states, any $h$ is harmonic and any distribution is stationary.
7.
Every step changes the parity of the vertex's position, so return times are even; $2$ is possible. The period is $\gcd\{2, 4, 6, \dots\} = 2$ , and $P(X_n = j)$ does not converge. On a pentagon the walker can return in $2$ and in $5$ steps, so the period is $1$ — a graph walk is aperiodic exactly when the graph is not bipartite.
8.
Only the $\Z^2$ statement is right: via the $45°$ rotation, $P(S_{2n} = 0) = a_n^2 \ge \frac1{4n}$ , whose sum diverges (formalised in Lean). The walk on $\Z^3$ is transient; recurrence on $\Z$ is null, so there is no stationary distribution; and numerical partial sums are evidence, not proof.
9.
Statement (a). (b) is the false converse, (c) drops the row-sum hypothesis the proof needs, and (d) multiplies on the wrong side.
10.
```
from fractions import Fraction

def step(mu, P):
    k = len(P)
    return [sum(mu[i] * P[i][j] for i in range(k)) for j in range(k)]

def power_iterate(mu, P, n):
    for _ in range(n):
        mu = step(mu, P)
    return mu

def is_stationary(pi, P):
    return step(pi, P) == pi
```
From the closed form of $P^n$ , $(P^n)_{11} = \frac{b + a\lambda^n}{a + b}$ with $\lambda = 1 - a - b = \tfrac14$ , so $(P^n)_{11} - \pi_1 = \frac{a}{a + b}\lambda^n = \frac13 \cdot 4^{-n}$ exactly — which the test checks in rational arithmetic.