Worked examples — Stochastic processes — Markov chains, steady-state, random walks

Before we start, a quick reminder of the two objects we keep using, in plain words:

We will also need two ways of summarising a random number, so define them once, now, before any calculation uses them:

---

The scenario matrix

Every problem in this chapter lives in exactly one of these cells. The worked examples that follow are tagged with the cell they cover, so together they fill the whole grid.

#	Case class	What makes it tricky	Covered by
A	Standard steady-state (2–3 states, nice numbers)	Solve $\pi =\pi P$ + normalise	Ex 1
B	Sign / direction of drift in a random walk ($p\ne q$)	Mean is no longer $0$ — which way does it lean?	Ex 2
C	Zero / degenerate input: an absorbing state ($P_{ii}=1$)	A row that "traps" you — steady-state can be non-unique	Ex 3
D	Limiting behaviour: what does ${\pi }^{(t)}$ approach, and how fast?	The second eigenvalue controls the speed	Ex 4
E	Periodic / non-convergent chain	Distribution oscillates forever, $\pi$ exists but is never reached	Ex 5
F	Real-world word problem (customer/machine model)	Translate English → matrix, then interpret the answer	Ex 6
G	Gambler's ruin, biased ($p\ne q$) + expected duration	The linear formula breaks; a ratio formula takes over	Ex 7
H	Exam twist: expected number of visits / first-passage	First-step analysis on a different quantity	Ex 8

---

Example 1 — Cell A: standard 3-state steady-state

Forecast: guess first — the middle pad $2$ is reachable from everyone and feeds everyone. Do you expect it to hold more or less probability than the ends? Write your guess.

Recall The setup: what equation are we solving?

$\pi =\pi P$ with ${\pi }_1+{\pi }_2+{\pi }_3=1$. This is the balance equation "inflow = there" for each column.

