Interactive guide · Probability in Action

Random walks, Poisson processes, Brownian motion

Everything so far has treated randomness as a fixed distribution you draw from. This part turns the clock on. A random walk is what you get when a coin flip decides the next step, and its most important fact is not where it goes but how far: after n steps the spread grows like $\sqrt{n}$ . Rescale that walk by exactly $1/\sqrt n$ and something remarkable happens — the jagged staircase converges to a continuous but nowhere-smooth curve, Brownian motion, which is the noise underneath diffusion, thermal physics and financial models. In continuous time the same coin flips become a stream of events: exponential gaps between arrivals that add up to Poisson counts. And through all of it runs a single structural idea, the martingale, the formal statement of a fair game. Once you have martingales you can ask the most useful question in applied probability — can I stop the game early and still expect to break even? — and learn exactly when the answer is yes.

The question

What does randomness do over time?

A single random variable is a snapshot. A stochastic process is a movie: a family of random variables indexed by time, (X_t), so that the joint behaviour at different times tells you how the randomness flows. The smallest interesting movie is a coin that decides your position. Start at zero. At each tick flip a fair coin; heads steps you right, tails steps you left. After n ticks you are at some integer S_n, and the sequence $S_0,S_1,S_2,\dots$ is the simple random walk.

The surprise is how much structure that trivial rule generates. The walk has no memory — where it goes next is independent of everything before — yet its large-scale shape is rigid. Its width grows like $\sqrt n$ , not like n, because the steps cancel one another on average; the variance adds, n is the sum of n unit variances, and the standard deviation is the square root. That one exponent governs diffusion, error accumulation in sensors, and the rate at which Monte Carlo estimates improve.

Continuous time changes the question from "where am I" to "when does something happen". If events arrive at a constant average rate $\lambda$ with independent exponential gaps, the process is a Poisson process, and the number of arrivals in a window of length t is Poisson with mean $\lambda t$ . Zoom out from the discrete walk and the same limiting object appears: Brownian motion, the continuous, jagged path whose increments are independent Gaussians. It is what the walk becomes after you rescale time and space so that neither the step size nor the step rate distorts the picture.

Underneath all three sits the idea of a fair game. If the expected next value of a process equals its current value given everything you know, the process is a martingale. A fair coin walk is one, and so are many natural transformations of it. The practical question is whether you can read a martingale at a random stopping time without changing its expectation. The optional stopping theorem says yes under boundedness conditions, and the best way to trust a theorem is to watch it fail the moment you drop them.

💡 By the end of this part you'll see why a walk's spread is $\sqrt n$ and not n, why exponential gaps produce Poisson counts, how rescaling turns a staircase into Brownian motion, and why $\mathbb{E}[X_\tau]=\mathbb{E}[X_0]$ holds for a bounded stopping rule and breaks for an unbounded one.

2 · The simple random walk and √n scaling 3 · The Poisson process 4 · The Brownian limit 5 · Martingales and optional stopping 6 · Where this shows up 7 · Cheat sheet 8 · Further reading

The simple random walk and √n scaling

Independent steps, a rigid width

Write the steps as $X_1,X_2,\dots$ , each taking the value +1 or -1 with probability one half, independent of the rest. The position after n steps is their sum, $S_n=X_1+\cdots+X_n$ . Each step has mean zero and variance one, so the mean of the sum is zero and the variances simply add. The whole large-scale theory of the walk is contained in that one line.

\mathbb{E}[S_n]=0,\qquad \operatorname{Var}(S_n)=n,\qquad \operatorname{sd}(S_n)=\sqrt{n},\qquad \frac{S_n}{\sqrt{n}}\;\xrightarrow{\;d\;}\;\mathcal{N}(0,1).

The variance identity is why the walk's typical distance from the origin grows like $\sqrt n$ and not like n. It is also the first place the central limit theorem shows its face: the normalised position $S_n/\sqrt n$ has mean zero and variance one for every n, and as n grows its distribution flattens into the standard bell curve. The walk is built from bounded steps with no dominating term, which is exactly the hypothesis the CLT needs. The central limit theorem part of the elementary volume tells that story properly; here it is the bridge from the discrete staircase to the smooth noise of the next sections.

