Fact-checked by Grok 2 weeks ago

Random walk

A random walk is a stochastic process consisting of a sequence of random steps taken along a mathematical space, such as the one-dimensional integers, higher-dimensional lattices, or graphs, where each step is chosen independently according to a fixed probability distribution.^[1] This model captures the idea of unpredictable movement, often formalized as the cumulative sum of independent, identically distributed random variables representing displacements.^[1] Random walks form a foundational concept in probability theory, with origins tracing back to early 20th-century studies of diffusion and recurrence. The term "random walk" was first introduced by Karl Pearson in 1905 in a letter to Nature.^[2]^[3] A landmark result is Pólya's theorem (1921), which states that a simple symmetric random walk on a d-dimensional integer lattice is recurrent—meaning it returns to the starting point with probability 1—in dimensions d=1 or 2, but transient (returns with probability less than 1) for d ≥ 3.^[3] This dimensionality-dependent behavior highlights key properties like the expected displacement scaling with the square root of the number of steps, reflecting diffusive spread rather than ballistic motion.^[1] The model has broad applications across disciplines. In physics, random walks underpin the description of Brownian motion, where Albert Einstein applied it in 1905 to estimate atomic sizes from particle diffusion in fluids.^[4] In finance, it models stock price fluctuations under the efficient market hypothesis, assuming prices follow a random path with no predictable drift beyond randomness.^[5] Other uses include computer science for algorithms like Wilson's method for generating uniform spanning trees,^[6] biology for simulating foraging patterns, and ecology for population spread.^[7]

Basic Concepts

Definition and Examples

A random walk is a mathematical model describing a path formed by a succession of random steps, typically taken on a lattice or in continuous space, with each step selected independently according to a fixed probability distribution.^[1] This framework captures stochastic processes where the direction and magnitude of movement at each increment are probabilistic, modeling phenomena such as particle diffusion or erratic trajectories in various physical and biological systems.^[8] The concept emphasizes independence between steps, distinguishing it from deterministic paths or correlated movements. The term "random walk" was introduced by Karl Pearson in a 1905 letter to Nature, where he posed the problem of calculating the probability distribution for the net displacement of a particle undergoing random motions in two dimensions, inspired by observations of erratic particle movements.^[2] Pearson's query sought the proportion of particles likely to lie within certain distances after a fixed number of steps, highlighting the model's relevance to statistical mechanics and diffusion processes.^[9] A simple illustrative example is the drunkard's walk on a one-dimensional line, where an individual starts at the origin and at each step moves one unit left or right with equal probability of 1/2, simulating aimless wandering.^[10] This scenario demonstrates how successive independent choices lead to unpredictable overall displacement, with the path's variability increasing over time. As an introductory analogy for processes with potential reinforcement—though basic random walks maintain independence—Polya's urn model shows how drawing and replacing balls with additions can bias future selections, akin to self-reinforcing paths in extended variants.^[11] Formally, the position after n steps in a random walk is denoted S_n = \sum_{i=1}^n X_i, where the X_i are independent and identically distributed random variables representing individual step displacements, often with mean zero for symmetric cases.^[1] Random walks serve as a foundational example of Markov chains, where the next state depends only on the current position, enabling memoryless progression.^[12]

Probability and Expected Behavior

A random walk is typically defined as the partial sum process S_n = \sum_{i=1}^n X_i, where the increments X_i are independent and identically distributed random variables with mean \mu = \mathbb{E}[X_i] and finite variance \sigma^2 = \mathrm{Var}(X_i) > 0.^[1] The expected position after n steps is \mathbb{E}[S_n] = n \mu, which indicates a linear drift away from the origin if \mu \neq 0 (biased walk) or no net drift if \mu = 0 (unbiased walk).^[13] The variance of the position grows linearly as \mathrm{Var}(S_n) = n \sigma^2, reflecting the diffusive spreading of the walker's position over time, where the standard deviation scales as \sqrt{n}.^[13] By the central limit theorem for independent identically distributed random variables with finite variance, the normalized position \frac{S_n - n \mu}{\sqrt{n} \sigma} converges in distribution to a standard normal random variable N(0, 1) as n \to \infty, implying that S_n is approximately normally distributed with mean n \mu and variance n \sigma^2 for large n.^[14] For the symmetric unbiased one-dimensional simple random walk (where steps are +[1](/page/1) or -[1](/page/−1) each with probability $1/2, so \mu = 0 and \sigma^2 = 1), the probability of returning to the origin at the even step $2m satisfies P(S_{2m} = 0) \sim \frac{1}{\sqrt{\pi m}} asymptotically as m \to \infty.^[14]

Discrete Random Walks

One-Dimensional Lattice Walk

