Random walks (1D and 2D)
A random walk is a stochastic process built from successive random steps. It is a basic model for
diffusion, Brownian motion approximations, gambler’s ruin, and “drunkard’s walk” intuition.
Even when the expected position is zero, the walk typically drifts away from the origin with
a spread proportional to \(\sqrt{n}\).
1) 1D random walk model
Let \(X_n\) be the position after \(n\) steps. Define the step increment \(\Delta X_k\) as:
\[
\Delta X_k=
\begin{cases}
+s, & \text{with probability } p,\\
-s, & \text{with probability } 1-p,
\end{cases}
\qquad
X_n=\sum_{k=1}^{n}\Delta X_k.
\]
2) Expected position and drift (1D)
The expected step is:
\[
E[\Delta X]=(+s)p+(-s)(1-p)=s(2p-1).
\]
By linearity of expectation:
\[
E[X_n]=\sum_{k=1}^{n}E[\Delta X_k]=n\,E[\Delta X]=n s(2p-1).
\]
Unbiased walk: \(p=0.5\Rightarrow E[X_n]=0\). Biased walk: \(p\ne 0.5\Rightarrow\) nonzero drift.
3) Variance after \(n\) steps (1D)
First compute:
\[
E[\Delta X^2]=s^2.
\]
Then:
\[
\mathrm{Var}(\Delta X)=E[\Delta X^2]-(E[\Delta X])^2
=s^2-s^2(2p-1)^2=4s^2p(1-p).
\]
For independent steps:
\[
\mathrm{Var}(X_n)=\sum_{k=1}^{n}\mathrm{Var}(\Delta X_k)=n\,\mathrm{Var}(\Delta X)=4 n s^2 p(1-p).
\]
In the unbiased case \(p=0.5\), \(\mathrm{Var}(X_n)=n s^2\). The typical displacement is on the order of \(s\sqrt{n}\).
4) 2D random walk (axis-aligned)
In 2D, a common model chooses one of four axis directions at each step:
\[
\Delta S=
\begin{cases}
(s,0), & p_R\\
(-s,0), & p_L\\
(0,s), & p_U\\
(0,-s), & p_D
\end{cases}
\qquad
p_R+p_L+p_U+p_D=1.
\]
If \(S_n=(X_n,Y_n)\), then drift per step is:
\[
E[\Delta X]=s(p_R-p_L),\qquad
E[\Delta Y]=s(p_U-p_D).
\]
Hence:
\[
E[X_n]=nE[\Delta X],\qquad E[Y_n]=nE[\Delta Y].
\]
5) Component variances (2D)
Each step has \(\Delta X\in\{-s,0,+s\}\) (and similarly for \(\Delta Y\)). One can show:
\[
\mathrm{Var}(\Delta X)=s^2\bigl((p_R+p_L)-(p_R-p_L)^2\bigr),
\]
\[
\mathrm{Var}(\Delta Y)=s^2\bigl((p_U+p_D)-(p_U-p_D)^2\bigr).
\]
With independent steps:
\[
\mathrm{Var}(X_n)=n\,\mathrm{Var}(\Delta X),\qquad
\mathrm{Var}(Y_n)=n\,\mathrm{Var}(\Delta Y).
\]
In the unbiased case \(p_R=p_L=p_U=p_D=0.25\), the drift is zero and the endpoint cloud spreads roughly like \(\sqrt{n}\) in each coordinate.
6) Simulation vs. theory
The simulator estimates expectations by averaging over many independent runs:
\[
\widehat{E[X_n]}=\frac{1}{M}\sum_{m=1}^{M} X_n^{(m)},
\qquad
\widehat{\mathrm{Var}}(X_n)=\frac{1}{M-1}\sum_{m=1}^{M}\left(X_n^{(m)}-\widehat{E[X_n]}\right)^2.
\]
As \(M\) increases, Monte Carlo estimates become more stable (law of large numbers), and should approach the theoretical values
whenever the model assumptions match the simulator.
7) University extensions
- Drift + diffusion limit: scaling limits lead to Brownian motion.
- First passage times: probability/time to hit a boundary (gambler’s ruin).
- Higher dimensions: recurrence vs transience depends on dimension (classic result: 1D/2D recurrent, 3D+ transient).