Drag the step count and reseed the sample below. Each faint blue curve is one walk of n steps; the bold one is called out so you can follow a single path. The two dashed magenta curves are the envelope $\pm\sqrt n$ . They are not a wall — the walk crosses them all the time, since the standard deviation is only about one envelope width — but they set the scale. Double the number of steps and the envelope grows by only about forty percent, because $\sqrt{2n}/\sqrt n=\sqrt 2$ . That square root is the reason long-run averages improve so slowly, and the reason a random error budget grows with the square root of elapsed time rather than with time itself.

Twenty-four seeded walks of the same length. The dashed magenta envelope is $\pm\sqrt{n}$ ; the bold line is one walk, so you can watch a single path wander inside the envelope while the others fan out.

Steps 300

Now let the walk move on a plane, choosing $\pm 1$ independently in each coordinate at every tick. The result is the two-dimensional walk on the canvas below, and the dashed circle of radius $\sqrt n$ is its scale. The single most striking difference from one dimension is not visible in a picture: the 1D and 2D walks both return arbitrarily close to the origin infinitely often, while the 3D walk escapes and never comes back. The $\sqrt n$ radius keeps growing in every dimension, but in three dimensions the space outgrows the walk's tendency to revisit. Lady Luck is transient in 3D and recurrent in 1D and 2D, a fact that surprises almost everyone and is proved by comparing the walk with an electrical network.

A seeded 2D walk: each tick moves one unit horizontally and one vertically, each sign chosen by a coin. The dashed circle has radius $\sqrt{n}$ , the typical distance from the start.

The Poisson process

Exponential gaps, Poisson counts

Discrete steps in time become a continuous stream when you stop asking "one tick at a time" and start asking "when is the next event". The Poisson process is the canonical answer. Fix a rate $\lambda>0$ , the average number of events per unit time. The waiting time until the first event is exponential with rate $\lambda$ , and after an event the clock resets: the next wait is again exponential, independent of everything before. The process is defined entirely by those iid gaps, and the defining property is memorylessness — the chance of an event in the next instant does not depend on how long you have already waited.

W_i\sim\operatorname{Exp}(\lambda)\ \text{iid},\qquad \mathbb{E}[W_i]=\frac{1}{\lambda},\qquad N(t)=\max\{k:W_1+\cdots+W_k\le t\}\sim\operatorname{Poisson}(\lambda t),

Counting and waiting are two views of the same object. The number of events up to time t, N(t), is the largest k whose cumulative gap still fits inside t. Because the gaps are iid exponential, that count is Poisson with mean $\lambda t$ , so its distribution is

\mathbb{P}\bigl(N(t)=k\bigr)=e^{-\lambda t}\,\frac{(\lambda t)^k}{k!},\qquad \mathbb{E}[N(t)]=\operatorname{Var}\bigl(N(t)\bigr)=\lambda t.

The equality of mean and variance is a fingerprint of the Poisson family and a quick sanity check in any simulation. It also carries the process's independence: the numbers of arrivals in disjoint time windows are independent Poisson variables, which is why N(t) has independent increments. Two more operations round out the toolkit. Superposition says merging two independent Poisson processes of rates $\lambda$ and $\mu$ gives one of rate $\lambda+\mu$ . Thinning says keeping each arrival independently with probability p leaves a Poisson process of rate $p\lambda$ . Arrivals get added and filtered without ever leaving the family.

The timeline below draws the exponential gaps directly: the alternating shaded intervals are the waiting times, and the ticks are the event times. Raise the rate and the events crowd together; lower it and long gaps appear. The readout reports the observed count in the drawn window and the mean gap, which should hover near $1/\lambda$ . The histogram beside it is the second half of the story. Thousands of independent windows of length L are simulated, the number of events in each is counted, and those counts are binned. The magenta bars are the Poisson pmf with mean $\lambda L$ . They sit on the histogram for every rate and every window length, which is the theorem made visible.

Waiting times are exponential: shade widths are the gaps between consecutive events, drawn from $\operatorname{Exp}(\lambda)$ .

Rate λ 2

Window length L 1

Counts in four thousand windows of length L (blue histogram) against the Poisson pmf with mean $\lambda L$ (magenta bars). The two should coincide.

