# Random walks, and how far they get Put $n$ walkers at home, the origin. Every tick each one takes a step of length $s$ in a direction chosen at random, with no memory of the steps before. The question the picture asks is the one every diffusion problem asks: *after $n$ steps, how far from home is a typical walker?* The answer is not $ns$ and it is not $0$; it is proportional to $\sqrt{n}$, and the applet lets you watch that law appear out of nothing but coin flips. <div class="applet" data-applet="random-walk"></div> ## What one step does Write the $k$-th step as a vector $\mathbf v_k = (s\cos\theta_k,\; s\sin\theta_k)$. With **any heading** the angle $\theta_k$ is uniform on $[0, 2\pi)$, so $ \mathbb E[\cos\theta_k] = 0, \qquad \mathbb E[\cos^2\theta_k] = \tfrac12, \qquad \mathbb E[\cos\theta_k \sin\theta_k] = 0, $ and each step has mean $\mathbf 0$ and covariance $\tfrac{s^2}{2} I$. On the **lattice** the step is one of $(\pm s, 0)$, $(0, \pm s)$ with probability $\tfrac14$ each, which gives the *same* mean and the *same* covariance. That is why the two modes end up indistinguishable in the plots even though they look nothing alike early on. ## The exact law The position after $n$ steps is $\mathbf r_n = \sum_{k=1}^n \mathbf v_k$, and its squared distance from home is $ R_n^2 = |\mathbf r_n|^2 = \sum_{k=1}^n |\mathbf v_k|^2 + 2\sum_{j<k} \mathbf v_j\cdot\mathbf v_k . $ Every term in the first sum is $s^2$. Every cross term has expectation zero, because the steps are independent and each has mean zero. So $ \mathbb E\bigl[R_n^2\bigr] = n s^2, \qquad \sqrt{\mathbb E[R_n^2]} = s\sqrt n , $ exactly, at every $n$, in either mode. This is the teal **RMS R** curve in the first plot, and it is the one prediction that is not an approximation. Notice how it is obtained: the walkers do not cooperate to get anywhere, and the only thing that survives averaging is the sum of the squared step lengths. ## The limit shape Everything else uses the central limit theorem. The coordinates $x_n$ and $y_n$ are each a sum of $n$ independent pieces of variance $s^2/2$, so for large $n$ $ (x_n, y_n) \;\approx\; \mathcal N\bigl(\mathbf 0,\; \sigma^2 I\bigr), \qquad \sigma^2 = \frac{n s^2}{2}. $ The histogram (set it to $x$) shows this Gaussian settling over the bars. The distance $R = \sqrt{x^2 + y^2}$ of a two-dimensional Gaussian is **Rayleigh** distributed, with density $\dfrac{r}{\sigma^2}e^{-r^2/2\sigma^2}$ (set the histogram to $R$), and the Rayleigh moments give the three dashed curves: $ \mathbb E[R] \approx \sigma\sqrt{\tfrac{\pi}{2}} = \frac{s}{2}\sqrt{\pi n}, \qquad \operatorname{SD}(R) \approx \sigma\sqrt{\tfrac{4-\pi}{2}} = \frac{s}{2}\sqrt{(4-\pi)\,n}, \qquad \mathbb E|x| \approx \sigma\sqrt{\tfrac{2}{\pi}} = s\sqrt{\tfrac{n}{\pi}} . $ All of them grow like $\sqrt n$. The dashed ring in the world view is $\mathbb E[R]$; watch it expand at the pace the cloud does. ## What to check **The ratio that does not move.** Mean $R$ over RMS $R$ should sit at $\sqrt{\pi}/2 \approx 0.886$ for large $n$, whatever $s$ and $n$ are. Read both numbers off the readout at a few ticks. **Where the dashed curves are wrong.** At $n = 1$ every walker is at distance exactly $s$, so mean $R = s$ while the prediction says $0.886\,s$; and mean $|x|$ is $2s/\pi \approx 0.64\,s$ with any heading but exactly $s/2$ on the lattice. Step once from setup and compare the two modes. The predictions are asymptotic, and the applet is honest about the first few ticks. **The lattice shows in the histogram, then disappears.** Switch to **lattice**, set the histogram to $x$, and step a few times: the bars sit on multiples of $s$ with gaps between them (and $x + y$ is always an even or always an odd multiple of $s$, depending on the parity of $n$). By $n = 100$ the Gaussian has swallowed the fine structure. The step size $s$ is invisible in the limit except through $\sigma$. **Smoothness is a matter of $n$ walkers, not $n$ steps.** Run with 10 walkers and then with 2000. The solid curves are averages over the walkers, so their jitter shrinks like $1/\sqrt{\text{walkers}}$; the *slope* of the curves does not change at all. **Will they come home?** The readout counts walkers within one step of home. Pólya's theorem says a lattice walk in two dimensions returns to the origin with probability one, but the expected time to do so is infinite, and the count in the readout drops to zero within a few dozen ticks and only occasionally flickers back to one. In three dimensions it would never be guaranteed to return at all. **Diffusion.** If a tick is a time $\Delta t$ and the step is $s$, then $\mathbb E[R^2] = ns^2 = (s^2/\Delta t)\,t$. The quantity $D = s^2/(4\Delta t)$ is the diffusion coefficient, and $\mathbb E[R^2] = 4Dt$ is the two-dimensional Einstein relation. The $\sqrt n$ in every curve above is the $\sqrt t$ of diffusion: to spread twice as far takes four times as long. --- This is an independent rebuild of Wilensky, U. (1997), *NetLogo Random Walk 360 model*, http://ccl.northwestern.edu/netlogo/models/RandomWalk360, Center for Connected Learning and Computer-Based Modeling, Northwestern University, released under CC BY-NC-SA 3.0. The original, with its Info tab and code, runs in NetLogo Web on the page [[Random Walk 360 (NetLogo)]]. The additions here are the lattice mode, the histograms and the predicted curves.