The one-dimensional lattice random walk, also known as the simple random walk on the integers \mathbb{[Z](/page/Z)}, models a particle starting at position 0 that at each step moves to the right (+1) with probability p or to the left (-1) with probability q = 1 - p.^[15] This setup captures the essential stochastic behavior in discrete time and space, where the position after n steps is S_n = X_1 + \cdots + X_n and each X_i is an independent random variable taking values +1 or -1 with the given probabilities.^[15] A classic application is the gambler's ruin problem, where the walk is confined between absorbing boundaries at 0 and a + b, starting from position k (with $0 < k < a + b), representing a gambler with initial capital k playing against an adversary with capital a + b - k.^[16] The probability of ruin (reaching 0 before a + b) is given by

P(\text{ruin} \mid S_0 = k) = \frac{(q/p)^k - (q/p)^{a+b}}{1 - (q/p)^{a+b}}

for p \neq q, derived by solving the associated linear recurrence relation for the absorption probabilities.^[16] In the symmetric case p = q = 1/2, this simplifies to P(\text{ruin} \mid S_0 = k) = (a + b - k)/(a + b).^[16] For the symmetric case p = q = 1/2, the probability of first return to the origin at step $2m (an even step, as returns occur only on even times) is

f_{2m} = \frac{1}{2m-1} \binom{2m}{m} \frac{1}{2^{2m}},

obtained using the reflection principle to count paths that return without prior returns.^[15] This formula highlights the recurrent nature of the walk, as the sum \sum_{m=1}^\infty f_{2m} = 1, meaning return to the origin is certain with probability 1.^[15] The one-dimensional lattice walk can be formalized as a Markov chain on the state space \mathbb{Z}, with transition probabilities P_{i,i+1} = p and P_{i,i-1} = q for interior states i.^[17] To incorporate boundaries, absorbing states are set where transitions from the boundary lead only to itself (probability 1), while reflecting boundaries modify the transitions at the edge, such as at state 0 where P_{0,1} = 1 (or adjusted for p, q).^[17] The transition matrix P is tridiagonal for finite-state truncations, enabling computation of occupation times or absorption probabilities via matrix exponentiation.^[17] Heterogeneous generalizations allow step sizes or probabilities to vary by position, such as site-dependent biases where the probability of moving right from site i is p_i and left is q_i = 1 - p_i, or steps of varying lengths \pm \ell_i.^[18] Position probabilities \pi_n(j) then satisfy recurrence relations like \pi_{n+1}(j) = \sum_i \pi_n(i) P_{i,j}, where P_{i,j} encodes the local rules, solvable iteratively or via generating functions for specific heterogeneity patterns such as random environments.^[18] These models extend to applications in disordered systems, preserving the Markov property but complicating closed-form solutions.^[18]

Multidimensional Lattice Walks

In the multidimensional setting, the simple symmetric random walk on the integer lattice \mathbb{Z}^d for d \geq 2 begins at the origin and, at each discrete time step, moves to one of the $2d nearest neighbors with equal probability $1/(2d).^[1] This setup generalizes the one-dimensional case by allowing steps along each of the d coordinate axes, either positively or negatively, selected uniformly at random. A key feature of these walks is their dimensionality-dependent recurrence behavior: in dimensions d=1 and d=2, the walk is recurrent, returning to the origin (and any starting point) infinitely often with probability 1; in d \geq 3, the walk is transient, with positive probability of never returning to the origin.^[11] This distinction arises because the effective "space" available for exploration grows faster in higher dimensions, making escapes more likely.^[3] Pólya's theorem formalizes this by stating that the probability of ever returning to the origin is 1 for d=1,2 and strictly less than 1 for d \geq 3, with the exact return probability given by $1 - \frac{1}{I_d} where I_d = \frac{1}{(2\pi)^d} \int_{[-\pi,\pi]^d} \frac{dk}{1 - \frac{1}{d} \sum_{j=1}^d \cos k_j}.^[19] The values decrease with dimension: approximately 0.3405 for d=3, 0.1932 for d=4, and approaching 0 as d \to \infty.^[19] This result, originally proved using asymptotic analysis and potential theory, highlights how the harmonic potential in low dimensions ensures recurrence while higher dimensions allow dissipation.^[11] The probability P_n(x) of being at site x \in \mathbb{Z}^d after n steps can be derived using the generating function approach via Fourier transform:

P_n(x) = \frac{1}{(2\pi)^d} \int_{[-\pi,\pi]^d} e^{-i k \cdot x} \left( \frac{1}{d} \sum_{j=1}^d \cos k_j \right)^n \, dk.

This integral representation facilitates analysis of asymptotic behavior, such as the local central limit theorem, where P_n(0) \sim c_d / n^{d/2} for large n, confirming recurrence in d \leq 2 via the divergence of the sum \sum_n P_n(0).^[1] As a special case of a Markov chain, the multidimensional lattice walk is time-homogeneous on the countable state space \mathbb{Z}^d, with transition probabilities p(y,z) = 1/(2d) if \|y - z\|_1 = 1 and 0 otherwise, enabling the use of Markov chain theory for studying mixing times, hitting probabilities, and equilibrium measures (though no stationary distribution exists due to infinite states).

