Probability and emergence

There is no physics in this module. No energy, no particles, no container, no temperature — not one symbol with a unit attached. That is deliberate. The course’s guiding question is how predictable macroscopic behaviour comes out of uncertain microscopic behaviour, and the cleanest way to see the mechanism is to remove every physical prop and watch it work anyway.

The puzzle: order out of nothing but noise¶

A drunkard leaves a lamp post. Every second he takes one step, left or right, decided by a fair coin. He has no destination, no memory of where he has been, and no tendency to return. After a thousand seconds, where is he?

The honest answer is that nobody knows. Run the experiment and he might be four steps to the left, or sixty to the right. Run it again and you get a different number. There is no prediction to make about him at all.

Now put ten thousand independent drunkards under the same lamp post and let them all walk. After a thousand seconds, count how many are standing at each position.

That histogram is the same every time. Not roughly the same — the same to a precision you can set your watch by, a smooth bell-shaped curve of a definite width, reproducible to three figures in an afternoon’s computing. It is there whether the walkers flip coins, draw from a uniform distribution, or use some lopsided rule you invented this morning.

Two things have to be explained, and they are separate. The width of the cloud is the easier one: it is module 0’s law of large numbers, read in the other direction. The shape is the harder one, and it is the central limit theorem — the most consequential theorem in this course, and the reason the rest of it is possible at all.

Predict before you calculate¶

Commit to an answer for each before running anything. Write them down. The point is not to be right; it is to find out which of your intuitions the simulation is about to overturn.

A walker takes 100 steps of $\pm 1$ . Roughly how far from the lamp post do you expect to find him — about 0, about 10, or about 100?
After 500 steps one particular walker is standing at +30. Over his next 500 steps, is his motion biased back toward zero?
The cloud of walkers is visibly getting wider as time goes on. Does that mean the average position is drifting?
Replace the coin with steps drawn uniformly from $[-1, 1]$ , and then with a heavy-tailed distribution that occasionally produces a large jump. Does the long-time histogram change its shape?

Explore the model¶

The laboratory notebook lets you set the number of walkers, the number of steps and the step distribution, then watch the cloud, its histogram, and its width all at once.

Here is the phenomenon in one picture. First a single walker, alone: a jagged line that tells you nothing. Then the ensemble on the same clock, with the profile of where its walkers are standing drawn beside them.

One walker, then a cloud. On the left, a hundred and twenty paths are drawn — enough to see a cloud, few enough to still see through it; the profile on the right is built from all four thousand walkers, which is why it is so much smoother than the picture beside it looks. The single dark path is present in both acts and behaves identically in both: nothing about it changed when the others arrived. The red curve is not fitted to that profile — it is the Gaussian predicted from the step distribution and the elapsed time alone, drawn on top.

The cloud widens, and it widens at a particular rate. The next animation measures it: the blue line is the spread of the cloud, the dashed red curve is $\sqrt{t}$ , and the dark line running along the bottom is the ensemble average.

Width and drift are independent facts. The spread climbs the square-root curve; the mean stays flat inside the grey band, which is its own three-standard-error uncertainty. A cloud that is spreading is not a cloud that is moving.

And here is the shape claim, with its counterexample attached. Each coloured curve is a different step distribution, standardised — shifted and scaled so only its shape remains — as the number of steps grows.

Three step distributions with nothing in common — a two-point coin, a flat interval, a heavy-tailed draw — collapse onto the dashed Gaussian as the number of steps grows. The fourth curve, in violet, is a walk whose steps are correlated; it is standardised by the same formula and stays stubbornly too wide. That curve is the point of the module as much as the other three are.

Model specification

System: $N$ independent walkers on an unbounded line; each position is the running sum of that walker’s own steps, and the observables are the ensemble histogram, its mean and its spread.
Dynamics: at each tick every walker adds one fresh draw from the step distribution, independent across walkers and across time.
Boundary: none — the line is unbounded, and $N$ , the number of steps and the step distribution are fixed for one run.
Ensemble: independent trials; each walker repeats the same experiment and nothing interacts with anything else.
Ignored: everything physical — no medium, no collisions, no energy, no units. By design, so that nothing physical can be doing the work.
Valid when: the steps are genuinely independent and have finite variance; a seeded pseudo-random generator satisfies both by construction.
Failure modes: correlated steps (the module’s own counterexample), infinite-variance steps such as Cauchy, and any question about one walker’s individual path beyond its distribution.

