5.11.1 Random walks | SigmaField

A walk of steps up and down

Toss a coin again and again. Each head moves a counter up by 1 and each tail moves it down by 1. The position of the counter after $n$ tosses is a random walk.

Write $X_i$ for the $i$ -th step: $+1$ with probability $p$ and $-1$ with probability $1 - p$ , independently of the other steps. The walk starts at $S_0 = 0$ , and after $n$ steps it is at $S_n$ .

Rule: Random walk

\begin{gathered} S_n = X_1 + X_2 + \cdots + X_n \\[4pt] P(X_i = 1) = p, \quad P(X_i = -1) = 1 - p \end{gathered}

Each step is independent of the others. With $p = \frac{1}{2}$ the walk is fair (or symmetric); otherwise it drifts up or down. Each $S_n$ is a random variable measured in steps.

The whole sequence $S_0, S_1, S_2, \ldots$ is a process: one random variable for each time. One run of it is a path. The path below has 6 steps up and 4 down, so it ends at $S_{10} = 6 - 4 = 2$ .

step $n$	1	2	3	4	5	6	7	8	9	10
step $X_n$	$+1$	$-1$	$-1$	$+1$	$+1$	$+1$	$+1$	$-1$	$-1$	$+1$
position $S_n$	1	0	$-1$	0	1	2	3	2	1	2

Try it rng.choice([-1, 1], size=10) draws ten fair steps with a fixed seed, and np.cumsum adds them up: each entry is the position after that many steps. The last line counts the steps up and down and prints where the walk ends.

import numpy as np rng = np.random.default_rng(5121) steps = rng.choice([-1, 1], size=10) S = np.cumsum(steps) print(steps) print(S) print((steps == 1).sum(), (steps == -1).sum(), S[-1])

⌘/Ctrl + Enter runs the cell

Where the walk can be after $n$ steps

If $U$ of the $n$ steps go up, the other $n - U$ go down, so $S_n = U - (n - U) = 2U - n$ . The number of steps up is a count of successes in $n$ independent trials, so $U \sim \operatorname{Bin}(n, p)$ (lesson 5.2.2).

For a fair walk of 4 steps, $U$ is 0 to 4 and $S_4$ is $-4$ , $-2$ , 0, 2 or 4:

$S_4$	$-4$	$-2$	0	2	4
steps up $U$	0	1	2	3	4
$P(S_4 = k)$	$\frac{1}{16}$	$\frac{4}{16}$	$\frac{6}{16}$	$\frac{4}{16}$	$\frac{1}{16}$

Odd values are impossible. Each step changes the position by 1. So after an even number of steps the walk is at an even number, and after an odd number at an odd one. In particular $S_n = 0$ can only happen when $n$ is even.

Rule: Distribution of the position

\begin{gathered} S_n = 2U - n, \quad U \sim \operatorname{Bin}(n, p) \\[4pt] P(S_n = k) = \binom{n}{\frac{n + k}{2}}\, p^{\frac{n + k}{2}}\,(1 - p)^{\frac{n - k}{2}} \end{gathered}

The second line needs $k$ between $-n$ and $n$ with the same parity as $n$ , both even or both odd; otherwise $P(S_n = k) = 0$ . It is the binomial pmf at $U = \frac{n + k}{2}$ .

With $p = 0.6$ the same five values have probabilities 0.0256, 0.1536, 0.3456, 0.3456 and 0.1296: the weight moves up. For a fair walk of 100 steps, $P(S_{100} = 0) = \binom{100}{50}\big/2^{100} = 0.0796$ : being back at the start is the single most likely position, but still unlikely.

p = 0.5

import numpy as np from scipy.stats import binom n = 4 k = np.arange(-n, n + 1, 2) ups = (n + k) // 2 print(k, ups) print(binom.pmf(ups, n, 0.5)) print(np.round(binom.pmf(ups, n, 0.6), 4)) rng = np.random.default_rng(5123) S4 = rng.choice([-1, 1], size=(100_000, n)).sum(axis=1) print([round(float((S4 == v).mean()), 4) for v in k], (S4 == 1).sum()) print(round(binom.pmf(50, 100, 0.5), 4))

⌘/Ctrl + Enter runs the cell

Mean and variance: the $\sqrt{n}$ spread

One step has mean $\mathbb{E}[X] = 1 \cdot p + (-1)(1 - p) = 2p - 1$ . Its square is always 1, so $\operatorname{Var}(X) = 1 - (2p - 1)^2 = 4p(1 - p)$ , by the shortcut of lesson 5.3.2.

