Random Walk

A random walk is a stochastic process describing a sequence of positions reached by successive randomly determined steps. In its standard mathematical form, each position is the previous position plus a random increment, with increments independent and identically distributed. More broadly, the term includes movement between neighboring vertices of a graph. Random walks provide models for accumulated fluctuations and connect probability theory with diffusion, discrete geometry, and computational methods. Their behavior depends on the step distribution, the underlying space, and any imposed boundaries. (math.uchicago.edu)

Mathematical definition

For a walk on the real line or in Euclidean space, let $X_1,X_2,\ldots$ be random variables representing successive increments. Starting from a fixed position $S_0=s$, define

The usual assumptions are statistical independence and a common probability distribution for the increments. The increments may take discrete or continuous values; they need not have equal lengths or be symmetric about zero. (math.uchicago.edu)

Such a walk is a Markov chain: conditional on the current position, its future evolution does not depend on earlier positions. This is the Markov property. Independence of increments is stronger than this property alone; a general Markov chain can have transition probabilities that vary with its current state. Random walks on irregular graphs illustrate this distinction because the available moves depend on the vertex occupied. (math.mit.edu)

The one-dimensional simple walk

The simplest example moves on the integers, taking a step $+1$ with probability $p$ and a step $-1$ with probability $q=1-p$. The walk is symmetric when $p=q=1/2$ and biased otherwise. Starting at zero, if $B_n$ counts positive steps, then $B_n$ has a binomial distribution and $S_n=2B_n-n$. Consequently,

provided $|k|\le n$ and $n+k$ is even; otherwise the probability is zero. The parity restriction means, for example, that a return to zero is possible only after an even number of steps. (math.mit.edu)

The expected value and variance are

Thus a symmetric walk has zero mean displacement but an increasing spread: its standard deviation is $\sqrt n$. Zero mean does not mean that a typical path remains near zero; positive and negative displacements cancel when averaged over possible paths. More generally, increments with mean $\mu$ and finite variance $\sigma^2$ give mean position $s+n\mu$ and variance $n\sigma^2$. (ocw.mit.edu)

Recurrence and transience

A walk is recurrent if it returns to its starting point with probability one, and transient if that return probability is less than one. For the simple symmetric walk on the lattice $\mathbb Z^d$, each step chooses uniformly among the $2d$ nearest neighbors. Pólya’s recurrence theorem, established in 1921, states that this walk is recurrent in dimensions one and two, but transient in dimensions three and higher. This conclusion applies to the specified lattice walk, not automatically to every random movement in those dimensions. (arxiv.org)

Recurrence implies infinitely many returns almost surely, but does not imply a finite expected waiting time. The one-dimensional symmetric walk is null recurrent: it returns with certainty, yet its expected first return time is infinite. For transient walks, any fixed site is visited only finitely many times almost surely. These distinctions separate eventual return, repeated visitation, and average return time. (cs.yale.edu)

Hitting times and boundaries

A hitting time records the first occasion on which a walk reaches a specified state or set. Boundary conditions can alter the process substantially: an absorbing boundary stops movement, whereas a reflecting boundary redirects or restricts it. (math.mit.edu)

The classical gambler’s ruin problem considers a nearest-neighbor walk on $\{0,1,\ldots,N\}$, stopped upon reaching either endpoint. For a symmetric walk starting at $i$, the probability of reaching $N$ before zero is $i/N$, and the expected stopping time is $i(N-i)$. These results follow from conditioning on the first step and solving a recurrence relation with prescribed endpoint values. They illustrate how boundary questions differ from the distribution of position at a fixed time. (stat.berkeley.edu)

Scaling limits and diffusion

For independent, identically distributed increments with finite mean and positive finite variance, the central limit theorem gives

This explains the appearance of the normal distribution in long-time position statistics, even when individual steps are not normally distributed. It concerns distributions, rather than convergence of an individual path to a fixed trajectory. (ocw.mit.edu)

A stronger functional limit result connects entire rescaled paths to Brownian motion, mathematically represented by the Wiener process. Time is accelerated while centered spatial displacements are reduced by a square-root factor. This supplies a connection between discrete random walks and continuum diffusion, whose density evolution is described by the heat equation. Heavy-tailed increments with infinite variance or strong dependence between steps can produce different scaling behavior. (math.uchicago.edu)

Walks on graphs and extensions

In graph theory, a simple random walk chooses uniformly among the neighbors of its current vertex. Its transition matrix satisfies $P_{uv}=1/\deg(u)$ for adjacent vertices. On a finite connected undirected graph with at least one edge, the unique stationary distribution is

High-degree vertices therefore receive greater stationary probability. Convergence to this distribution also requires aperiodicity; allowing the walker to remain in place with positive probability removes the period-two obstruction of bipartite graphs. (cs.yale.edu)

Extensions include continuous-time walks with random waiting times, persistent walks with correlated directions, and self-avoiding walks that prohibit revisiting sites. These modify different assumptions of the basic model. Persistent and self-avoiding walks are used in polymer modeling, while long waiting times and heavy-tailed jumps provide models of anomalous diffusion. (math.mit.edu)