Three things are worth doing before you read on:

Watch one walker for 1000 steps, then watch 10,000 of them. Note what changed and what did not.
Switch the step distribution from the coin to the uniform draw and back. Watch the width change and the shape not change.
Push the persistence slider up from 0 and find the value at which the curve visibly stops matching the Gaussian.

Derive the result¶

Everything below is mathematics. Nothing is approximated except where it says so.

System and boundary. One walker on an unbounded line, and behind it an ensemble of $N$ independent copies. There is no boundary: nothing reflects, absorbs or confines.

Independent variables. The number of steps $t$ , the number of walkers $N$ , and the step distribution — which enters only through its mean $\mu_1$ and variance $\sigma_1^2$ .

Constraints and approximations. Steps are independent and identically distributed with finite variance. That is the whole list, and each item is load-bearing: the verify section breaks the first one on purpose and the problem set breaks the third.

Kind of argument. Purely statistical. There is no sign convention to fix and no differential to call exact or inexact, because no energy, heat or work appears anywhere in this module — which is the point of putting it here, before any of them exist.

With that settled, a walker’s position after $t$ steps is

x_t = s_1 + s_2 + \cdots + s_t ,

(1)

where the steps $s_i$ are independent draws from one fixed distribution with mean $\mu_1$ and variance $\sigma_1^2$ . That is the entire model: a position is a sum of independent draws.

The width: means and variances add¶

Module 0 established the two facts we need, and we do not re-derive them here.

Applying both to the sum of $t$ identical, independent steps:

\langle x_t \rangle = \mu_1 t , \qquad \operatorname{Var}(x_t) = \sigma_1^2 t , \qquad \sigma_{x_t} = \sigma_1 \sqrt{t} .

(3)

There is the width law, and there is the answer to prediction 1: after 100 coin steps ( $\mu_1 = 0$ , $\sigma_1 = 1$ ) the typical distance from the start is $\sqrt{100} = 10$ . Not 0, because the walk does spread; not 100, because the steps cancel far more often than they conspire.

Notice that the mean and the spread grow at different rates and for different reasons. For a fair coin $\mu_1 = 0$ , so the cloud spreads without going anywhere. For a biased coin the centre marches linearly while the width still only crawls as $\sqrt{t}$ , and by $t = 1000$ the drift has left the spread far behind. That answers prediction 3: widening and drifting are independent, and a cloud can do either without the other.

The coin walk is exactly binomial¶

For $\pm 1$ steps we can do better than the first two moments and write down the whole distribution. In $n$ steps, let $k$ be the number taken to the right. The walker’s position is

x = k - (n - k) = 2k - n ,

(4)

and $k$ is the number of successes in $n$ independent trials.

That last sentence is worth pausing on, because module 8 is built on it. The reason the middle of the histogram is tall is not that the walker prefers the middle. Every individual sequence of $n$ coin flips is exactly as likely as every other. There are simply astronomically more sequences with roughly equal numbers of lefts and rights than sequences with all rights.

From binomial to Gaussian: de Moivre–Laplace¶

Factorials are awkward and they hide the shape. Take the logarithm of $P(k)$ , expand it to second order about its maximum at $k = np$ , and exponentiate. With $q = 1 - p$ :

\binom{n}{k} p^{k} q^{n-k} \;\approx\; \frac{1}{\sqrt{2\pi n p q}} \exp\!\left[-\frac{(k - np)^2}{2 n p q}\right] .

(6)

At $n = 100$ , $p = 1/2$ the approximation gives the peak height

\frac{1}{\sqrt{2\pi n p q}} = \frac{1}{\sqrt{50\pi}} \approx 0.0798 ,

(7)

against the exact binomial value 0.0796 — an error of a quarter of a percent. Work this one out by hand once; it is the number the quiz asks for, and it is the first time in this course that a factorial-free formula reproduces a combinatorial one.

The shape: the central limit theorem¶

De Moivre–Laplace is one distribution’s story. The remarkable fact is that the answer does not depend on the step distribution at all.

Central limit theorem