Notice what thinning and superposition buy you in modelling. If a server receives requests at rate $\lambda$ and each is a cache miss with probability p, misses form a Poisson process of rate $p\lambda$ ; if two independent sources feed the same queue, the combined arrivals are Poisson of the summed rate. The family is closed under the operations you actually use, which is why the Poisson process is the default null model for event data in queueing, networking, particle physics and insurance.

The Brownian limit

Rescale the staircase until it becomes smooth noise

Take the simple walk and squeeze its steps together in time while shrinking them in space. Concretely, run the walk for n steps and read it at the rescaled time $t\in[0,1]$ by

B^{(n)}_t=\frac{S_{\lfloor nt\rfloor}}{\sqrt{n}},\qquad\text{so}\qquad B^{(n)}_t\;\xrightarrow[\;n\to\infty\;]{}\;B_t,\qquad B_t\sim\mathcal{N}(0,t).

Two factors are doing opposite jobs. The $1/\sqrt n$ keeps the vertical size fixed, since the walk has spread $\sqrt n$ by the end; without it the path would blow up. Smoothing over the n steps fills the horizontal axis densely, so the staircase's corners get closer together. In the limit the corners become so dense that the path is continuous, but it is nowhere differentiable: at every scale it still looks like the same jagged walk. The limit object is Brownian motion, and its increments are independent Gaussians with $B_t-B_s\sim\mathcal{N}(0,t-s)$ for s. That is the exact continuum version of "independent steps, variance adds", and the CLT is what makes the Gaussian appear.

The slider below is a refinement dial. At low k the walk is a coarse staircase with visible corners. As k rises and the number of steps n=2^k grows, the same rescaled ensemble tightens onto a fixed cloud of continuous curves. The paths never become smoother in the usual sense — zoom into any piece of Brownian motion and it looks just as rough as the whole — but the spacing between the corners vanishes and the jump sizes shrink, so the eye sees a continuous random function. This is the sense in which Brownian motion is the universal limit of walks: many microscopic rules, one macroscopic object.

Eight walks rescaled by $1/\sqrt n$ and read over $t\in[0,1]$ . Coarse corners at small k; a continuous random cloud as n=2^k grows.

Refinement k (n = 2^k) 8

Brownian motion earns its place because it is the noise source for a huge class of models. Adding a drift gives $X_t=\mu t+\sigma B_t$ , the arithmetic Brownian motion used as a first model for a diffusing particle or a stock's log price. Feeding the noise through a differential equation gives a diffusion, the object behind the heat equation, the Fokker–Planck equation and the stochastic calculus of the calculus-of-motion guide. Its paths have infinite variation — the total up-and-down distance is infinite over any interval — which is precisely why ordinary calculus fails on them and a new rule for changing variables, Itô's lemma, is needed. The rescaling picture above is the intuitive root of all of it.

Martingales and optional stopping

The fair game, and when you may leave it

A martingale is the formal statement of a fair game. Let X_t be your capital and $\mathcal{F}_s$ everything observable up to time s. The process is a martingale when your best prediction of the future, given the present, is the present itself:

\mathbb{E}\bigl[X_t\mid\mathcal{F}_s\bigr]=X_s\qquad\text{for all }s\le t,\qquad\text{equivalently}\qquad \mathbb{E}[X_{t+1}-X_t\mid\mathcal{F}_t]=0.

The fair coin walk is the prototype: after each flip the expected position is unchanged, so S_n is a martingale. So is S_n^2-n, because the variance grows at exactly one per step and subtracting n removes the drift from the square; that martingale is how you compute expected hitting times. And so is the exponential martingale $\exp(\theta S_n-n\theta^2/2)$ , the tool behind large-deviation bounds on the walk's range. Martingales are not rare; they are what you get whenever you correct a growing quantity by its predictable trend.

Now the useful question. Suppose you gamble until some rule tells you to stop, and the rule depends only on what has happened so far. The optional stopping theorem answers: under the right conditions you cannot beat a fair game by choosing a stopping time, and the expected capital at the stop equals the expected starting capital,