Continuous Random Walks

Wiener Process as Limit

The scaling limit of a discrete random walk approximates the continuous Wiener process by letting the lattice spacing \epsilon \to 0 and the time step \tau \to 0, while fixing the diffusion constant D = \sigma^2 / (2\tau), where \sigma is the step variance; under this regime, the position of the walk at time t converges in distribution to the Wiener process W_t satisfying the covariance \mathbb{E}[W_s W_t] = \min(s,t).^[20] This limit bridges discrete lattice walks with continuous diffusion, capturing the irregular yet continuous paths observed in physical phenomena like particle motion.^[21] The Wiener process is formally defined as a continuous-time stochastic process \{W_t\}_{t \geq 0} on a probability space, starting at W_0 = 0, with independent increments W_t - W_s \sim \mathcal{N}(0, t-s) for $0 \leq s < t that are Gaussian with mean zero and variance equal to the time interval, and almost surely continuous sample paths.^[21] These properties ensure the process is a martingale with stationary increments, making it the canonical model for additive noise in stochastic systems.^[21] Donsker's theorem provides the rigorous foundation for this convergence, stating as a functional central limit theorem that the linearly interpolated and rescaled paths of a simple symmetric random walk—specifically, S_{\lfloor nt \rfloor}/\sqrt{n} for t \in [0,1]—converge in distribution to a standard Brownian motion in the Skorokhod space of càdlàg functions equipped with the Skorokhod topology.^[22] This invariance principle extends the classical central limit theorem from finite-dimensional distributions to the entire path, enabling weak convergence arguments for functional approximations.^[22] A fundamental tool for analyzing functions of the Wiener process is Itô's lemma, which specifies that for a twice-differentiable function f(t, W_t),

df(t, W_t) = \frac{\partial f}{\partial t} dt + \frac{\partial f}{\partial w} dW_t + \frac{1}{2} \frac{\partial^2 f}{\partial w^2} dt,

accounting for the quadratic variation of the process and forming the basis of stochastic calculus. The Wiener process, named after Norbert Wiener's 1923 rigorous construction of Brownian motion paths, builds on Albert Einstein's 1905 derivation of the diffusion equation linking microscopic collisions to macroscopic spreading.^[23]

Gaussian Random Walk Properties

A Gaussian random walk is defined by independent and identically distributed steps X_i \sim \mathcal{N}(\mu, \sigma^2) for i = 1, 2, \dots, n, where the position after n steps is the partial sum S_n = \sum_{i=1}^n X_i. Unlike lattice-based walks that require the central limit theorem for large n approximations, the distribution of S_n is exactly Gaussian: S_n \sim \mathcal{N}(n\mu, n\sigma^2). This exact normality arises from the reproductive property of Gaussian distributions under convolution, enabling precise analytical treatment of moments and tail probabilities without asymptotic assumptions.^[24] In continuous space, the trajectory of a Gaussian random walk, akin to a discretized Wiener process, visits uncountably infinite distinct points due to the continuity of the path. However, in discretized versions on a lattice—where positions are rounded or binned—the expected number of distinct sites visited exhibits asymptotic growth similar to simple symmetric walks, scaling as \sqrt{8n/\pi} in one dimension and \pi n / \log n in two dimensions for large n.^[25] These behaviors highlight the diffusive spreading, with slower exploration in higher dimensions due to recurrence effects in low dimensions. From an information-theoretic perspective, the differential entropy of the position H(S_n) in one dimension quantifies the uncertainty in location after n steps:

H(S_n) = \frac{1}{2} \log (2 \pi e n \sigma^2),

reflecting the maximum entropy for a given variance n\sigma^2. The entropy rate, \lim_{n \to \infty} [H(S_{n+1}) - H(S_n)] / n = 0, indicates that incremental positional uncertainty grows sublinearly (\sim 1/(2n)), vanishing in the per-step limit; this contrasts sharply with deterministic paths, where entropy remains zero as positions are fully predictable. In higher dimensions, the entropy scales as (d/2) \log (2 \pi e n \sigma^2) for d-dimensional isotropic steps.^[26]^[27] Mean-reverting variants extend the Gaussian random walk by incorporating a linear drift toward a central value, leading to the Ornstein-Uhlenbeck process as a continuous-time analog; in discrete form, this is an autoregressive process S_{n+1} = \theta S_n + X_{n+1} with |\theta| < 1 and Gaussian noise X_{n+1}, yielding a stationary Gaussian distribution for large n.^[28] Such extensions model bounded fluctuations, common in physical systems like velocity in Brownian motion under friction. Key developments in the 1960s, particularly Frank Spitzer's work on the range—the number of distinct sites up to time n—laid foundational results for Gaussian random walks, including limit theorems for the normalized range and its fluctuations in both discrete and continuous settings.