Step 1. Write the three balance equations, one per column of $P$ (a column collects everyone who flows into that state). ${\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.$ Why this step? Each equation says "probability sitting in state $j$ equals total probability flowing in from all $i$", which is exactly ${\pi }_j={\sum }_i{\pi }_i{P}_{ij}$.

Step 2. Simplify equation 1: $0.5{\pi }_1=0.25{\pi }_2\Rightarrow {\pi }_1=0.5{\pi }_2$. By symmetry, equation 3 gives ${\pi }_3=0.5{\pi }_2$. Why this step? Move the ${\pi }_1$ term to the left; the algebra collapses because the chain is symmetric left-to-right.

Step 3. Normalise: ${\pi }_1+{\pi }_2+{\pi }_3=0.5{\pi }_2+{\pi }_2+0.5{\pi }_2=2{\pi }_2=1\Rightarrow {\pi }_2=0.5$, so ${\pi }_1={\pi }_3=0.25$. Why this step? The three fractions must add to certainty ($1$); that pins down the scale.

$\boxed{\pi =(0.25,0.5,0.25)}$

The middle pad holds more — good if you guessed that.

---

Example 2 — Cell B: biased random walk, which way does it drift?

Forecast: $p>q$, so it leans right. But by how much compared to the random wobble? Guess whether the drift or the spread wins after 100 steps.

How to read the figure below. The horizontal axis is the number of steps $n$; the vertical axis is the particle's position $X_n$. The three thin coloured lines are individual random journeys. The thick navy line is the drift $E[X_n]=0.2n$ — the average position, climbing steadily to the labelled point $(100,20)$. The two dashed navy lines are the spread band $E[X_n]\pm \sqrt{\mathrm{Var}(X_n)}$; the shaded orange region between them is where a typical path lives. The visual lesson: the drift line races up in a straight line while the shaded band only fans out slowly (like $\sqrt{n}$), so by step $100$ the drift ($20$) has clearly overtaken the wobble ($\approx 9.8$).

Step 1. One step $S_k$ has mean $E[S_k]=(+1)(0.6)+(-1)(0.4)=0.2$. Why this step? By the definition of expectation above, the mean of a single move = each outcome times its chance. This nonzero mean is the drift — the constant lean the parent note's symmetric case did not have.

Step 2. $E[X_{100}]={\sum }_{k=1}^{100}E[S_k]=100\times 0.2=20$. Why this step? Expectation is additive; identical steps make it $n$ times one step. The drift grows linearly in $n$ — this is the steep straight navy line in the figure.

Step 3. Variance of one step, using $\mathrm{Var}(S_k)=E[S_k^2]-(E[S_k]{)}^2$: first $E[S_k^2]=(+1{)}^2(0.6)+(-1{)}^2(0.4)=1$, so $\mathrm{Var}(S_k)=1-(0.2{)}^2=0.96$. Why this step? This is exactly the variance definition we set up above. Because steps are independent, variances add: $\mathrm{Var}(X_{100})=100\times 0.96=96$.

Step 4. Spread $=\sqrt{\mathrm{Var}(X_{100})}=\sqrt{96}\approx 9.80$. Why this step? The typical wobble is the standard deviation (square root of variance) — the half-width of the shaded band in the figure. Compare: drift $20$ vs wobble $\approx 9.80$ — the drift wins, so the particle is reliably to the right of the origin.

---

Example 3 — Cell C: an absorbing state (degenerate row)

Forecast: state $2$ is perfectly symmetric between $1$ and $3$ ($0.3$ each). Guess the absorption probability before reading.

Step 1. Let $h=P(\text{absorbed in }3\mid \text{start in }2)$. First-step analysis: $h=0.3\underset{\text{go to }3}{\underbrace{(1)}}+0.4h+0.3\underset{\text{go to }1}{\underbrace{(0)}}.$ Why this step? From state $2$, condition on the first move (memorylessness). Going straight to $3$ succeeds with prob $1$; going to $1$ fails; staying in $2$ leaves us with the same unknown $h$.

Step 2. Solve: $h-0.4h=0.3\Rightarrow 0.6h=0.3\Rightarrow h=0.5$. Why this step? Collect the $h$ terms; the self-loop $0.4h$ moves to the left. Symmetry confirmed: $h=0.5$.

Step 3. Stationary distributions. Solving $\pi =\pi P$ here gives infinitely many: any $\pi =(a,0,1-a)$ with $0\le a\le 1$ works. Why this step? Both absorbing states are stationary on their own; any mixture of them is too. This is the non-uniqueness the parent warned about — the chain is reducible (you cannot get from $1$ to $3$).

$\boxed{P(\text{absorb in }3\mid \text{start }2)=0.5,\pi =(a,0,1-a).}$

---

Example 4 — Cell D: how fast does ${\pi }^{(t)}$ converge?

Forecast: every stochastic matrix has eigenvalue $1$. The other one decides speed. Guess: closer to $0$ means faster or slower convergence?

Step 1. Eigenvalues solve $\det (P-\lambda I)=0$: $(0.8-\lambda )(0.6-\lambda )-(0.2)(0.4)=0$. Why this step? The determinant is zero exactly when $P-\lambda I$ squashes some vector to zero — i.e. that vector is an eigenvector.

Step 2. Expand: ${\lambda }^2-1.4\lambda +(0.48-0.08)={\lambda }^2-1.4\lambda +0.4=0$. Roots: $\lambda =1$ and $\lambda =0.4$. Why this step? Factor the quadratic. As promised, ${\lambda }_1=1$; the mover is ${\lambda }_2=0.4$.

Step 3. Treating the decay as $d(t)\approx |{\lambda }_2{|}^t=0.4^t$, we want $0.4^t<0.01$: $t>\frac{\ln 0.01}{\ln 0.4}=\frac{-4.605}{-0.916}\approx \mathrm{5.03.}$ Why this step? Take logs to unstick $t$ from the exponent. So $6$ steps already bring the total-variation distance below $1\%$.

$\boxed{{\lambda }_2=0.4,\approx 6\text{ steps to }1\%.}$

---

Example 5 — Cell E: a periodic chain that never converges

Forecast: this chain flips deterministically $1\to 2\to 1\to 2$. A stationary $\pi$ still exists — but will a lopsided start ever settle? Guess yes/no.

Step 1. Solve $\pi =\pi P$: $({\pi }_1,{\pi }_2)\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)=({\pi }_2,{\pi }_1)$, so ${\pi }_1={\pi }_2$. With ${\pi }_1+{\pi }_2=1$: $\pi =(0.5,0.5)$. Why this step? The balance equation still has a solution — a stationary distribution existing does not guarantee convergence.

