Random walk

Definition and basic properties

Formally, a random walk is a process with increments that are random and often independent. Key features include the Markov property (the future depends only on the present position) and the typical scaling of displacement: after many steps the position often grows on the order of the square root of the number of steps. Central-limit-type results imply that suitably rescaled sums of independent steps approach a normal (Gaussian) distribution in many cases.

Variants and continuous limits

There are many variants: simple symmetric walks (equal probabilities), biased walks (drift), walks in higher dimensions, and walks on networks or groups. When step sizes and times are scaled appropriately, discrete random walks converge to continuous stochastic processes such as Brownian motion (the Wiener process). Other extensions include random walks with memory, Lévy flights with heavy-tailed step distributions, and reinforced or self-avoiding walks.

History and theoretical milestones

The random walk concept arose in the late 19th and early 20th centuries in work on diffusion and finance. Early contributors studied its connection to Brownian motion and market price behavior. Later mathematical developments established deep results: classification of recurrence versus transience, limit theorems connecting discrete walks to continuous processes, and exact formulas for hitting probabilities in simple settings.

Applications and examples

• Physics: model for diffusion, thermal motion, and polymers.
• Finance: simple models of price changes and foundations for stochastic calculus.
• Computer science: randomized algorithms, Markov chain Monte Carlo, and network exploration.
• Biology and ecology: animal foraging paths and gene frequency models.

Notable theoretical facts include Pólya's observation that simple symmetric random walks on one- and two-dimensional lattices almost surely return to their starting point (recurrent), while in three or more dimensions they have a positive probability of never returning (transient). Classic problems such as gambler's ruin and first-passage (hitting) times quantify the likelihood of reaching specified states and are central in both theory and applications.