Mathematical Properties

Recurrence and Transience

In random walk theory, a state is recurrent if the walk returns to it infinitely often with probability 1, and transient otherwise.^[1] For an irreducible random walk starting at the origin, recurrence is equivalent to the probability of eventual return to the origin being 1, which holds if and only if the sum of return probabilities diverges: \sum_{n=1}^\infty P(S_n = 0) = \infty, where S_n denotes the position after n steps.^[1] For symmetric random walks with finite second moment, the Chung-Fuchs theorem establishes that such walks on \mathbb{R}^d are recurrent when d \leq 2 and transient when d > 2, mirroring the behavior of Brownian motion via the invariance principle.^[1] This result generalizes Pólya's theorem for the simple symmetric random walk on the integer lattice \mathbb{Z}^d, which is recurrent in dimensions 1 and 2 but transient in dimension 3 and higher.^[1] In transient cases, the potential kernel, or Green function, G(x) = \sum_{n=0}^\infty P(S_n = x) converges to a finite value, providing a key tool for analyzing escape probabilities from the origin, such as the probability that the walk never returns, given by $1 / G(0).^[1] For recurrent walks, G(x) diverges, reflecting infinite expected visits to each site. Biased random walks, with nonzero mean drift, are transient in all dimensions d \geq 1, as the drift ensures the walk escapes to infinity with positive speed.^[1] In contrast, the simple symmetric case without bias exhibits dimension-dependent recurrence as noted above.

Number of Distinct Sites Visited

The number of distinct sites visited by a random walk up to step n, denoted R_n = |\{S_0, S_1, \dots, S_n\}|, quantifies the spatial spread of the trajectory, where S_k denotes the position at step k. In one dimension, for the symmetric simple random walk on the integers, the expected value satisfies \mathbb{E}[R_n] \sim \sqrt{8n / \pi} as n \to \infty. This asymptotic arises from the reflection principle applied to the maximum and minimum positions attained by the walk, as R_n = \max_{0 \leq k \leq n} S_k - \min_{0 \leq k \leq n} S_k + 1, with each endpoint having expectation asymptotically \sqrt{2n / \pi}. In two dimensions, on the square lattice, the expected number grows more slowly due to recurrence: \mathbb{E}[R_n] \sim \pi n / \log n as n \to \infty. This result reflects the logarithmic factor emerging from the harmonic potential in recurrent walks. For dimensions d \geq 3, simple random walks are transient, and \mathbb{E}[R_n] \sim c_d n as n \to \infty, where c_d = 1 / G(0,0) is a dimension-specific constant, with G(0,0) = \sum_{k=0}^\infty \mathbb{P}(S_k = 0) denoting the Green function value at the origin (the expected number of visits to the starting point). This linear growth stems from the finite expected number of returns to any site in transient regimes. In the continuous setting, the range of Brownian motion paths in \mathbb{R}^d has Lebesgue measure zero almost surely for d \geq 2, but positive measure in d=1.^[29] However, the expected area covered in two dimensions—analogous to the discrete case via discretization or the volume of an \epsilon-neighborhood (Wiener sausage)—grows as t / \log t for fixed small \epsilon > 0 as t \to \infty, mirroring the lattice result.^[30] Local time L_t^x, measuring the density of occupation time at point x up to time t, connects to the range through the Ray-Knight theorems, which characterize the process (L_t^x)_{x \geq 0} at fixed times t (or the last zero-crossing) as a squared Bessel process, thereby linking visit multiplicities to spatial exploration.^[31]

Variants and Generalizations

Walks on Graphs

