Random Walk
Visualize a 1D random walk over time.
Random Walk
Concept Overview
A random walk is a mathematical object that describes a path consisting of a succession of random steps on some mathematical space such as the integers. An elementary example is the 1D random walk on the integer number line, where at each step, the position moves by either +1 or -1 according to a specific probability distribution.
Mathematical Definition
Consider a sequence of independent and identically distributed random variables Z1, Z2, ..., Zn, where each variable represents a step. The position Xn of a 1D random walk after n steps is defined as the sum of these variables. If the walk starts at 0, then:
Xn = Σi=1n Zi
For a simple 1D random walk, Zi takes the value +1 with probability p and -1 with probability q = 1 - p. If p = 0.5, it is called a symmetric random walk.
Key Concepts
- Expected Value: The expected position after n steps is given by E[Xn] = n(2p - 1). For a symmetric walk (p = 0.5), the expected position remains 0.
- Variance: The variance of the position after n steps is Var(Xn) = 4np(1-p). The variance grows linearly with time, meaning the spread or uncertainty of the position increases.
- Recurrence: A symmetric 1D or 2D random walk is recurrent, meaning it will return to its origin with probability 1. However, random walks in 3D or higher dimensions are transient.
Historical Context
The term "random walk" was first introduced by Karl Pearson in 1905 in a letter to Nature, describing the problem of a walker taking random steps in a field. Random walks have since become a fundamental concept in probability theory, deeply connected to Brownian motion, which was analyzed by Albert Einstein in his miraculous year of 1905 to provide empirical evidence for the existence of atoms.
Real-world Applications
- Finance: Used to model stock prices and market fluctuations (e.g., the Random Walk Hypothesis in financial economics).
- Physics: Describes phenomena like Brownian motion, polymer chains, and diffusion processes.
- Computer Science: Forms the basis of randomized algorithms, such as Google's PageRank algorithm, network routing, and Monte Carlo simulations.
- Genetics: Models genetic drift and variations in allele frequencies over time.
Related Concepts
- Monte Carlo Simulation — Uses random sampling to solve complex problems, often involving random walks.
- Markov Chains — A sequence of possible events where the probability of each event depends only on the state attained in the previous event.
- Central Limit Theorem — Explains why the distribution of a random walk's position approaches a normal distribution for large n.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Random Walk module.
Try Random Walk on Riano →