Step 2. Now iterate from ${\pi }^{(0)}=(1,0)$: ${\pi }^{(1)}=(0,1),{\pi }^{(2)}=(1,0),{\pi }^{(3)}=(0,1),\dots$ Why this step? Multiplying by $P$ just swaps the two entries. It oscillates with period $2$ forever, never approaching $(0.5,0.5)$.

$\boxed{\pi =(0.5,0.5)\text{ exists, but }{\pi }^{(t)}\text{ oscillates and never converges.}}$

---

Example 6 — Cell F: real-world word problem

Forecast: stickiness $0.9$ is high, but win-back $0.2$ is modest. Guess the long-run subscribed fraction — above or below $2/3$?

Step 1. Translate the English into a matrix. States: $S$ (subscribed), $C$ (cancelled). $P=\left(\begin{array}{cc}0.9& 0.1\\ 0.2& 0.8\end{array}\right).$ Why this step? Row $S$ reads "stay $0.9$, leave $0.1$"; row $C$ reads "return $0.2$, stay gone $0.8$". Each row sums to $1$ ✔ — that sum is the sanity check that the English translated correctly into a valid transition matrix.

Step 2. Write the balance equation for the $S$ column: ${\pi }_S=0.9{\pi }_S+0.2{\pi }_C$. Why this step? Inflow into $S$ = the $90\%$ who stayed subscribed plus the $20\%$ of cancelled who returned; in steady state this must equal the mass ${\pi }_S$ sitting in $S$.

Step 3. Rearrange: ${\pi }_S-0.9{\pi }_S=0.2{\pi }_C\Rightarrow 0.1{\pi }_S=0.2{\pi }_C\Rightarrow {\pi }_S=2{\pi }_C$. Why this step? Collect the ${\pi }_S$ terms on the left; the leftover relates the two unknowns by a clean ratio $2:1$.

Step 4. Normalise: ${\pi }_S+{\pi }_C=2{\pi }_C+{\pi }_C=3{\pi }_C=1\Rightarrow {\pi }_C=\frac{1}{3},{\pi }_S=\frac{2}{3}$. Why this step? The two fractions must add to $1$ (every customer is in exactly one state); that fixes the scale.

Step 5. Interpret in plain English: in the long run two out of every three customers ($66.7\%$) are subscribed at any given month, regardless of how the company started. Why this step? The problem asked for a real-world fraction, so we translate the vector back to words — the point of a word problem.

$\boxed{\pi =(\frac{2}{3},\frac{1}{3}):66.7\%\text{ subscribed long-run.}}$

---

Example 7 — Cell G: biased gambler's ruin + expected duration

Forecast: with a favourable game ($p>q$), reaching $5$ from $2$ should be higher than the fair-game answer $2/5=0.4$. Guess a number.

Step 1. Set up the first-step equation. Let $h_i=P(\text{reach }5\text{ before }0\mid \text{start at }i)$. Conditioning on the first bet: $h_i=p{h}_{i+1}+q{h}_{i-1},h_0=0,h_5=1.$ Why this step? Memorylessness: after one bet the game restarts at $i+1$ (win) or $i-1$ (loss). The boundaries are certain — at $0$ you have already lost, at $5$ you have already won.

Step 2. Rearrange into a gap relation. Writing $g_i=h_{i+1}-h_i$ and using $p+q=1$: $p{g}_i=q{g}_{i-1}\Rightarrow g_i=r{g}_{i-1},r=\frac{q}{p}=\frac{0.4}{0.6}=\frac{2}{3}.$ Why this step? Move $h_i=(p+q)h_i$ to the right and group. The successive gaps shrink by the constant factor $r$ — a geometric sequence, not the constant gaps that gave the fair-game linear rule.

Step 3. Sum the geometric gaps from $0$ to $i$. Since $h_i=h_0+{\sum }_{k=0}^{i-1}{g}_k=g_0(1+r+\cdots +r^{i-1})$ and $h_5=1$ fixes $g_0$, the standard result drops out: $h_i=\frac{1-r^i}{1-r^N},N=5.$ Why this step? A finite geometric sum $1+r+\cdots +r^{i-1}=\frac{1-r^i}{1-r}$; the same $\frac{1}{1-r}$ appears top and bottom and cancels, leaving the clean ratio.