Let $s_1, \ldots, s_n$ be independent, identically distributed random variables with finite mean $\mu_1$ and finite variance $\sigma_1^2$ , and let $S_n = s_1 + \cdots + s_n$ . Then the standardised sum

Z_n = \frac{S_n - n\mu_1}{\sigma_1 \sqrt{n}}

(8)

converges in distribution to a standard Gaussian $\mathcal{N}(0,1)$ as $n \to \infty$ .

The hypotheses are the content. Independent. Identically distributed. Finite variance. Nothing is assumed about the shape of the step distribution, and nothing about it survives into the limit: only $\mu_1$ and $\sigma_1$ appear in the answer, and they only say where the Gaussian sits and how wide it is.

The proof — characteristic functions, or a moment expansion — is beyond the core of this course; a sketch is in the advanced section. What matters here is the statement, because the statement is what you will use, and the hypotheses are what you will have to check.

Standardising is the whole trick, and it is worth saying plainly what it does. Subtracting $n\mu_1$ removes the drift; dividing by $\sigma_1\sqrt{n}$ removes the width. Whatever is left is pure shape — and the theorem says the shape is always the same one.

Deviation and error are different quantities¶

One more definition, small and constantly misused.

This is the sentence that ties the module to every laboratory that follows. When a later notebook reports a measurement as value ± error, that error is a standard error, and the $\sqrt{N}$ under it comes from here.

Verify computationally¶

Deriving a formula and trusting it are different things. Each check below is also a test in the project’s suite, so the claims on this page cannot silently rot.

1. The width law. Measure the cloud’s spread at $t = 4, 16, 64, 256, 1024$ and fit $\sigma \propto t^{\alpha}$ on log-log axes. The fitted exponent is 0.500 to within 0.02, and the coefficient comes out at $\sigma_1$ for each of the four step distributions — the exponent is universal, the coefficient is not.

2. Mean and spread, separately. The ensemble mean of an unbiased walk stays at zero to within its own standard error while the spread grows by a factor of eight; a biased walk drifts linearly at $\mu_1 t$ beside a spread that still only grows as $\sqrt{t}$ .

3. De Moivre–Laplace. The worst-case gap between the exact binomial and its Gaussian, measured across the central three standard deviations, shrinks steadily from $n = 25$ to $n = 400$ .

4. The collapse. This is the answer to the opening puzzle.

What the collapse measures

Standardised sums of coin, uniform and heavy-tailed steps are compared with a standard Gaussian using the largest gap between their cumulative distributions. All three distances fall as the number of summed terms grows. Against the floor of 0.006 set by having only 20,000 samples — the distance a genuine Gaussian sample of that size sits from the Gaussian it was drawn from — the heavy-tailed steps reach 0.004 by $n = 256$ , the uniform steps 0.012, and the coin 0.029.

The coin is the interesting one, and it does not get better by adding samples. Its sums live on a lattice, so its cumulative distribution is a staircase and a smooth curve can never match it more closely than half a step. That residual falls as $n^{-1/2}$ — it is the same finite- $n$ lattice effect the approximation box above describes, not a failure of the theorem, and it is why the honest statement is “these two distributions have reached the sampling floor and the third is still walking down towards it”.

Three distributions with nothing in common produce one curve. That agreement is a measurement, not a proof; the proof is the theorem above.

5. The counterexample. Now break a hypothesis on purpose. Give the walk persistence: at each step it repeats its previous step with probability $q$ , and otherwise draws afresh. The steps are still identically distributed and still have finite variance; only independence is gone.

Independence is a hypothesis, not a decoration

Standardised by the same independent-step formula $\sigma_1 \sqrt{n}$ , the persistent walk at $q = 0.9$ sits far from the standard Gaussian and stays there as $n$ grows — the distance stops falling instead of shrinking to the sampling floor.

It is worth being precise about what broke. The shape is not ruined; the walk is still Gaussian at long times. What is wrong is the width, by a factor

\frac{\operatorname{Var}(x_t)}{t} \longrightarrow \frac{1 + q}{1 - q} ,

(10)

which is 19 at $q = 0.9$ . Successive steps are correlated, so variances no longer simply add and the formula $\sigma_1\sqrt{t}$ underestimates the spread by a factor of $\sqrt{19}$ . The theorem was not wrong; it was applied where its hypothesis does not hold.

Transfer the idea¶

