Random walks

A random walk is the simplest model of something that moves by chance. At every tick of the clock it takes a single step — +1 (right) with probability $p$, or −1 (left) otherwise — and we record where it is.

Tiny rule, surprisingly rich behaviour: random walks describe a diffusing molecule, a share price, a foraging animal, the error in a noisy measurement. In this lesson you'll watch one walk wander, then run thousands at once and see a smooth bell curve appear out of pure randomness.

Everything below the sliders runs in your browser as WebAssembly — no Julia server, no install. The randomness is a small hand-written generator (a linear congruential generator), so it compiles to plain integer arithmetic and every seed reproduces exactly the same walk.

begin
    using PlutoUI, WasmMakie
end

One walk, step by step

Move the sliders and the path below redraws instantly. steps is how long the clock runs, p tilts the coin toward the right, and seed picks which particular random walk you see.

steps = 120

p (probability of stepping right) = 0.5

seed = 7

path = let
    # one walk, computed inline (the Float `prob` is used directly in this cell —
    # threading it through a helper miscompiles under WasmTarget today)
    s = (seed * 2654435761 + 12345) % 2147483647   # an LCG state in [1, 2^31-1)
    if s == 0
        s = 1
    end
    xs = Vector{Float64}(undef, nsteps + 1)
    pos = 0.0
    xs[1] = pos
    for i in 1:nsteps
        s = (s * 16807) % 2147483647          # advance the Park-Miller generator
        u = Float64(s) / 2147483647.0         # a fraction in (0, 1)
        pos += u < prob ? 1.0 : -1.0
        xs[i + 1] = pos
    end
    xs
end;

let
    # the step index 0, 1, …, nsteps on the x-axis (integer loop — StepRangeLen
    # iteration is not wasm-compilable yet)
    steps_axis = Vector{Float64}(undef, nsteps + 1)
    for i in 0:nsteps
        steps_axis[i + 1] = Float64(i)
    end
    fig = Figure(size = (560, 320))
    ax = Axis(fig[1, 1])
    lines!(ax, [0.0, Float64(nsteps)], [0.0, 0.0])   # the starting height (0)
    lines!(ax, steps_axis, path)                      # the walk itself
    fig
end

After 120 steps this walk ended at position 0.0. Slide seed to meet a different walk, or p to bias the coin — at p = 1 it marches straight up, at p = 0 straight down, and at p = 0.5 it drifts aimlessly.

Many walks → the bell curve

One walk is unpredictable. But run many fair walks (an even coin, p = 0.5) and a clear pattern appears: the final positions pile up into a bell-shaped curve (a normal distribution) centred on 0. This is diffusion — the same mathematics behind why a drop of ink spreads evenly through water.

A key fact: the typical distance from the centre grows like √steps, not like steps — randomness spreads slowly. Drag walks up and watch the histogram fill in. (The one-walk sliders above still bias a single walk with p.)

number of walks = 600

let
    # Histogram of the final positions, drawn as vertical bars. We run all the walks
    # in ONE flat loop (a single RNG stream chopped into `nwalks` chunks of `nsteps`)
    # so the Float `prob` is only ever used at single-loop depth — the bonded value
    # currently miscompiles inside a doubly-nested loop under WasmTarget.
    lo = -Float64(nsteps)
    hi = Float64(nsteps)
    nbins = 41
    counts = Vector{Float64}(undef, nbins)
    for k in 1:nbins
        counts[k] = 0.0
    end
    s = 777
    pos = 0.0
    j = 0
    grand = nwalks * nsteps
    for t in 1:grand
        s = (s * 16807) % 2147483647
        u = Float64(s) / 2147483647.0
        pos += u < 0.5 ? 1.0 : -1.0     # fair coin (the standard diffusion demo)
        j += 1
        if j == nsteps           # one walk just finished — record where it landed
            tt = (pos - lo) / (hi - lo)
            b = Int64(floor(tt * (nbins - 1))) + 1
            if b < 1
                b = 1
            end
            if b > nbins
                b = nbins
            end
            counts[b] += 1.0
            pos = 0.0
            j = 0
        end
    end
    fig = Figure(size = (560, 320))
    ax = Axis(fig[1, 1])
    for k in 1:nbins
        center = lo + (hi - lo) * (k - 1) / (nbins - 1)
        lines!(ax, [center, center], [0.0, counts[k]])  # one bar
    end
    fig
end

rw_stats = let
    # mean and spread of the final positions, accumulated in ONE flat pass. Returns a
    # tuple so the markdown cell below can interpolate it: computing the numbers in a
    # SEPARATE bond-dependent cell is what makes the live readout track the sliders
    # (values buried inside a markdown cell's own `let` get baked to slider defaults).
    m_total = 0.0
    sq_total = 0.0
    s = 777
    pos = 0.0
    j = 0
    grand = nwalks * nsteps
    for t in 1:grand
        s = (s * 16807) % 2147483647
        u = Float64(s) / 2147483647.0
        pos += u < 0.5 ? 1.0 : -1.0     # fair coin (the standard diffusion demo)
        j += 1
        if j == nsteps
            m_total += pos
            sq_total += pos * pos
            pos = 0.0
            j = 0
        end
    end
    m = m_total / nwalks
    var = sq_total / nwalks - m * m
    if var < 0.0
        var = 0.0
    end
    sd = sqrt(var)
    expected = sqrt(Float64(nsteps))
    (floor(m * 100.0) / 100.0, floor(sd * 100.0) / 100.0, floor(expected * 100.0) / 100.0)
end;

Across 600 walks: mean final position is about 0.27, spread (standard deviation) is about 10.76.

For a fair walk (p = 0.5) the mean sits near 0 and the spread tracks sqrt(steps) = 10.95 – that's diffusion in one number.

Appendix

The original MIT lecture builds random walks with Julia's rand and the Distributions.jl / Plots.jl stack. WebAssembly can't run that machinery in the browser, so here the randomness is a hand-written linear congruential generator (pure integer arithmetic) and the picture is drawn with WasmMakie. The mathematics — Bernoulli steps, the √n spread, the emergent bell curve — is exactly the same.