5.11.3 Practice set: discrete-time processes

Random walks

Random walks (lesson 5.11.1)

0 of 12 correct

1.
A $\pm 1$ walk takes 12 steps, 5 of them down. Find $S_{12}$
2.
A fair walk takes 3 steps. Find $P(S_3 = 1)$
3.
Each step is $+1$ with probability 0.7. Find $\mathbb{E}[S_{20}]$
4.
Each step is $+1$ with probability 0.6. Find $P(S_2 = 0)$
5.
A fair walk has standard deviation 12 after $n$ steps. What is it after $4n$ steps?
6.
A fair walk takes steps of $\pm 0.5$ . Find $\operatorname{Var}(S_{64})$
7.
A fair walk takes 10,000 steps. Find the standard deviation of the average step $S_n / n$
8.
A fair walk starts at 6 and stops at 0 or 15. Find the chance that it reaches 15 first
9.
The same walk, from 6 between 0 and 15: find the expected number of steps
10.
A fair walk reaches $+10$ within 100 steps with probability 0.3197, and ends at 10 or above with probability 0.1841. Find the chance that it reaches 10 but ends below it
11.
A walk with $p = 0.4$ starts at 1 and stops at 0 or 2. Find the chance it reaches 2 first
12.
A fair walk takes 7 steps. Find $P(S_7 = 0)$

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

Markov chains

Markov chains (lesson 5.11.2)

0 of 10 correct

1.
$P = \begin{pmatrix} 0.8 & 0.2 \\ 0.5 & 0.5 \end{pmatrix}$ . Starting in state 1, find the chance of being in state 2 after 2 steps
2.
The same $P$ , with $\mathbf{s}_0 = (0.2, 0.8)$ . Find the second entry of $\mathbf{s}_1$
3.
The same $P$ : find $\pi_1$ , the stationary chance of state 1
4.
$P = \begin{pmatrix} 0.5 & 0.5 & 0 \\ 0.25 & 0.5 & 0.25 \\ 0 & 0.5 & 0.5 \end{pmatrix}$ . Find $\pi_2$
5.
A regular chain has second eigenvalue 0.5, and $\mathbf{s}_k$ is 0.4 from $\boldsymbol{\pi}$ . About how far is $\mathbf{s}_{k + 3}$ ?
6.
A matrix laid out as in lesson 3.6.2, $M = \begin{pmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{pmatrix}$ , has columns adding up to 1. Find entry $p_{12}$ of the transition matrix $P = M^\top$
7.
State 2 is absorbing. From state 1 the chain stays with chance 0.5 or moves to 2; from state 3 it moves to 1 with chance 0.8 or to 2 with chance 0.2. Find the expected number of steps to absorption from state 3
8.
A walk on 0, 1, 2, 3, 4 stops at 0 and 4 and steps up with chance 0.5. Find the chance that it ends at 4, starting from 3
9.
A student takes the eigenvector of $P$ , not of $P^\top$ , for eigenvalue 1 of a 4-state chain, and scales it to add up to 1. What is its first entry?
10.
$F = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ and $\mathbf{s}_0 = (0.3, 0.7)$ . Find the first entry of $\mathbf{s}_5$

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

Coding exercise

Exercise

The stationary distribution

Write stationary(P), which returns the stationary distribution of a transition matrix P, as in lesson 5.11.2. P is a NumPy array or nested lists, with rows the state now.

Raise ValueError unless P is square, every entry lies between 0 and 1, and every row adds up to 1 within $10^{-9}$ .
Solve $\boldsymbol{\pi}P = \boldsymbol{\pi}$ with the entries adding up to 1. Raise ValueError if the answer is not unique: then $P^\top - I$ has rank below $n - 1$ .
Return an array of $n$ probabilities that add up to 1.

Running the chain for many steps is not enough: the tests include a chain that swings and never settles. They also use the weather chain, lesson 3.6.2's towns and the rating table of case study 5.1.6. A chain with two absorbing states and some broken tables must raise ValueError.

See the tests

import numpy as np

WEATHER = [[0.7, 0.2, 0.1], [0.3, 0.4, 0.3], [0.2, 0.3, 0.5]]
RATINGS = [[0.90, 0.08, 0.015, 0.005], [0.05, 0.85, 0.08, 0.02], [0.01, 0.09, 0.80, 0.10], [0.0, 0.0, 0.0, 1.0]]


def expect_value_error(call, why):
    try:
        call()
    except ValueError:
        return
    raise AssertionError(f"expected ValueError: {why}")


def test_weather():
    """The weather chain of lesson 5.11.2 has stationary distribution (21/46, 13/46, 6/23)"""
    expect_close(np.asarray(stationary(WEATHER)), np.array([21 / 46, 13 / 46, 6 / 23]), what="stationary(weather)", rel=1e-9)


def test_two_towns():
    """Lesson 3.6.2's two towns, as rows: (2/3, 1/3)"""
    expect_close(np.asarray(stationary(np.array([[0.9, 0.1], [0.2, 0.8]]))), np.array([2 / 3, 1 / 3]), what="stationary(towns)", rel=1e-9)


def test_swinging_chain():
    """A chain that swings between two states never settles, but (1/2, 1/2) is still stationary"""
    expect_close(np.asarray(stationary([[0, 1], [1, 0]])), np.array([0.5, 0.5]), what="stationary([[0, 1], [1, 0]])", rel=1e-9)


def test_three_cycle():
    """A chain that cycles 1 → 2 → 3 → 1 has stationary distribution (1/3, 1/3, 1/3)"""
    expect_close(np.asarray(stationary([[0, 1, 0], [0, 0, 1], [1, 0, 0]])), np.array([1, 1, 1]) / 3, what="stationary(cycle)", rel=1e-9)


def test_absorbing():
    """The rating table of case study 5.1.6 ends in default: (0, 0, 0, 1)"""
    expect_close(np.asarray(stationary(RATINGS)), np.array([0.0, 0.0, 0.0, 1.0]), what="stationary(ratings)", abs_tol=1e-9)


def test_any_chain():
    """For a seeded 5-state chain, the answer is a pmf with πP = π"""
    rng = np.random.default_rng(5113)
    P = rng.random((5, 5))
    P /= P.sum(axis=1, keepdims=True)
    pi = np.asarray(stationary(P))
    expect_close(pi.sum(), 1.0, what="sum of the entries", rel=1e-9)
    assert (pi >= 0).all(), f"entries must not be negative, got {pi}"
    expect_close(pi @ P, pi, what="πP", abs_tol=1e-12)


def test_not_unique():
    """Two absorbing states, as in the walk between 0 and 2, leave many stationary distributions: ValueError"""
    expect_value_error(lambda: stationary([[1, 0, 0], [0.5, 0, 0.5], [0, 0, 1]]), "(1 - w, 0, w) is stationary for every w")
    expect_value_error(lambda: stationary(np.eye(2)), "every distribution is stationary for the identity")


def test_bad_matrices():
    """A row adding up to 1.01, a negative entry or a matrix that is not square raise ValueError"""
    expect_value_error(lambda: stationary([[0.7, 0.31], [0.2, 0.8]]), "the first row adds up to 1.01")
    expect_value_error(lambda: stationary([[1.2, -0.2], [0.5, 0.5]]), "an entry is negative")
    expect_value_error(lambda: stationary([[0.5, 0.5, 0.0], [0.1, 0.9, 0.0]]), "a 2 × 3 matrix is not a transition matrix")

Random walks

Markov chains

Coding exercise

Free further reading