A random walk spreads as 2Dt and turns Gaussian

Every tolerance is a multiple of a measured spread. The reference, posts/refs/a-random-walk-becomes-diffusion.py, runs the same experiment 2000 times with numpy's own random numbers and reports how much each quantity varies from run to run; the tests allow three of those spreads. It also replays this run draw for draw (Viv's rand() is the Park-Miller generator, which Python can reproduce exactly), so the numbers this program prints are checked as well as the statistics behind them.

From steps to a diffusion constant

Diffusion is what a drop of ink does in still water: it spreads, and the width of the spread grows as the square root of time. The equation for the concentration $c(x,t)$ is ${\partial }_{t}c=D{\partial }_x^{2}c$, and a drop that starts at one point becomes a Gaussian of variance $2Dt$. The constant $D$, the diffusion constant, is a property of the ink and the water.

This program shows where $D$ comes from. Each walker starts at $x=0$ and every $\Delta t=0.01$ moves by a random step, drawn evenly from $[-a,a]$ with $a=0.1\sqrt{3}$, so a step has mean 0 and variance ${\sigma }^2=a^2/3=0.01$. Steps are independent, so after $n$ steps the variances add: $⟨x^2⟩=n{\sigma }^2$. Writing $t=n\Delta t$,

The mean squared displacement (MSD) grows linearly, and its slope is $2D$. Nothing about the shape of one step enters, only its variance.

The MSD against $2Dt$

How far should the measured MSD be from $2Dt$? It is an average of 4000 values of $x^2$, so its standard error is $\sqrt{\mathrm{Var}(x^2)/4000}$. For a sum of $n$ uniform steps, $\mathrm{Var}(x^2)=2n^2{\sigma }^4-\frac{6}{5}n{\sigma }^4$ (the $\frac{6}{5}$ is the uniform distribution's fourth cumulant), which gives 0.045 at step 200. The reference's 2000 runs spread by 0.0451 there, so the formula holds. The tests allow three standard errors at steps 50, 100, 150 and 200.

The slope is fitted by least squares through the origin, $D=\sum t\mathrm{MSD}/(2\sum t^2)$, using all 200 steps. The reference's runs give it a spread of 0.0098.

How the spread becomes Gaussian

After one step the walkers are spread evenly over $[-a,a]$: a flat distribution, not a bell. The central limit theorem says the sum of many independent steps is Gaussian whatever one step looks like, and the diffusion equation's solution is that Gaussian. How fast does the flat shape wear off?

A number that measures it is the excess kurtosis, $⟨x^4⟩/⟨x^2{⟩}^2-3$. It is zero for a Gaussian, and $-1.2$ for a flat distribution, whose tails are cut off. For a sum of $n$ independent steps it is exactly $-1.2/n$: the fourth cumulant grows as $n$, the squared variance as $n^2$. Before running: at which step does the measured value stop being distinguishable from zero? The reference's runs put the noise on a 4000-walker estimate at about $0.07$, so after about 16 steps the $-1.2/n$ signal is below the noise.

The histograms

The last cell sorts the walkers into 24 bins spanning three standard deviations each side, after step 1 and after step 200, and draws each over the Gaussian with the same variance. Each bar is $\pm \sqrt{\text{count}}$, the Poisson spread of a count.

The agreement at step 200 is measured by Pearson's chi-square, ${\chi }^2=\sum (O-E{)}^2/E$ over the bins, with $E$ the count the Gaussian predicts. For 24 bins it averages about 24 when the Gaussian is right; the test allows $24+3\sqrt{48}=44.8$, which a correct Gaussian exceeds 0.6% of the time (the ${\chi }^2$ distribution's tail; 0.25% of the reference's runs did). After one step the same statistic is over a thousand.

The flat distribution after one step sits under the bell in the middle and is zero beyond $\pm \sqrt{3}$ standard deviations; after 200 steps the points follow the curve bin by bin, within their bars.