Multiplicity, in module 8. The coin walk’s $P(k)$ is the two-box multiplicity fraction $\Omega(N, n)/2^N$ — the same binomial, read as a count of microstates rather than a count of routes. The sharp peak that makes a gas stay spread out through the room, and its relative width $N^{-1/2}$ , are de Moivre–Laplace applied to particles.
Pressure, in module 4. The steady pressure of a gas is an average over an enormous number of collisions, and its jitter falls as $N^{-1/2}$ . That module measured the width; this one supplies the shape, and the reason the shape does not depend on the details of a collision.
Diffusion, in module 18. Let the step size and the time between steps go to zero together and the walker cloud’s density obeys the diffusion equation. The $\sqrt{t}$ spread is why a drop of ink takes minutes to cross a centimetre and years to cross a metre.
A Galton board. Beads falling through a triangular array of pegs, going left or right at each one, pile up in a bell curve at the bottom. It is de Moivre–Laplace built out of wood, and it works whether or not anyone has proved the theorem.
Every error bar you will meet. Polls, laboratory measurements, and every value ± error in this course quote a standard error. A poll of 1000 people has a margin near $3\%$ regardless of the size of the country, because $1/\sqrt{1000} \approx 0.032$ .

Check your understanding¶

A walker takes 400 steps of +1 or -1, each direction equally likely. Roughly how far from the starting point would you typically find him? Give the RMS displacement, sigma_1 sqrt(t), in steps.
Check your answer
Correct answer: 20 (± 1)
Var(x_t) = sigma_1^2 t with sigma_1 = 1, so the typical distance is sqrt(400) = 20 steps. Not 0 — the walk does spread. Not 400 — that is the distance he would cover if every step went the same way, and the steps cancel far more often than they conspire.
After 500 steps, one particular walker is standing at position +30. Over his next 500 steps, what is his expected displacement from where he now stands?
A. Zero — his next 500 steps are drawn from exactly the same distribution as anyone else’s. B. About -30, bringing him back to the origin on average. C. About -30 divided by 500, since the return is spread over the remaining steps. D. About +30, since a walker who has drifted right is evidently a rightward drifter.
Check your answer
Correct answer: A — Zero — his next 500 steps are drawn from exactly the same distribution as anyone else’s.
- A. Right. Nothing in the model refers to the origin. The step distribution does not know where the walker is, so his future is symmetric about his present position no matter how far out he has strayed.
- B. This is the restoring-force picture, and there is no force here. A walker at +30 would have to consult his own position to know to move left, and nothing in the model lets him. The ensemble mean stays at zero because walkers who stray right are matched by walkers who stray left — not because any individual is recalled.
- C. Same restoring-force idea with the arithmetic rearranged. Any nonzero expected displacement would require the step distribution to depend on position, and it does not.
- D. The steps are independent and identically distributed, so past steps carry no information about future ones. There is no such thing as a “rightward drifter” in this model — only a walker who happens to have had more rights so far.
For a binomial distribution with n = 100 trials and p = 1/2, compute the standard deviation of the number of successes, sqrt(n p (1-p)).
Check your answer
Correct answer: 5 (± 0.2)
sqrt(100 x 0.5 x 0.5) = sqrt(25) = 5. So the number of heads in 100 flips sits at 50 +/- 5 about 68% of the time. Note that the walker’s position is x = 2k - n, whose spread is therefore 2 x 5 = 10 = sqrt(100), consistent with sigma_1 sqrt(t).
Which of the following is NOT a hypothesis of the central limit theorem as stated in this module?
A. The individual steps must themselves be Gaussian. B. The steps must be independent of one another. C. The steps must all be drawn from the same distribution. D. The step distribution must have a finite variance.
Check your answer
Correct answer: A — The individual steps must themselves be Gaussian.
- A. Correct — and this is the whole point of the theorem. If the steps had to be Gaussian already, the result would be a triviality. The steps may be coins, uniform draws, or anything else with a finite variance; the Gaussian appears in the sum regardless.
- B. This is a genuine hypothesis, and the one the module’s persistent walk breaks. It is what allows variances to add.
- C. This is a genuine hypothesis of the version stated here. (Weaker conditions exist which relax it, but they are not what this module claims.)
- D. This is a genuine hypothesis, and problem 8 of the problem set explores what a Cauchy step distribution — which has no finite variance — does to the conclusion.
A walk repeats its previous step with probability 0.9 and otherwise draws a fresh +/-1 step. Its standardized sums, divided by sigma_1 sqrt(n), are compared with a standard Gaussian for growing n. What happens, and why?
A. The histogram stays far too wide at every n, because independence fails and variances no longer simply add. B. The histogram collapses onto the Gaussian anyway; only more steps are needed. C. The histogram becomes visibly non-bell-shaped — two peaks appear. D. Nothing changes, since the steps are still +/-1 with equal probability.
Check your answer
Correct answer: A — The histogram stays far too wide at every n, because independence fails and variances no longer simply add.
- A. Exactly. The steps are still identically distributed with finite variance; only independence is gone. The true variance is t(1+q)/(1-q) = 19t rather than t, so dividing by sigma_1 sqrt(n) undershoots the width by a factor sqrt(19).
- B. It does not. This is the “any sum of many random things is Gaussian” reflex, and the persistent walk exists to falsify it. The distance to the standard Gaussian stops falling instead of shrinking to the sampling floor, however large n gets.
- C. The shape is not what breaks. At long times the persistent walk is still Gaussian; it is the width that the independent-step formula gets wrong. Standardizing by the correct variance makes it collapse perfectly.
- D. The marginal distribution of a single step is indeed unchanged — that is what makes this counterexample sharp. The joint distribution is what changed, and the theorem is a statement about the joint distribution.
Use the de Moivre-Laplace approximation to estimate the probability of exactly 50 heads in 100 fair coin flips. That is, evaluate 1/sqrt(2 pi n p q) at n = 100, p = q = 1/2.
Check your answer
Correct answer: 0.0798 (± 0.0005)
1/sqrt(2 pi x 100 x 0.25) = 1/sqrt(50 pi) = 0.0798. The exact binomial value is 0.0796, so the approximation is off by about a quarter of a percent — near the peak. Try the same comparison at k = 90 and the relative error is enormous: this is a statement about the central region, not the tails.
You watch a cloud of unbiased walkers and see it getting steadily wider. What is its average position doing?
A. Staying at zero, within an uncertainty of order sqrt(t/N) that itself grows. B. Growing, since a wider cloud must have a larger average position. C. Growing as sqrt(t), the same as the width. D. Impossible to say without knowing the step distribution.
Check your answer
Correct answer: A — Staying at zero, within an uncertainty of order sqrt(t/N) that itself grows.
- A. Right, and the caveat matters. The mean stays at zero, but our estimate of it is only good to the standard error sigma_1 sqrt(t) / sqrt(N) — which is why the animation draws a widening grey band around zero rather than a bare line.
- B. Width and mean are separate quantities. The cloud grows symmetrically: walkers who wander right are matched by walkers who wander left, so the mean stays put while the spread grows as sqrt(t). A biased walk shows the contrast — there the mean really does march, linearly, while the width still only crawls.
- C. For an unbiased walk the mean does not grow at all: <x_t> = mu_1 t and mu_1 = 0. The sqrt(t) belongs to the spread alone.
- D. It is entirely determined: <x_t> = mu_1 t for any step distribution, so “unbiased” (mu_1 = 0) already fixes the answer at zero regardless of the shape of the steps.
You quadruple the number of measurements in a sample, from N to 4N. What happens to the standard deviation of the data, and to the standard error of their mean?
A. The standard deviation is unchanged; the standard error halves. B. Both halve. C. Both are unchanged. D. The standard deviation halves; the standard error is unchanged.
Check your answer
Correct answer: A — The standard deviation is unchanged; the standard error halves.
- A. Correct. The standard deviation describes the population and does not care how much of it you looked at. The standard error, sigma_1/sqrt(N), describes your uncertainty about the mean, and sqrt(4) = 2.
- B. Measuring more of a population does not make the population less variable. If it did, you could make any quantity precise by measuring it often enough — and the scatter of the individual values would visibly shrink, which it does not.
- C. The standard deviation is unchanged, but the whole point of averaging is that the mean becomes better determined. If the standard error did not shrink, there would be no reason to repeat a measurement at all.
- D. This has the two quantities exactly the wrong way round. It is worth writing both definitions out side by side: one is a property of the data, the other a property of your estimate.
Ten thousand independent walkers produce a smooth, reproducible bell-shaped histogram. Which account of where that order comes from is correct?
A. Astronomically more step sequences land near the middle than at the extremes, and every sequence is equally likely. B. Walkers who have strayed too far are pulled back, which keeps the distribution centred. C. The walkers’ steps average out to zero, so each walker ends up near the origin. D. With enough walkers, an excess on one side is compensated by later walkers landing on the other.
Check your answer
Correct answer: A — Astronomically more step sequences land near the middle than at the extremes, and every sequence is equally likely.
- A. Yes. The order is a counting fact, not a dynamical one. Nothing steers a walker, and no walker knows about any other; the shape is simply what you get when you count how many routes arrive at each destination.
- B. There is no such mechanism, and the laboratory falsifies it directly: condition on the walkers standing at +30 and their subsequent motion is symmetric. Convergence here works by dilution, never by correction.
- C. Each walker does not end up near the origin — the typical distance is sigma_1 sqrt(t), which grows without bound. What settles down is the ensemble’s shape, not any individual’s position.
- D. The walkers are independent, so no walker can compensate for another; a later walker has no way to learn what the earlier ones did. This is the compensation fallacy from module 0, transplanted from time into the ensemble.
A walker takes 400 steps of +/-1, but the coin is biased: p = 0.6 to the right. Compute his expected displacement, mu_1 t, in steps.

