[Advanced] — probability that evolves over time, and why a system forgets where it started.
Before you start
- You know distributions and expectation — distributions.
- You can find eigenvalues and a steady state — eigenvalues and eigenvectors. This lesson is the probabilistic reading of that one.
- You know conditional probability — probability.
What you will be able to do after this lesson:
- Model a system as a Markov chain, and state the memorylessness assumption it requires.
- Find a steady state two ways — as an eigenvector and by iterating — and say when one is guaranteed to exist.
- Analyse a random walk, and explain why its expected position is zero while its expected distance grows as .
- Use the Poisson process and a simple queue, and explain why utilisation near makes waiting times explode.
Study route: read 1–5, attempt the prediction in section 4, then run the lab. Block 5 is the result that governs every capacity decision you will ever make.
1. Why this exists
Everything so far has been static: one sample, one distribution, one answer. Real systems evolve. A queue grows and shrinks, a share price moves, a molecule diffuses, a user clicks from page to page.
A stochastic process is a family of random variables indexed by time. The general case is intractable, so the subject lives on one enormously productive simplification: assume the future depends only on the present, not on the whole history. That is the Markov property, and it is both a strong assumption and a surprisingly good approximation for a lot of real systems.
2. Terminology
| Term | Plain-English definition | Note |
|---|---|---|
| Stochastic process | A sequence of random variables over time | |
| State | The condition the system is in | ”sunny”, “queue length 3” |
| Markov property | The future depends only on the present state | ”memorylessness” |
| Transition matrix | Columns sum to | |
| Steady state | A distribution unchanged by a step | The eigenvector for |
| Irreducible | Every state reachable from every other | Needed for a unique steady state |
| Aperiodic | Not locked into a fixed cycle | Also needed |
| Random walk | Steps of with given probabilities | The simplest non-trivial process |
| Poisson process | Events at a constant rate, independently | Gaps are exponential |
| Utilisation | Arrival rate ÷ service rate | The queue’s single most important number |
3. Markov chains
The defining property:
Given the present, the past is irrelevant. That is a real restriction — a queue’s next length depends only on its current length, but a share price’s next move arguably depends on momentum — and it is what makes the mathematics tractable.
Represent it as a matrix where column holds the probabilities of moving from state . Then the distribution after one step is , after steps .
Steady state. A distribution with — precisely an eigenvector with eigenvalue . Every Markov matrix has one, because its columns sum to (the argument is in eigenvalues).
When is it unique, and reached from anywhere? When the chain is irreducible (you can get from any state to any other) and aperiodic (it is not trapped in a rigid cycle). Then for every starting — the chain forgets its initial condition.
The rate of forgetting is , the second-largest eigenvalue magnitude. Closer to means slower mixing. This single number is what PageRank’s convergence speed and a shuffling algorithm’s quality both come down to.
When it fails: a chain with an absorbing state (one you can never leave) is not irreducible, and it converges to that state regardless of the rest. A strictly alternating chain is periodic and never settles — it oscillates forever. The lab shows both.
4. Random walks
Start at ; each step is or with probability . Then:
The expectation is zero by symmetry — but that does not mean the walker stays near the origin. The typical distance grows as , because variances of independent steps add.
This is the same as the standard error in inference, and for the same reason. It also governs diffusion: a molecule’s distance from its start grows with the square root of time, which is why diffusion is fast over microns and hopeless over metres — and why your body needs a circulatory system rather than relying on diffusion.
TIP
Predict before section 5. A service can handle requests per second. Requests arrive at per second — comfortably under capacity. Then traffic rises by , to per second, still under capacity. Roughly what happens to the average queue length: up by , doubles, or something else? Decide before opening the answers.
5. Queues, and why the last 10% of capacity is unusable
A Poisson process has events at a constant average rate , independently. The number in a window is Poisson; the gaps between events are exponential, and exponential gaps are memoryless — having waited five minutes tells you nothing about how much longer you will wait.
The simplest queue, M/M/1, has Poisson arrivals at rate , exponential service at rate , and one server. With utilisation :
Look at the denominator. As , — not linearly, but hyperbolically:
Going from to utilisation multiplies the queue by eleven. This is why systems are provisioned at –: the headroom is not waste, it is the entire defence against latency collapse. It is also why a motorway at capacity jams from one brake tap.
Little’s Law, , holds far more generally than M/M/1 — for essentially any stable queue, regardless of distributions. It is the most useful formula in capacity planning.
Worked example — runnable
Runnable example: save as stochastic.py in any empty directory and run python3 stochastic.py. Standard library only; writes no files.
"""Markov chains, random walks, and why queues explode near full utilisation."""
import math
import random
def step(P, x):
return [sum(P[i][j] * x[j] for j in range(len(x))) for i in range(len(P))]
def steady_state(P, iters=2000):
x = [1.0 / len(P)] * len(P)
for _ in range(iters):
x = step(P, x)
return x
def eigen2(A):
tr = A[0][0] + A[1][1]
de = A[0][0] * A[1][1] - A[0][1] * A[1][0]
disc = tr * tr - 4 * de
if disc < -1e-12:
return []
s = math.sqrt(max(0.0, disc))
return sorted({(tr + s) / 2, (tr - s) / 2}, key=abs, reverse=True)
def mm1(lam, mu):
rho = lam / mu
return rho, rho / (1 - rho), 1 / (mu - lam)
if __name__ == "__main__":
print("Block 1 - a Markov chain forgets where it started")
# columns: from sunny -> (0.9, 0.1); from rainy -> (0.5, 0.5)
P = [[0.9, 0.5], [0.1, 0.5]]
pi = steady_state(P)
print(f" transition matrix {P}")
print(f" steady state: sunny {pi[0]:.9f} rainy {pi[1]:.9f} (exact 5/6, 1/6)")
assert abs(pi[0] - 5 / 6) < 1e-9
for start, label in [([1.0, 0.0], "certainly sunny"), ([0.0, 1.0], "certainly rainy"),
([0.5, 0.5], "an even split")]:
x = start[:]
for _ in range(60):
x = step(P, x)
print(f" from {label:16}: {x[0]:.9f}, {x[1]:.9f}")
assert abs(x[0] - 5 / 6) < 1e-9
lam = eigen2(P)
print(f" eigenvalues {[round(v, 6) for v in lam]} - the 1 guarantees a steady state,")
print(f" and |lambda2| = {abs(lam[1]):.3f} sets how fast it is reached")
print()
print(" the convergence rate really is |lambda2| per step:")
x = [1.0, 0.0]
prev_err = None
for k in range(1, 13):
x = step(P, x)
err = abs(x[0] - 5 / 6)
if k in (1, 2, 4, 8, 12):
ratio = "" if prev_err is None else ""
print(f" step {k:2}: error {err:.3e} |lambda2|^{k} = {abs(lam[1])**k:.3e}")
prev_err = err
print()
print("Block 2 - when the steady state is NOT unique or NOT reached")
absorbing = [[1.0, 0.3], [0.0, 0.7]] # state 0 can never be left
print(f" absorbing chain {absorbing}: everything ends in state 0")
for start in ([0.0, 1.0], [0.5, 0.5]):
x = start[:]
for _ in range(400):
x = step(absorbing, x)
print(f" from {start} -> {[round(v, 9) for v in x]}")
periodic = [[0.0, 1.0], [1.0, 0.0]] # strict alternation
print(f" periodic chain {periodic}: it oscillates and never settles")
x = [1.0, 0.0]
seen = []
for _ in range(6):
x = step(periodic, x)
seen.append(round(x[0], 3))
print(f" state-0 probability over 6 steps: {seen}")
assert seen == [0.0, 1.0, 0.0, 1.0, 0.0, 1.0]
print(" its eigenvalues are 1 and -1: the -1 is what makes it oscillate forever")
assert sorted(eigen2(periodic)) == [-1.0, 1.0]
print()
print("Block 3 - random walk: mean zero, typical distance sqrt(n)")
rng = random.Random(20260910)
TRIALS = 20000
print(" n mean position mean |position| sqrt(2n/pi)")
for n in (10, 100, 1000, 10000):
finals = []
for _ in range(TRIALS // 4):
pos = 0
for _ in range(n):
pos += 1 if rng.random() < 0.5 else -1
finals.append(pos)
mean_pos = sum(finals) / len(finals)
mean_abs = sum(abs(v) for v in finals) / len(finals)
pred = math.sqrt(2 * n / math.pi)
print(f" {n:8} {mean_pos:13.4f} {mean_abs:15.4f} {pred:11.4f}")
assert abs(mean_abs / pred - 1) < 0.06
assert abs(mean_pos) < 0.5 * math.sqrt(n)
print(" the mean is ~0 by symmetry, yet the walker is typically sqrt(n) from home")
print(" this is why diffusion works over microns and fails over metres")
print()
print("Block 4 - exponential gaps are memoryless")
rng2 = random.Random(31337)
waits = [rng2.expovariate(1.0) for _ in range(200000)]
print(f" mean wait {sum(waits)/len(waits):.4f} (should be 1.0)")
for already in (0.0, 1.0, 3.0):
remaining = [w - already for w in waits if w > already]
print(f" given you have already waited {already}: mean REMAINING wait"
f" {sum(remaining)/len(remaining):.4f}")
surv = [w - 3.0 for w in waits if w > 3.0]
assert abs(sum(surv) / len(surv) - 1.0) < 0.05
print(" the remaining wait is always the same - the process has no memory")
print()
print("Block 5 - the last 10% of capacity is unusable")
MU = 10.0
print(" arrivals/s utilisation avg in system L avg wait W (s)")
for lam in (5.0, 8.0, 9.0, 9.5, 9.9, 9.99):
rho, L, W = mm1(lam, MU)
print(f" {lam:10.2f} {rho:11.3f} {L:15.2f} {W:14.4f}")
_, L90, _ = mm1(9.0, MU)
_, L99, _ = mm1(9.9, MU)
print(f" raising arrivals by 10% (9.0 -> 9.9) multiplies the queue by {L99/L90:.1f}x")
assert abs(L99 / L90 - 11.0) < 0.01
print(" a 10% traffic increase, an 11x queue. Utilisation is not a linear dial.")
print()
print(" Little's Law, L = lambda * W, checked at each point above:")
for lam in (5.0, 9.0, 9.9):
rho, L, W = mm1(lam, MU)
print(f" lambda={lam:5.2f}: L={L:8.3f} lambda*W={lam*W:8.3f}")
assert abs(L - lam * W) < 1e-9
print()
print("stochastic: passed")Expected output:
Block 1 - a Markov chain forgets where it started
transition matrix [[0.9, 0.5], [0.1, 0.5]]
steady state: sunny 0.833333333 rainy 0.166666667 (exact 5/6, 1/6)
from certainly sunny : 0.833333333, 0.166666667
from certainly rainy : 0.833333333, 0.166666667
from an even split : 0.833333333, 0.166666667
eigenvalues [1.0, 0.4] - the 1 guarantees a steady state,
and |lambda2| = 0.400 sets how fast it is reached
the convergence rate really is |lambda2| per step:
step 1: error 6.667e-02 |lambda2|^1 = 4.000e-01
step 2: error 2.667e-02 |lambda2|^2 = 1.600e-01
step 4: error 4.267e-03 |lambda2|^4 = 2.560e-02
step 8: error 1.092e-04 |lambda2|^8 = 6.554e-04
step 12: error 2.796e-06 |lambda2|^12 = 1.678e-05
Block 2 - when the steady state is NOT unique or NOT reached
absorbing chain [[1.0, 0.3], [0.0, 0.7]]: everything ends in state 0
from [0.0, 1.0] -> [1.0, 0.0]
from [0.5, 0.5] -> [1.0, 0.0]
periodic chain [[0.0, 1.0], [1.0, 0.0]]: it oscillates and never settles
state-0 probability over 6 steps: [0.0, 1.0, 0.0, 1.0, 0.0, 1.0]
its eigenvalues are 1 and -1: the -1 is what makes it oscillate forever
Block 3 - random walk: mean zero, typical distance sqrt(n)
n mean position mean |position| sqrt(2n/pi)
10 0.0888 2.4656 2.5231
100 -0.1792 7.9952 7.9788
1000 0.6416 25.6488 25.2313
10000 0.7268 79.8668 79.7885
the mean is ~0 by symmetry, yet the walker is typically sqrt(n) from home
this is why diffusion works over microns and fails over metres
Block 4 - exponential gaps are memoryless
mean wait 1.0005 (should be 1.0)
given you have already waited 0.0: mean REMAINING wait 1.0005
given you have already waited 1.0: mean REMAINING wait 1.0029
given you have already waited 3.0: mean REMAINING wait 0.9929
the remaining wait is always the same - the process has no memory
Block 5 - the last 10% of capacity is unusable
arrivals/s utilisation avg in system L avg wait W (s)
5.00 0.500 1.00 0.2000
8.00 0.800 4.00 0.5000
9.00 0.900 9.00 1.0000
9.50 0.950 19.00 2.0000
9.90 0.990 99.00 10.0000
9.99 0.999 999.00 100.0000
raising arrivals by 10% (9.0 -> 9.9) multiplies the queue by 11.0x
a 10% traffic increase, an 11x queue. Utilisation is not a linear dial.
Little's Law, L = lambda * W, checked at each point above:
lambda= 5.00: L= 1.000 lambda*W= 1.000
lambda= 9.00: L= 9.000 lambda*W= 9.000
lambda= 9.90: L= 99.000 lambda*W= 99.000
stochastic: passed
Block 5 is the practical payoff. Arrivals rise by ten per cent — from to against a capacity of — and the queue grows eleven-fold. No component got slower and nothing failed; the arithmetic of did it.
Common pitfalls and traps
- Assuming the Markov property without checking. If the next state depends on how you arrived, the model is wrong. The usual repair is to enlarge the state so it carries the needed history.
- Expecting every chain to converge. Absorbing states and periodicity both break it. Irreducible and aperiodic is the condition.
- Reading as “stays near zero”. The mean is zero; the typical distance grows as . Mean and magnitude are different questions.
- Sizing a system by average utilisation. Averages hide the queue. At the average queue is already nine deep, and bursts make it far worse.
- Assuming exponential service times. M/M/1 assumes them, and real service times are often much more variable — which makes queues worse than the formula predicts, not better.
- Confusing rate with probability. per second is a rate, not a probability, and can exceed .
Check your understanding
- A chain has . Find its steady state.
- Why does every Markov transition matrix have ?
- After steps of a symmetric random walk, what is the expected position, and roughly the typical distance from the origin?
- A server handles requests/s; arrivals are /s. Find , and .
- You have waited minutes for a bus whose arrivals are Poisson with mean gap minutes. What is the expected further wait?
Answers — open only after an attempt
- Solve : gives , so . With : .
- Because each column sums to , the all-ones vector satisfies — so has eigenvalue , and a matrix shares eigenvalues with its transpose.
- by symmetry. Typical distance , so around steps from home.
- . requests. s. Check: . ✓
- Ten minutes. Exponential waits are memoryless — the time already spent carries no information. This is genuinely counter-intuitive and genuinely true for a Poisson process.
And the prediction from section 4: the queue grows by a factor of about eleven, not ten per cent. goes from to . The in the denominator shrank by a factor of ten, and that denominator is what governs the answer.
Practice — independent task
Simulate an M/M/1 queue event by event, and check the formulas you have been handed.
- Implement a discrete-event simulation: draw exponential inter-arrival gaps at rate and exponential service times at rate , and track each customer’s arrival, service-start and departure times.
- Measure the average number in the system and the average time in it. Compare against and at .
- Handle the warm-up. A simulation starting from an empty queue under-reports until it settles. Discard an initial transient, justify the length you chose, and show the difference it makes to your answer.
- Verify Little’s Law directly from your event log, without using either formula.
- Then break the M/M/1 assumption: replace exponential service with a constant service time at the same mean (an M/D/1 queue). Measure and compare with M/M/1 at the same . Theory says the wait halves — confirm or refute it with your numbers, and explain what property of the service distribution is responsible.
Edge cases: (the queue is unstable — what does your simulation do, and what should it do?); very small; a run too short to be meaningful at high .
Done when: your simulated and match theory at every stable , Little’s Law holds on your raw event log, and your M/D/1 result is explained by service-time variability rather than just reported.
Tradeoffs, limits and extensions
The Markov property is an approximation, and a load-bearing one. Real arrivals are bursty and correlated, not Poisson; real service times are more variable than exponential. Both make queues worse than M/M/1 predicts. The Pollaczek–Khinchine formula generalises to arbitrary service distributions and shows the wait grows with service-time variance — which is why reducing variability often beats making the average faster.
Continuous time and the diffusion limit. Let a random walk’s steps shrink and its rate grow and you get Brownian motion, the continuous-time analogue, which underlies both physical diffusion and the Black–Scholes model. The becomes .
Where this connects. The steady state is an eigenvector, so everything from eigenvalues applies — including that convergence speed is , and PageRank is this lesson at web scale. Hidden Markov models add unobserved states and are the basis of a great deal of speech and sequence modelling.
Before moving on
You are done with this lesson when you can:
- Write a transition matrix, find its steady state both ways, and state the conditions for uniqueness.
- Explain why a random walk has zero mean and typical distance.
- Explain memorylessness and why the remaining wait never changes.
- Use and Little’s Law, and say why systems are not run near full utilisation.
Recap for later lookup: Markov property — the future depends only on the present; steady state is the eigenvector for , unique and reached when the chain is irreducible and aperiodic, at rate ; random walk has , , typical distance ; Poisson process has exponential, memoryless gaps; M/M/1 gives , ; Little’s Law holds almost always.
Where next: this is the last lesson in probability and statistics. It connects directly to eigenvalues and to queueing in architecture and operating systems.
Related
- Eigenvalues — the steady state, algebraically
- Inference — the same , in a different setting
- Distributions — Poisson and exponential
- architecture/ — where queueing decides capacity in practice
Software engineering
Infrastructure & security
Computer science
Hardware & engineering