Practice: Markov chains · The Lumenary

Markov chains

Warm-upHuman

A Markov chain $X_0, X_1, \dots$ is often called memoryless. Which statement captures the Markov property?

Choose one

X_{n+1}

is independent of

X_0, \dots, X_n

.Given

X_n

, the next state

X_{n+1}

is conditionally independent of

X_0, \dots, X_{n-1}

.From every state, all next states are equally likely.The distribution of

X_n

does not change with

n

.

Markov chains

Warm-upHuman

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?

Markov chains

CoreHuman

Find the stationary distribution of $P = \begin{pmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{pmatrix}$ .

Choose one

\big(\tfrac56, \tfrac16\big)

\big(\tfrac16, \tfrac56\big)

\big(\tfrac12, \tfrac12\big)

(0.9, 0.5)

Markov chains

CoreHuman

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?

Markov chains

CoreHuman

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.)

Choose all that apply

\{3, 4\}

is a closed class, and its states are recurrent.States

1

and

2

are transient.State

1

has period

2

.The chain is irreducible.The stationary distribution gives positive probability to state

1

.

Markov chains

CoreHuman

The lesson proves uniqueness of the stationary distribution by showing that every harmonic function ( $Ph = h$ ) is constant. Where exactly is irreducibility used?

Choose one

To show that

h

attains a maximum.To pass from "

h_j = M

for every

j

reachable in one step from a maximiser" to "

h_j = M

for every state

j

".To show that

h_i = \sum_j p_{ij}h_j

is an average of the values

h_j

.To show that

P - I

and its transpose have the same rank.

Markov chains

CoreHuman

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?

Markov chains

StretchHuman

Which statement about simple random walk is correct?

Choose one

On

\Z^3

the walk returns to the origin with probability

1

, but the expected return time is infinite.On

\Z^2

the expected number of returns to the origin is infinite, so the walk returns with probability

1

.On

\Z

the walk has a stationary distribution, because it is recurrent.Computing

\sum_{n \le 10^6} P(S_{2n} = 0)

in

\Z^2

proves the series diverges.

Markov chains

CoreFormal

Which Lean statement formalises "detailed balance implies stationarity"? (π ᵥ* P is the row vector $\pi P$ .)

Choose one

(hrow : ∀ i, ∑ j, P i j = 1) (hdb : ∀ i j, π i * P i j = π j * P j i) : π ᵥ* P = π(hrow : ∀ i, ∑ j, P i j = 1) (hst : π ᵥ* P = π) : ∀ i j, π i * P i j = π j * P j i(hdb : ∀ i j, π i * P i j = π j * P j i) : π ᵥ* P = π(hrow : ∀ i, ∑ j, P i j = 1) (hdb : ∀ i j, π i * P i j = π j * P j i) : P *ᵥ π = π

Markov chains

StretchComputational

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}$ .

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.