Random Walk
A stochastic process modeling paths formed by successive random steps through a space.
A random walk is a mathematical model describing a sequence of steps where each step is chosen randomly from some set of possible moves. The process can unfold across many types of spaces — integers on a number line, nodes in a graph, or high-dimensional continuous spaces — making it a versatile abstraction for modeling systems that evolve through chance. The defining property is that each step is independent (or nearly so) of previous steps, giving the trajectory an unpredictable, wandering character whose statistical behavior can nonetheless be analyzed rigorously.
In machine learning and AI, random walks appear in a surprising range of applications. Graph-based algorithms such as PageRank and node2vec use random walks to capture structural information about networks, enabling tasks like link prediction, community detection, and graph embedding. In reinforcement learning, an agent exploring an environment with no policy guidance follows something close to a random walk, and understanding the coverage and mixing properties of such walks informs how quickly an agent can learn. Markov Chain Monte Carlo (MCMC) methods — workhorses of Bayesian inference — are fundamentally random walks designed to sample from complex probability distributions by wandering through parameter space in a statistically controlled way.
The mathematical properties of random walks are well-studied and directly useful. In one or two dimensions, a random walk is recurrent — it will almost surely return to its starting point given enough time. In three or more dimensions, it becomes transient, drifting away indefinitely. The expected distance from the origin after n steps scales as √n, a result that has practical implications for how quickly MCMC chains mix and how far a diffusion process spreads. These properties help practitioners diagnose convergence, set exploration schedules, and design more efficient sampling strategies.
Random walks also underlie diffusion models, one of the most powerful generative modeling frameworks in modern deep learning. The forward process that gradually corrupts data with noise is mathematically a discrete random walk (or its continuous analog, Brownian motion), and the generative model learns to reverse it. This connection between classical stochastic processes and cutting-edge generative AI illustrates why random walks remain a foundational concept across the field.