Exam-style problems for this module — the ones worth doing with a pen — are collected in the problem set.

Explain it in your own words¶

Answer in a few sentences each. No number will save you here.

A student says: “The walk comes back toward zero because steps to the left cancel steps to the right.” Part of that sentence is right and part is badly wrong. Separate them.
The persistent walk has identically distributed steps with finite variance, and its histogram is still not the predicted Gaussian. Which hypothesis of the central limit theorem fails, and what exactly does its failure cost?
A pollster’s margin of error shrinks as more people are surveyed, while the raw scatter in the number of votes counted grows. Explain how both can be true at once.
Explain, without writing an equation, why the shape of the long-time histogram does not depend on what a single step looks like — and name the one thing about the step that does survive.

Advanced: three loose ends¶

Why the theorem is true. The mechanism is easiest to see through the characteristic function $\varphi(k) = \langle e^{ikX}\rangle$ , which turns sums into products: the characteristic function of a sum of independent variables is the product of theirs. Standardise so that $\mu_1 = 0$ and $\sigma_1 = 1$ , and expand for small $k$ :

\varphi(k) = 1 - \tfrac{1}{2}k^2 + o(k^2) \quad\Longrightarrow\quad \left[\varphi\!\left(\frac{k}{\sqrt{n}}\right)\right]^{n} \longrightarrow e^{-k^2/2} .