The position is a sum of $n$ independent steps. Means add (linearity, lesson 5.3.2), and so do variances, because the steps are independent.

Rule: Mean and variance after n steps

\begin{gathered} \mathbb{E}[S_n] = n(2p - 1) \\[4pt] \operatorname{Var}(S_n) = 4np(1 - p) \\[4pt] \text{fair walk: } \mathbb{E}[S_n] = 0, \quad \sigma_{S_n} = \sqrt{n} \end{gathered}

The variance grows in proportion to $n$ , so the standard deviation grows like $\sqrt{n}$ . Four times as many steps give twice the spread. With steps of $\pm h$ instead of $\pm 1$ , every position is multiplied by $h$ , and so is the standard deviation: $h\sqrt{n}$ for a fair walk.

steps $n$	1	4	16	100	400
standard deviation $\sqrt{n}$	1	2	4	10	20

The figure shows eight fair walks of 400 steps. They spread out, but slowly: after 400 steps the standard deviation is 20 steps, not 400. By the central limit theorem (lesson 5.7.3), $S_n$ is close to normal for large $n$ . So about 95% of walks stay within $\pm 2\sqrt{n}$ (lesson 5.4.3's rule). For $n = 100$ the exact chance of $\lvert S_{100} \rvert \le 20$ is 0.9648.

Eight seeded fair walks. The band of $\pm 2\sqrt{n}$ widens like a square root, not a straight line: after 400 steps it reaches only $\pm 40$ . Seven of the eight paths end inside it.

n = 4

import numpy as np from scipy.stats import binom rng = np.random.default_rng(5112) S = rng.choice([-1, 1], size=(10_000, 100)).cumsum(axis=1) for n in [4, 16, 100]: Sn = S[:, n - 1] print(n, round(Sn.mean(), 2), round(Sn.var(), 2), round(Sn.std(), 2)) k = np.arange(101) inside = np.abs(2 * k - 100) <= 20 print(round((np.abs(S[:, 99]) <= 20).mean(), 4), round(binom.pmf(k, 100, 0.5)[inside].sum(), 4))

⌘/Ctrl + Enter runs the cell

The average settles, the sum does not

The law of large numbers (lesson 5.7.2) says the average step $\frac{S_n}{n}$ settles on the mean step, 0 for a fair walk. The walk itself does the opposite. Its typical distance from the start, $\mathbb{E}\lvert S_n \rvert$ , grows like $\sqrt{n}$ :

steps $n$	10	100	1,000
distance $\mathbb{E}\lvert S_n \rvert$	2.46	7.96	25.23
average $\mathbb{E}\lvert S_n \rvert / n$	0.2461	0.0796	0.0252

Both hold at once: a distance of about $0.8\sqrt{n}$ , divided by $n$ , shrinks like $\frac{1}{\sqrt{n}}$ . A fair walk does not come back towards 0 to make up for a run of heads. It has no reason to go either way.

\mathbb{E}\lvert S_n \rvert

import numpy as np from scipy.stats import binom for n in [10, 100, 1000]: k = np.arange(n + 1) distance = (binom.pmf(k, n, 0.5) * np.abs(2 * k - n)).sum() print(n, round(distance, 2), round(distance / n, 4), round(distance / np.sqrt(n), 3))

⌘/Ctrl + Enter runs the cell

A walk with a drift

With $p = 0.55$ each step has mean $0.1$ and variance $4 \times 0.55 \times 0.45 = 0.99$ . After 100 steps the mean is 10 and the standard deviation 9.95, about the same size, so $P(S_{100} > 0)$ is only 0.8173.

After 10,000 steps the mean is 1,000 and the standard deviation 99.5. The drift grows like $n$ and the spread only like $\sqrt{n}$ , so in the long run the drift wins.

n(2p - 1)

import math import numpy as np from scipy.stats import binom p = 0.55 for n in [100, 10_000]: print(n, round(n * (2 * p - 1), 2), round(math.sqrt(4 * n * p * (1 - p)), 2)) k = np.arange(101) print(round(binom.pmf(k, 100, p)[2 * k - 100 > 0].sum(), 4)) rng = np.random.default_rng(5113) S100 = np.where(rng.random((10_000, 100)) < p, 1, -1).sum(axis=1) print(round(S100.mean(), 2), round(S100.std(), 2))

⌘/Ctrl + Enter runs the cell

First passage: reaching a level

A first-passage question asks when the walk first reaches a level. Take a fair walk and the level $+10$ . What is the chance that it gets there within 100 steps?

This is not $P(S_{100} \ge 10) = 0.1841$ . A walk can touch 10 at step 40 and end below it. Counting those paths too, the chance is 0.3197, almost twice as large.

Simulation answers such questions directly: run many walks and count those that reach the level. For an exact answer, keep the probability of every position. At each step move half of each probability up and half down, and set aside what arrives at $+10$ .

within $n$ steps	100	1,000	10,000
$P(\text{reach } {+10})$	0.3197	0.752	0.9203

A fair walk reaches $+10$ in the end with probability 1, and any other level too. But the wait can be very long: about 8% of walks are still short of it after 10,000 steps. The average waiting time is in fact infinite, which is why the table, not a mean, describes it.

-10{,}000

import numpy as np from scipy.stats import binom level, horizon = 10, 10_000 prob = np.zeros(horizon + level + 1) # index i is position i - horizon prob[horizon] = 1.0 reached = 0.0 for t in range(1, horizon + 1): new = np.zeros_like(prob) new[1:] += 0.5 * prob[:-1] # half moves up new[:-1] += 0.5 * prob[1:] # half moves down reached += new[-1] # walks arriving at +10 stop there new[-1] = 0.0 prob = new if t in (100, 1_000, 10_000): print(t, round(reached, 4)) k = np.arange(101) print(round(binom.pmf(k, 100, 0.5)[2 * k - 100 >= 10].sum(), 4)) rng = np.random.default_rng(5114) S = rng.choice([-1, 1], size=(20_000, 100)).cumsum(axis=1) print(round((S >= 10).any(axis=1).mean(), 4), round((S[:, -1] >= 10).mean(), 4))

⌘/Ctrl + Enter runs the cell

The gambler's ruin

A gambler starts with $a$ dollars and bets $1 at a time on a fair coin. She stops when she has $b$ dollars or nothing. Her fortune is a fair walk started at $a$ that stops at 0 or at $b$ . What is the chance she reaches $b$ first?

Call it $h(a)$ . Condition on the first step: up to $a + 1$ or down to $a - 1$ , each with probability $\frac{1}{2}$ . By the law of total probability (lesson 5.1.3), this first-step analysis gives

h(a) = \tfrac{1}{2}\,h(a + 1) + \tfrac{1}{2}\,h(a - 1)

with $h(0) = 0$ and $h(b) = 1$ . Each value is the average of its two neighbours, so the points lie on a straight line from 0 to 1.

Rule: Gambler's ruin, fair walk

\begin{gathered} P(\text{reach } b \text{ before } 0) = \frac{a}{b} \\[4pt] \mathbb{E}[\text{steps until a stop}] = a(b - a) \end{gathered}

For a fair walk started at $a$ , with $0 \le a \le b$ . The second line comes from the same first-step analysis: each step adds 1, so $m(a) = 1 + \frac{1}{2}m(a + 1) + \frac{1}{2}m(a - 1)$ , with $m(0) = m(b) = 0$ .

From $a = 3$ with $b = 10$ , she reaches $10 with probability 0.3 and goes broke with probability 0.7. The game lasts $3 \times 7 = 21$ bets on average. The fair game gives no edge: her expected fortune at the end is $0.3 \times 10 = 3$ , what she started with.

b = 10

import numpy as np b = 10 A = np.eye(b + 1) for a in range(1, b): A[a, a - 1] = A[a, a + 1] = -0.5 # h(a) - h(a-1)/2 - h(a+1)/2 = 0 top = np.zeros(b + 1) top[b] = 1 # h(b) = 1, h(0) = 0 one_step = np.zeros(b + 1) one_step[1:b] = 1 # m(a) = 1 + averages, m(0) = m(b) = 0 print(np.round(np.linalg.solve(A, top), 4)) print(np.round(np.linalg.solve(A, one_step), 4)) def game(a, b, p, walkers, rng): pos = np.full(walkers, a) steps = np.zeros(walkers, dtype=int) playing = np.ones(walkers, dtype=bool) while playing.any(): pos[playing] += np.where(rng.random(playing.sum()) < p, 1, -1) steps[playing] += 1 playing = (pos > 0) & (pos < b) return round(float((pos == b).mean()), 4), round(float(steps.mean()), 2) rng = np.random.default_rng(5116) print(game(3, 10, 0.5, 100_000, rng))

⌘/Ctrl + Enter runs the cell

A small edge decides a long game

The straight line $\frac{a}{b}$ holds only for a fair walk. With $p \neq \frac{1}{2}$ the same first-step analysis has a different solution, stated here: with $\rho = \frac{1 - p}{p}$ ,

P(\text{reach } b \text{ before } 0) = \frac{1 - \rho^{a}}{1 - \rho^{b}}

Start at 50 with $b = 100$ . A fair coin gives 0.5. A coin with $p = 0.49$ , an edge of one percentage point against the gambler, gives only 0.1192, and $p = 0.47$ gives 0.0025.

The chance of reaching 100 before 0. Fair, it is a straight line; with a small bias against the walker the curve sags far below it, because a long game gives the bias many steps to act.

In a short game the edge matters less: from 5 with $b = 10$ , $p = 0.49$ still gives 0.4502. The longer the game, the more the drift of $n(2p - 1)$ outweighs the $\sqrt{n}$ spread, as in the section on drift.

\frac{a}{b}

import numpy as np def reach_b(a, b, p): if p == 0.5: return a / b rho = (1 - p) / p return (1 - rho**a) / (1 - rho**b) for p in [0.5, 0.49, 0.47]: print(p, round(reach_b(50, 100, p), 4), round(reach_b(5, 10, p), 4)) def game(a, b, p, walkers, rng): pos = np.full(walkers, a) steps = np.zeros(walkers, dtype=int) playing = np.ones(walkers, dtype=bool) while playing.any(): pos[playing] += np.where(rng.random(playing.sum()) < p, 1, -1) steps[playing] += 1 playing = (pos > 0) & (pos < b) return round(float((pos == b).mean()), 4), round(float(steps.mean()), 1) rng = np.random.default_rng(5117) print(game(50, 100, 0.49, 2_000, rng))

⌘/Ctrl + Enter runs the cell

Lesson 5.11.2 writes the gambler's walk as a Markov chain and solves for $h$ the same way. Case study 5.11.4 uses a walk with steps of $\pm\sigma\sqrt{\Delta t}$ : the log of a stock price on a binomial tree.

Common mistakes

The spread grows like $\sqrt{n}$ , not $n$ . Variances add; standard deviations do not. 100 fair steps have standard deviation 10, not 100.
Parity. After an odd number of steps the walk cannot be at 0, or at any even number.
The average settles; the walk does not. $\frac{S_n}{n} \to 0$ for a fair walk, while $\lvert S_n \rvert$ grows like $\sqrt{n}$ . A run of heads is not "made up" later.
Reaching a level is not ending above it. Within 100 steps a fair walk reaches $+10$ with probability 0.3197; it ends at 10 or above with probability only 0.1841.
Certain is not soon. A fair walk reaches every level in the end, but the average wait is infinite.
$\frac{a}{b}$ is for a fair walk only. One point of bias turns 0.5 into 0.1192 over a long game.

Random walks

0 of 12 correct

1.
A walk takes 7 steps up and 3 down. Find $S_{10}$
2.
Can a $\pm 1$ walk be at 0 after 9 steps? Type 1 for yes, 0 for no
3.
A fair walk takes 4 steps. Find $P(S_4 = 2)$
4.
A fair walk takes 6 steps. Find $P(S_6 = 0)$
5.
Each step is $+1$ with probability 0.6. Find $\mathbb{E}[S_{10}]$
6.
Each step is $+1$ with probability 0.6. Find $\operatorname{Var}(S_{25})$
7.
Find the standard deviation of a fair walk after 400 steps
8.
After how many steps does a fair walk have standard deviation 30?
9.
A fair walk takes steps of $\pm 2$ . Find the standard deviation of its position after 100 steps
10.
A fair walk starts at 4 and stops at 0 or 10. Find the chance it stops at 10
11.
The same walk, from 4 between 0 and 10: how many steps does it take on average?
12.
A fair walk starts at 2 and stops at 0 or 8. Find the chance it stops at 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.

S_n = X_1 + \cdots + X_n

Random walks

A walk of steps up and down

Rule: Random walk

Where the walk can be after $n$ steps

Rule: Distribution of the position

Mean and variance: the $\sqrt{n}$ spread

Rule: Mean and variance after n steps

The average settles, the sum does not

A walk with a drift

First passage: reaching a level

The gambler's ruin

Rule: Gambler's ruin, fair walk

A small edge decides a long game

Common mistakes

Random walks

Summary card

Free further reading

A walk of steps up and down

Rule: Random walk

Where the walk can be after nnn steps

Rule: Distribution of the position

Mean and variance: the n\sqrt{n}n​ spread

Rule: Mean and variance after n steps

The average settles, the sum does not

A walk with a drift

First passage: reaching a level

The gambler's ruin

Rule: Gambler's ruin, fair walk

A small edge decides a long game

Common mistakes

Summary card

Free further reading

Where the walk can be after $n$ steps

Mean and variance: the $\sqrt{n}$ spread