Random Walk and Central Limit Theorem

Here, we explore how chaos at the micro-level—individual, unpredictable random events—transforms into a highly structured and predictable pattern at the macro-level. This transformation is governed by the Central Limit Theorem (CLT), arguably the most important concept in statistics and a cornerstone of applied computer science.

To visualize this, we will use the Random Walk: a simple model of movement that serves as a laboratory for seeing the "Bell Curve" (Gaussian distribution) emerge from thin air.

The Random Walk: A Drunkard’s Path

Imagine a walker standing at position $0$ on a number line. Every second, they flip a coin:

• Heads: Move one step to the right ($+1$)
• Tails: Move one step to the left ($-1$)

If you watch one walker for 1,000 steps, their path looks like a jagged, unpredictable line. However, the CLT tells us that if we repeat this experiment with 10,000 different walkers, the distribution of their final positions will always follow a specific shape.

The Central Limit Theorem (CLT)

The CLT states that the sum (or average) of a large number of independent, identically distributed (i.i.d.) random variables will tend toward a Gaussian (Normal) distribution, regardless of the original distribution of those variables.

In our random walk:

• Each "step" is a random variable $X_i \in \{-1, 1\}$.
• The final position $S_n$ is the sum: $S_n = X_1 + X_2 + \dots + X_n$.
• As $n$ (the number of steps) grows, the distribution of $S_n$ becomes a Bell Curve.

Simulation: Watching the Bell Curve Emerge

As Computer Science students, we don't just rely on formulas; we simulate. With a program we can demonstrate that the Gaussian shape emerges naturally from the aggregation of steps:

from ipynb.fs.defs.plot_random_walk_and_CLT  import plot_random_walk_results, plot_random_walk_and_normal_dist
plot_random_walk_results(n_steps = 1000,      # Length of each walk
                         n_walkers = 100000)  # Number of individual simulations

Why does this happen?

It is a matter of combinatorics. To end up at the extreme edge (e.g., +1000), you would need to flip "Heads" 1,000 times in a row—an incredibly rare event. However, there are millions of different ways to flip roughly 500 Heads and 500 Tails, all of which land you near 0. The "Bell" is simply a map of where the most combinations exist.

Real-World "Random Walks"

The Gaussian distribution appears in nature because many natural processes are actually "sums" of tiny random factors:

• Biology: The height of a person is the sum of hundreds of small genetic and environmental "steps."
• Physics (Brownian Motion): A pollen grain in water moves because it is being hit by millions of water molecules from random directions. Its position over time is a 3D random walk.
• Finance: While controversial, stock prices are often modeled as "Geometric Random Walks," where each day's price change is a random step.
• Engineering: Measurement error in a sensor is often the sum of many tiny, independent interferences, leading to "Gaussian Noise."

Quantifying the Spread: The $\sqrt{n}$ Rule

In our simulation, you likely noticed that while the average position is $0$, the walkers don't all stay at $0$. They "diffuse" outward. A critical question for computer scientists is: How far, on average, will a walker be from the start after $n$ steps?

In a random walk where each step $X$ has a value of $+1$ or $-1$:

• The Mean of the final position is $0$.
• The Variance of the final position is exactly $n$ (the number of steps).
• The Standard Deviation ($\sigma$) is $\sqrt{n}$.

This means that in a 1,000-step walk, the "typical" distance from the center is $\sqrt{1000} \approx 31.6$ steps. According to the properties of the Gaussian distribution:

• 68% of walkers will be within $\pm 31.6$ steps of the origin.
• 95% of walkers will be within $\pm 63.2$ steps ($2\sigma$).

This is why, in your simulation code, the histogram doesn't just look like a "spike" at zero; it has a predictable "width" that grows predictably as you increase the number of steps.

In applied CS, this is why if you want to reduce the "noise" (standard deviation) in a sensor reading by a factor of 10, you usually need to take 100 times ($10^2$) more samples to average them out.

The Statistical Intuition: Variance vs. Distance

The math becomes clearer if we look at Variance ($V$).

For independent events, Variances add up linearly. If each step $X_i$ has a variance $\sigma^2 = 1$:$$Var(S_n) = Var(X_1) + Var(X_2) + \dots + Var(X_n) = n$$But distance (Standard Deviation) is the square root of Variance:$$\sigma = \sqrt{Var(S_n)} = \sqrt{n}$$This is a fundamental law in Computer Science and Physics: Uncertainty (noise) adds up linearly in power (variance), but sub-linearly in magnitude (standard deviation).

plot_random_walk_and_normal_dist(n_steps = 1000, n_walkers = 10000)

Summary Table

Concept	Definition	Applied Significance
i.i.d.	Independent and Identically Distributed.	Ensures each "step" is fair and doesn't depend on the past.
Central Limit Theorem	The sum of many random variables tends toward a Gaussian.	Explains why "noise" in data usually follows a Bell Curve.
Random Walk	A process of taking successive random steps.	A fundamental model for diffusion, stock prices, and search algorithms.
$\sqrt{n}$ Scaling	The standard deviation of a walk grows with the square root of steps.	Helps predict the "search area" or "error margin" over time.
Convergence	The more samples ($n$) you take, the smoother the Gaussian becomes.	Why "Big Data" often reveals patterns that small samples hide.