(11)

The limit is the characteristic function of a standard Gaussian. Read the calculation backwards and you can see exactly what each hypothesis was for: independence let the characteristic functions multiply, identical distribution let one $\varphi$ serve for all $n$ factors, and finite variance is what makes the $k^2$ term exist and be the leading one. The whole theorem is the statement that only the quadratic term survives the rescaling.

Walks in two dimensions. Give each walker an independent step in $x$ and in $y$ . Every result above applies to each coordinate separately, so the mean-square distance from the origin is the sum of two identical contributions,

\langle r_t^2 \rangle = \langle x_t^2 \rangle + \langle y_t^2 \rangle = 2\sigma_1^2 t ,

(12)

and the cloud is a circular Gaussian widening as $\sqrt{t}$ . The picture is prettier and the mathematics is the same one twice, which is why the core sticks to a line.

The persistent walk recovers. The counterexample above is a broken width, not a broken shape, and the repair is exact. Successive steps of the persistent walk have correlation $q^j$ at separation $j$ , so summing the covariance matrix instead of just the diagonal gives

\operatorname{Var}(x_t) = t\left(1 + 2\sum_{j=1}^{\infty} q^{\,j}\right) = t\,\frac{1+q}{1-q}

(13)

in the long-time limit. Substituting this variance in place of $\sigma_1^2 t$ makes the standardised histogram collapse onto the Gaussian after all. The general statement — a central limit theorem for sequences with decaying correlations — is what lets statistical mechanics use Gaussian fluctuation formulas for systems whose particles very much do interact, provided the correlations die away fast enough.