Random walks on graphs generalize the concept of lattice walks to arbitrary discrete structures, where the state space consists of the vertices of a graph G = (V, E), and transitions occur along edges. In the simple random walk on an undirected graph, from a current vertex u \in V, the walk moves to a neighboring vertex v with probability P_{uv} = 1 / \deg(u) if \{u, v\} \in E, and remains at u with probability 0 otherwise; alternatively, uniform probability over neighbors can be specified, but the degree-proportional variant is standard for non-regular graphs.^[32] This model assumes the graph is connected and finite, ensuring the walk is a Markov chain with irreducible transitions. For undirected graphs, the simple random walk is reversible, meaning the detailed balance equations hold with respect to a specific stationary distribution.^[33] The stationary distribution \pi for the simple random walk on an undirected graph satisfies \pi_v = \deg(v) / (2 |E|) for each vertex v \in V, where \deg(v) is the degree of v and |E| denotes the number of edges; this distribution is unique and positive, reflecting the walk's tendency to spend more time at higher-degree vertices.^[32] The chain converges to \pi from any initial distribution, with the rate governed by the mixing time \tau_{\mix}(\epsilon), defined as the minimum number of steps t such that the total variation distance to \pi is at most \epsilon > 0 regardless of starting state. A key bound relates mixing time to the graph's conductance \Phi(G), defined as \Phi(G) = \min_{S \subseteq V: 0 < \pi(S) \leq 1/2} \frac{\sum_{u \in S, v \notin S} P_{uv} \pi_u}{\pi(S)}, yielding \tau_{\mix}(\epsilon) \leq \frac{1}{2\Phi(G)} \log(1/\epsilon) for sufficiently lazy variants or continuous-time analogs, highlighting how bottlenecks in the graph (low \Phi) prolong convergence.^[33] The cover time C(G), the expected number of steps for the walk to visit every vertex starting from the worst-case initial vertex, quantifies exploration efficiency. For d-regular graphs, Matthews' bound establishes C(G) \sim |V| \log |V|, more precisely C(G) \leq 2 |E| (\ln |V| - \ln \pi_{\min} + 1) where \pi_{\min} is the minimum stationary probability, providing a tight asymptotic for many expander-like structures.^[32] This bound arises from coupon-collector arguments adapted to hitting times, with the maximum expected hitting time H_{\max} satisfying C(G) \leq H_{\max} \sum_{k=1}^{|V|} 1/k \approx H_{\max} \ln |V|. Lattice walks, such as those on \mathbb{Z}^d, emerge as special cases when the graph is the infinite d-dimensional grid.^[32] An elegant analogy interprets random walks via electrical networks, where the graph is treated as a resistor network with each edge of unit resistance. The effective resistance R_{uv} between vertices u and v equals the commute time \mathbb{E}_u[T_v] + \mathbb{E}_v[T_u] (expected steps to go from u to v and back) divided by $2 |E|, i.e., \mathbb{E}_u[T_v] + \mathbb{E}_v[T_u] = 2 |E| R_{uv}; this connection, rooted in Thomson's principle, facilitates computations of hitting and cover times using circuit theory.^[34]

Biased and Correlated Walks

Biased random walks introduce directional preferences in the step probabilities, deviating from the unbiased case where steps are equally likely in all directions. In one dimension, this is modeled by assigning probability p \neq 1/2 to a step right and $1-p to a step left, resulting in a net drift. The expected position after n steps, E[S_n], exhibits ballistic motion proportional to n(2p - 1), reflecting the systematic displacement due to the bias.^[35] On graphs, bias can be incorporated through weighted edges, where transition probabilities are proportional to edge weights, favoring paths along stronger connections and altering the walk's exploration dynamics.^[36] Correlated walks extend this by introducing temporal dependencies between consecutive steps, capturing persistence or memory effects absent in independent steps. A prominent example is the persistent random walk, where the direction of motion influences the next step, often parameterized by the angle \theta between consecutive velocities. This correlation leads to a velocity autocorrelation function that decays exponentially as e^{-t/\tau}, with \tau representing the persistence time scale.^[37] In one dimension, the persistent random walk satisfies the telegrapher's equation, a hyperbolic partial differential equation that interpolates between wave propagation and diffusion:

\frac{\partial^2 P}{\partial t^2} + \frac{1}{\tau} \frac{\partial P}{\partial t} = v^2 \frac{\partial^2 P}{\partial x^2},

where P(x,t) is the probability density, v is the constant speed, and \tau is the mean time between direction changes. This equation arises as the continuum limit of the discrete model and was first derived for such walks in the context of discontinuous diffusion processes. Another correlated variant is the maximal entropy random walk, which selects transition probabilities to maximize the Shannon entropy of the path distribution subject to constraints like stationary measures, resulting in uniform coverage over accessible states. This approach contrasts with standard biased walks by prioritizing informational uniformity rather than directional favoritism, and it localizes in defect-free regions on lattices.^[38] Early models of persistent walks, including those with correlations suitable for neutron transport, were developed in the 1950s, notably by Sidney Goldstein and Mark Kac in 1951, who derived the telegraph equation for such processes in the context of particle scattering and moderation in nuclear physics.^[39]

Applications

In Physics and Diffusion