Step 4. Plug $i=2$, $N=5$, $r=2/3$: $h_2=\frac{1-(2/3{)}^2}{1-(2/3{)}^5}=\frac{1-4/9}{1-32/243}=\frac{5/9}{211/243}=\frac{5}{9}\cdot \frac{243}{211}=\frac{135}{211}\approx \mathrm{0.640.}$ Why this step? Direct substitution. Answer $\approx 0.640>0.4$ — the favourable edge helps, as forecast.

Step 5 — part (b). Why $i/N$ fails: the fair-game derivation assumed equal gaps $h_{i+1}-h_i=h_i-h_{i-1}$, which forces a straight line $h_i=i/N$. That equality only holds when $p=q$ (so $r=1$). With bias $r\ne 1$, the gaps form a geometric sequence, curving $h_i$ upward toward the favourable end — the walk reaches the far goal more easily than "linear" would predict. Why this step? It pinpoints the exact assumption that breaks, so you know when each formula is legal.

$\boxed{P(\text{reach }\$5\mid \$2)=\frac{135}{211}\approx \mathrm{0.640.}}$

---

Example 8 — Cell H: exam twist — expected number of steps (first-passage)

Forecast: this asks about duration, not which end. Guess: a few steps, or many?

Step 1. Let ${\tau }_i$ = expected steps to absorption from state $i$. First-step analysis on the count: ${\tau }_i=1+\frac{1}{2}{\tau }_{i-1}+\frac{1}{2}{\tau }_{i+1},{\tau }_0={\tau }_3=0.$ Why this step? Every move costs one step (the "$+1$"), then from the new state we still expect ${\tau }_{i\pm 1}$ more. Absorbing states cost $0$ (already done). This is first-step analysis applied to a duration instead of a probability — the exam twist.

Step 2. Write the two interior equations ($i=1,2$): ${\tau }_1=1+\frac{1}{2}(0)+\frac{1}{2}{\tau }_2,{\tau }_2=1+\frac{1}{2}{\tau }_1+\frac{1}{2}(0).$ Why this step? Substitute the boundary values ${\tau }_0={\tau }_3=0$; two equations, two unknowns.

Step 3. Solve. From the first, ${\tau }_1=1+\frac{1}{2}{\tau }_2$. Substitute into the second: ${\tau }_2=1+\frac{1}{2}(1+\frac{1}{2}{\tau }_2)=1.5+\frac{1}{4}{\tau }_2\Rightarrow \frac{3}{4}{\tau }_2=1.5\Rightarrow {\tau }_2=2,{\tau }_1=1+1=2.$ Why this step? Linear substitution. By symmetry ${\tau }_1={\tau }_2=2$ makes sense — states $1$ and $2$ are mirror images.

$\boxed{\text{Expected steps from }1=2.}$

---

Active Recall

Recall Which cell asks for the

second eigenvalue, and why? Cell D (convergence speed). The largest eigenvalue $1$ gives $\pi$; $|{\lambda }_2{|}^t$ governs how fast the total-variation distance to $\pi$ decays.

Recall In a biased random walk, which grows like

$n$ and which like $\sqrt{n}$? Drift (mean) grows like $n$; spread (std dev) grows like $\sqrt{n}$. For large $n$ the drift dominates.

Recall Why is

$i/N$ wrong for a biased gambler? It assumes equal gaps $h_{i+1}-h_i$, true only when $p=q$. With bias the gaps are geometric with ratio $q/p$, giving $h_i=\frac{1-r^i}{1-r^N}$.

Recall Absorbing states make a chain's stationary distribution…

Non-unique (the chain is reducible): any mixture of the absorbing states is stationary.

Recall Expected absorption time for a symmetric walk from

$i$ on $\{0,\dots ,N\}$? ${\tau }_i=i(N-i)$.

---

Connections

• Parent topic (the machinery these examples apply)
• Linear Algebra — Eigenvalues and Eigenvectors (Ex 4: ${\lambda }_2$ and convergence rate)
• Perron–Frobenius Theorem (Ex 3 & 5: uniqueness fails for reducible / periodic chains)
• Law of Total Probability (first-step analysis in Ex 3, 7, 8)
• Central Limit Theorem (Ex 2: biased walk → Gaussian around drift $np$)
• Diffusion and Brownian Motion (Ex 2 & 8: $\sqrt{n}$ spread and passage times)
• Google PageRank (Ex 6: a real steady-state = long-run fractions)