\mathbb{E}[X_\tau]=\mathbb{E}[X_0]\qquad\text{when }\tau\text{ is bounded, or when }X\text{ is bounded and }\tau\text{ has finite expectation.}

The conditions are not decoration. The demo runs two stopping rules on the same fair walk and tracks the running average of the payoff. In the first, you stop as soon as the walk reaches +A or -A. That stopping time is a.s. finite, the stopped capital is bounded by A, and the running average of the payoff converges to zero: the theorem holds. In the second, you stop the moment the walk first reaches +1. That happens almost surely, so every completed game pays exactly one unit, and the average over completed games sits at one — not zero. The theorem fails because this stopping time has infinite expectation; the walk can spend arbitrarily long on the negative side before climbing back. The third curve is the honest repair: cap the game at T steps and look at $X_{\tau\wedge T}$ . That is a bounded stopping time, and its average returns to zero. The break in optional stopping is not a paradox; it is the conditions doing their job.

Running mean of the payoff over games. The bounded barrier rule stays at zero. Stopping at the first +1 pays one unit every completed game, so its average climbs to one; capping at T restores the zero expectation.

Barrier A 5

Two habits are worth keeping. First, check the hypotheses before invoking optional stopping — a stopping time that looks innocent can have infinite mean, and unbounded capital can let a rare branch carry the expectation. Second, look for a martingale early: many questions about walks, queues and filters become one-line computations once the right compensated quantity is found, and S_n^2-n is the template for all of them. Part 10 takes the same "state and transition" view and drops the requirement that the next state be chosen by a coin; the Markov chain is the walk's more general cousin.

Where this shows up

Accumulated noise everywhere

Robotics

Drift in dead reckoning

When a robot integrates noisy velocity to track its pose, small independent errors pile up exactly like the steps of a walk. The position error grows with the square root of elapsed time, which is why odometry needs periodic correction from a global sensor and why loop closures matter so much.

Math

The CLT behind the limit

Brownian motion exists because $S_n/\sqrt n$ converges in distribution to a normal. That statement and its hypotheses are the work of the central limit theorem, which is the engine converting independent bounded steps into Gaussian noise.

AI / ML

Stochastic gradient noise

Each minibatch gradient is a noisy estimate, so the parameter path under stochastic optimisation is a random walk with drift, and the noise scale falls as batches grow. That relationship between batch size, step size and loss noise is central to training at scale.

Vision

Inertial integration for SLAM

An IMU's bias performs a slow random walk, and integrating its measurements compounds that error. Treating bias as a Brownian process and propagating its uncertainty is what makes visual-inertial SLAM work, and it is the same martingale bookkeeping in a different notation.

Cheat sheet

Every formula in one place

Idea	Formula	Reading
Simple random walk	$S_n=X_1+\cdots+X_n,\quad X_i=\pm1$	Independent fair steps; the canonical accumulated noise.
Mean and variance	$\mathbb{E}[S_n]=0,\quad \operatorname{Var}(S_n)=n$	Variances add, so the spread is $\sqrt n$ .
CLT scaling	$S_n/\sqrt n\Rightarrow\mathcal{N}(0,1)$	Normalised walk flattens into the bell curve.
Recurrence	1D and 2D recurrent; 3D transient	Space outgrows the walk only in three dimensions.
Poisson process	$N(t)\sim\operatorname{Poisson}(\lambda t)$	Count of events in a window of length `t`.
Poisson pmf	$e^{-\lambda t}(\lambda t)^k/k!$	Mean and variance both equal $\lambda t$ .
Exponential gaps	$W_i\sim\operatorname{Exp}(\lambda),\quad \mathbb{E}[W_i]=1/\lambda$	Memoryless waiting times between arrivals.
Brownian motion	$B_t\sim\mathcal{N}(0,t),\quad B_t-B_s\sim\mathcal{N}(0,t-s)$	Independent Gaussian increments; continuous, nowhere smooth.
Martingale	$\mathbb{E}[X_t\mid\mathcal{F}_s]=X_s$	Fair game: best forecast of the future is the present.
Optional stopping	$\mathbb{E}[X_\tau]=\mathbb{E}[X_0]$	Needs boundedness; breaks for $\tau=$ first hit of `+1`.

Check your understanding

0/6 answered