In physics, random walks provide a foundational model for Brownian motion, the irregular movement of microscopic particles suspended in a fluid due to collisions with surrounding molecules. Albert Einstein's 1905 analysis treated the particle's trajectory as a random walk, deriving the diffusion coefficient D for a spherical particle of radius r in a medium of viscosity \eta at temperature T as D = \frac{kT}{6\pi\eta r}, where k is Boltzmann's constant; this relation links thermal energy to measurable transport properties and confirmed the molecular-kinetic theory of heat.^[23] The mean squared displacement in this process grows linearly with time, \langle x^2 \rangle = 2Dt in one dimension, establishing normal diffusion as a hallmark of equilibrium thermal fluctuations.^[23] The connection between discrete random walks and continuous diffusion emerges in the continuum limit, where the master equation governing the probability P(\mathbf{x}, t) of finding a particle at position \mathbf{x} at time t—accounting for jumps to neighboring sites—yields the diffusion equation \frac{\partial P}{\partial t} = D \nabla^2 P as the step size and time interval approach zero while preserving the variance.^[40] This derivation, formalized in early stochastic analyses, underpins the heat equation for temperature diffusion and Fick's laws for mass transport, illustrating how microscopic randomness aggregates to macroscopic parabolic partial differential equations.^[40] Anomalous diffusion arises when random walks deviate from Gaussian steps, such as in Lévy flights with power-law distributed step lengths P(\ell) \sim |\ell|^{-1-\alpha} for $0 < \alpha < 2, leading to long-range jumps that produce superdiffusion with mean squared displacement \langle x^2 \rangle \sim t^{2H} where the Hurst exponent H > 1/2.^[41] Conversely, subdiffusion occurs in trapped or heterogeneous media with H < 1/2, often modeled by continuous-time random walks with heavy-tailed waiting times, resulting in non-exponential relaxation and fractional diffusion equations that capture memory effects in disordered systems like porous materials or glasses.^[41] In polymer physics, the random walk serves as the ideal chain model for a Gaussian polymer, where the chain of N segments of length l adopts configurations akin to a three-dimensional random walk, yielding a root-mean-square end-to-end distance \sqrt{\langle R^2 \rangle} = l \sqrt{N} in the absence of interactions.^[42] Real polymers exhibit excluded volume effects that swell the chain, modifying the scaling to \sqrt{\langle R^2 \rangle} \sim N^\nu with the Flory exponent \nu = 3/5 in three dimensions, as predicted by mean-field theories balancing entropy and repulsive interactions; more precise estimates from renormalization group theory and simulations give \nu \approx 0.588.^[42]^[43] Twentieth-century advancements extended these ideas to non-equilibrium settings, notably through Marian Smoluchowski's 1906 formulation of the drifted diffusion equation \frac{\partial P}{\partial t} = D \nabla^2 P - \nabla \cdot (\mathbf{v} P), where \mathbf{v} is a drift velocity from external forces like gravity or electric fields, enabling descriptions of sedimentation and electrophoresis in colloidal suspensions.^[44] This Fokker-Planck equation, derived from random walks with bias, bridges stochastic dynamics to deterministic transport under linear restoring forces.^[44]

In Finance and Biology

In finance, the random walk model forms the foundation of modern asset pricing theory, positing that stock prices evolve unpredictably due to successive random changes in expectations. Louis Bachelier's 1900 doctoral thesis introduced this concept by modeling stock prices as a random walk, where future price changes are independent of past changes, laying the groundwork for the efficient market hypothesis that markets fully reflect all available information, rendering price prediction impossible beyond random fluctuations.^[45]^[46] This idea evolved into the geometric Brownian motion (GBM) model for stock prices, described by the stochastic differential equation dS = \mu S \, dt + \sigma S \, dW, where S is the stock price, \mu is the drift rate, \sigma is the volatility, and dW is the increment of a Wiener process representing random shocks.^[47] The GBM ensures positive prices and log-normal distribution of returns, capturing the empirical observation that volatility scales with price level. In option pricing, the Black-Scholes model derives the partial differential equation (PDE) \frac{\partial V}{\partial t} + \frac{1}{2} \sigma^2 S^2 \frac{\partial^2 V}{\partial S^2} + r S \frac{\partial V}{\partial S} - r V = 0, for the value V(S, t) of a European option, solved under risk-neutral valuation where the drift \mu equals the risk-free rate r, allowing arbitrage-free pricing by discounting expected payoffs at r.^[47] In biology, random walks model adaptive behaviors under uncertainty, such as bacterial navigation toward nutrients via chemotaxis, interpreted as a biased random walk where cells adjust tumbling frequency in response to chemical gradients to increase net displacement up the gradient.^[48] The run-and-tumble motion in bacteria like Escherichia coli, as analyzed by Berg and Brown (1972), can be modeled using a correlated random walk framework, where straight "runs" persist directionally before random "tumbles" reorient the cell, enhancing diffusion efficiency over uncorrelated walks and approximating continuous-time processes for analyzing persistence in movement.^[49] Search theory applies random walks to optimal foraging, where animals like sharks or spiders use Lévy walks—random walks with step lengths drawn from heavy-tailed α-stable distributions (typically 1 < α ≤ 2)—to detect sparse resources more efficiently than Brownian motion, as the power-law tails allow occasional long excursions that maximize encounter rates in patchy environments without exhaustive local search. In evolutionary genetics, the Wright-Fisher model treats allele frequency changes as a discrete random walk due to genetic drift in finite populations, where the frequency of a neutral allele in generation t+1 is binomially sampled from the previous generation's frequency, leading to eventual fixation or loss with probabilities equal to initial frequencies.

References

[1]
[PDF] Random Walk: A Modern Introduction - The University of Chicago
Random walk – the stochastic process formed by successive summation of ... definition of P. Suppose that on the same probability space we have defined ...
[2]
[PDF] p´olya's random walk theorem - MIT Mathematics
A random walk is said to be recurrent if it returns to its initial position with probability one. A random walk which is not recurrent is called transient.
[3]
The One-Dimensional Random Walk - Galileo
Einstein used the random walk to find the size of atoms from the Brownian motion. The Probability of Landing at a Particular Place after n Steps. Let's begin ...
[4]
[PDF] Random Walks: A Review of Algorithms and Applications - arXiv
Aug 9, 2020 · Random walks can be used to analyze and simulate the randomness of objects and calculate the correlation among objects, which are useful in ...
[5]
[PDF] Random walks
Random walks are one of the basic objects studied in probability theory. The moti- vation comes from observations of various random motions in physical and ...Missing: authoritative sources
[6]
The Problem of the Random Walk - Nature
The random walk. In the warm summer months of 1905, Karl Pearson was perplexed by the problem of the random walk. He appealed to the readers of Nature for a ...
[7]
[PDF] The Problem of the Random Walk
KARL PEARSON. The Gables, East Isley, Berks. British Archæology and Philistinism. AT the end of the second week in July two contracted skeletons were found ...
[8]
Random Walk -- from Wolfram MathWorld
A random walk is a sequence of discrete steps in which each step is randomly taken subject to some set of restrictions in allowed directions and step lengths.Missing: definition | Show results with:definition
[9]
[PDF] p´olya's theorem on random walks via p´olya's urn
If d ≥ 3, then with positive probability, the walk never returns to its starting position. This is Pólya's theorem referred to in the title. Theorem 1 motivates.
[10]
[PDF] Lecture 12: Random walks, Markov chains, and how to analyse them
Example 1 (Drunkard's walk) There is a sequence of 2n + 1 pubs on a street. A drunkard starts at the middle house. At every time step, if he is at pub ...
[11]
[PDF] Probability: Theory and Examples Rick Durrett Version 5 January 11 ...
Jan 11, 2019 · The four sections of the random walk chapter have been relocated. Stopping times have been moved to the martingale chapter; recur- rence of ...
[12]
[PDF] 1957-feller-anintroductiontoprobabilitytheoryanditsapplications-1.pdf
random walks (chapter III and the main part of XIV). These chapters are almost ... INTRODUCTION: THE NATURE OF PROBABILITY THEORY . The Background ...
[13]
[PDF] Random Walks - Chance
. Theorem 12.3 For m ≥ 1, the probability of a first return to the origin at time. 2m is given by f2m = u2m. 2m − 1. = ¡2m m. ¢. (2m − 1)22m . Proof. We begin ...
[14]
[PDF] 1 Gambler's Ruin Problem
If Rτi = N, then the gambler wins, if. Rτi = 0, then the gambler is ruined. Let Pi = P(Rτi = N) denote the probability that the gambler wins when R0 = i.
[15]
[PDF] MARKOV CHAINS AND RANDOM WALKS
28 The reflection principle for a simple random walk in dimension 1. 86. 28.1 ... is called the (one-step) transition probability matrix or, simply, transition ma ...
[16]
[PDF] Random walks in one dimensional environment Dmitry Dolgopyat
Central Limit Theorem for excited random walk in the recurrent regime, preprint. [9] Dolgopyat D., Goldsheid I. Quenched limit theorems for random walks in one.Missing: 1D | Show results with:1D
[17]
Pólya's Random Walk Constants -- from Wolfram MathWorld
Let p(d) be the probability that a random walk on a d-D lattice returns to the origin. In 1921, Pólya proved that p(1)=p(2)=1, (1) but p(d)<1 (2) for d>2.
[18]
11.4.1 Brownian Motion as the Limit of a Symmetric Random Walk
The random process W(t) is called the standard Brownian motion or the standard Wiener process. Brownian motion has continuous sample paths, i.e., W(t) is a ...
[19]
[PDF] BROWNIAN MOTION 1.1. Wiener Process
in fact, Brow- nian scaling implies that there is an embedded simple random walk on ...
[20]
[PDF] Brownian motion as the limiting distribution of random walks
Aug 28, 2021 · Donsker's invariance principle, also known as the functional central limit theo- rem, extends the central limit theorem from random variables to ...
[21]
[PDF] the brownian movement - DAMTP
Equation (I) can be used to find the coefficient of diffusion of the suspended substance. We can look upon the dynamic equilibrium condition con- sidered ...
[22]
Cumulants of the maximum of the Gaussian random walk
We consider the partial sums S n = X 1 + ⋯ + X n , with S 0 = 0 , and refer to the process { S n : n ≥ 0 } as the Gaussian random walk. This paper is concerned ...
[23]
[PDF] Random walks
Random walk on a 1D lattice. At each step particle jumps to the right with probability q and to the left with probability 1-q. ... In the limit of small jumps ...
[24]
Entropy of the Gaussian - Gregory Gundersen
Sep 1, 2020 · The information entropy or entropy of a random variable is the average amount information or “surprise” due to the range values it can take.
[25]
Proof: Differential entropy of the multivariate normal distribution
May 14, 2020 · (2) (2) h ( x ) = n 2 ln ⁡ ( 2 π ) + 1 2 ln ⁡ | Σ | + 1 2 n . Proof: The differential entropy of a random variable is defined as.
[26]
[PDF] Ornstein-Uhlenbeck Processes and Extensions - mediaTUM
This paper surveys a class of Generalised Ornstein-Uhlenbeck (GOU) processes associated with Lévy processes, which has been recently much analysed in view of ...Missing: walk | Show results with:walk
[27]
[PDF] Random Walks on Graphs: A Survey
Various aspects of the theory of random walks on graphs are surveyed. In particular, estimates on the important parameters of access time, commute time,.
[28]
[PDF] Markov Chains and Mixing Times, second edition David A. Levin ...
Page 1. Markov Chains and Mixing Times, second edition. David A. Levin. Yuval Peres. With contributions by Elizabeth L. Wilmer. University of Oregon. E-mail ...
[29]
[PDF] Random walks and electric networks - Dartmouth Mathematics
Consider a random walk on the integers 0, 1, 2,...,N. Let p(x) be the probability, starting at x, of reaching N before 0. We regard p(x) as a function defined on ...
[30]
Record statistics for biased random walks, with an application to ...
May 9, 2011 · We consider the occurrence of record-breaking events in random walks with asymmetric jump distributions. The statistics of records in ...
[31]
Accurately Modeling Biased Random Walks on Weighted Graphs ...
Sep 15, 2021 · \textit{Node2vec} is a widely used method for node embedding that works by exploring the local neighborhoods via biased random walks on the graph.
[32]
[PDF] Lecture 10: Persistent Random Walks and the Telegrapher's Equation
Here we consider the Persistent Random Walk example, a correlated random walk on a hypercubic lattice in which the walker has probability α of continuing in ...
[33]
None
Nothing is retrieved...<|separator|>
[34]
(PDF) A Continuous-Time Generalization of the Persistent Random Walk
### Summary of Key Information
[35]
[PDF] Stochastic Problems in Physics and Astronomy
The diffusion equation is an elementary consequence of this fact. Consequently, we may describe the motion of a large number of particles describing random ...
[36]
(PDF) The random walk's guide to anomalous diffusion: a fractional ...
Aug 5, 2025 · The random walk's guide to anomalous diffusion: a fractional dynamics approach. Phys Rep DOI:10.1016/s0370-15730000070-3 Authors: Ralf Metzler at Universität ...
[37]
[PDF] Nobel Lecture, December 11, 1974 - PAUL J. FLORY
The skeletal bonds of the molecular chain were thus likened to the steps in a random walk in three dimensions, the steps being uncorrelated one to another.
[38]
[PDF] CENTENARY OF MARIAN SMOLUCHOWSKI'S THEORY OF ...
The papers published by Smoluchowski one hundred years ago turned out to be of fundamental importance not only to the theory of Brownian motion but above all to ...Missing: drifted | Show results with:drifted
[39]
Théorie de la spéculation - Numdam
Bachelier, L. Annales scientifiques de l'École Normale Supérieure, Série 3, Tome 17 (1900), pp. 21-86.
[40]
[PDF] Louis Bachelier's “Theory of Speculation” - Imperial College London
Louis Bachelier's 1900 PhD thesis Théorie de la Spéculation introduced mathematical finance to the world and also provided a kind of agenda for probability ...
[41]
[PDF] Fischer Black and Myron Scholes Source: The Journal of Political Eco
Author(s): Fischer Black and Myron Scholes. Source: The Journal of Political Economy, Vol. 81, No. 3 (May - Jun., 1973), pp. 637-654. Published by: The ...
[42]
Biased random walk models for chemotaxis and related diffusion ...
Stochastic models of biased random walk are discussed, which describe the behavior of chemosensitive cells like bacteria or leukocytes in the gradient of a.
[43]
Dispersion of soluble matter in solvent flowing slowly through a tube
When a soluble substance is introduced into a fluid flowing slowly through a small-bore tube it spreads out under the combined action of molecular diffusion.