Random Walks - probability

Definition and Basic Concepts

Random Walk as a Stochastic Process

Definition: sequence of random steps on a mathematical space. Typically discrete time, discrete state space. Model: position X_n at step n defined recursively by X_{n} = X_{n-1} + ξ_n, where ξ_n are i.i.d. random variables.

One-Dimensional Random Walk

State space: integers ℤ. Step distribution: commonly symmetric Bernoulli ±1 with probability 0.5 each. Initial condition: X_0 = 0 or given start point.

Terminology and Notation

Path: sequence {X_0, X_1, ..., X_n}. Transition probabilities: P(X_{n+1} = x+1 | X_n = x) = p, P(X_{n+1} = x-1 | X_n = x) = 1-p. Homogeneous Markov chain: transition probabilities independent of n.

Types of Random Walks

Simple Symmetric Random Walk (SSRW)

Step size: ±1 with equal probability 0.5. Characteristic: zero drift, unbiased.

Biased Random Walk

Step distribution asymmetric: P(ξ_n=1)=p ≠ 0.5. Drift: E[ξ_n] = 2p -1 ≠ 0. Models directional trends.

Random Walk on Graphs and Lattices

Generalization to arbitrary state spaces: vertices of a graph, lattice ℤ^d. Transition probabilities determined by adjacency and weights.

Continuous-Time Random Walks

Steps occur at random times; modeled by Poisson processes or renewal processes. Leads to continuous-time Markov chains.

Key Properties

Markov Property

Future state depends only on current state, not past states. Formally, P(X_{n+1}|X_n,...,X_0) = P(X_{n+1}|X_n).

Stationarity of Increments

Increments ξ_n are i.i.d., identically distributed, independent of n.

Symmetry and Drift

Symmetric if P(ξ_n=1) = P(ξ_n=-1). Drift is expected step size E[ξ_n]. Determines long-term behavior.

Variance and Scaling

Variance after n steps: Var(X_n) = n Var(ξ_1). Standard deviation grows as √n, signifying diffusive spread.

Martingale Connection

Definition of Martingale

Process {M_n} adapted to filtration {F_n} with E[|M_n|]<∞ and E[M_{n+1}|F_n] = M_n.

Random Walk as Martingale

Simple symmetric random walk {X_n} with zero drift is martingale with respect to natural filtration.

Applications of Martingale Theory

Optional stopping theorem: expected value at stopping times. Used to analyze gambler’s ruin and hitting probabilities.

Recurrence and Transience

Definitions

Recurrent state: visited infinitely often with probability 1. Transient state: visited finitely many times with probability 1.

One-Dimensional Case

Simple symmetric random walk on ℤ is recurrent: returns to origin infinitely often almost surely.

Higher Dimensions

For d=1,2 SSRW is recurrent. For d≥3, SSRW is transient: positive probability to never return.

Criteria and Theorems

Polya’s theorem establishes recurrence/transience based on dimension. Proof uses potential theory and Fourier analysis.

Gambler’s Ruin Problem

Setup

Player starts with capital i, goal is to reach capital N or fall to 0. Modeled as random walk absorbed at 0 and N.

Probability of Ruin

For symmetric walk, ruin probability = 1 - (i/N). For biased walk, explicit formula involves ratios of drift probabilities.

Expected Duration

Expected time to absorption finite; formulas depend on bias and initial capital.

Applications

Modeling risk, finance, queues, and survival analysis.

Parameter	Formula	Comments
Ruin Probability (p=0.5)	P_ruin = 1 - i/N	Linear in initial capital
Ruin Probability (p ≠ 0.5)	P_ruin = ( ( (q/p)^i - 1 ) / ( (q/p)^N - 1 ) ), q=1-p	Geometric series form

Hitting Times and First Passage

Definition

Hitting time T_A = inf{ n ≥ 0 : X_n ∈ A } for subset A of state space.

Distribution and Expectation

Often difficult to compute exactly. For simple states, recursive methods or generating functions used.

First Passage Probabilities

Probability that random walk hits a state before another. Used in gambler’s ruin and queueing theory.

Let T_b = min{ n ≥ 0 : X_n = b }Then, for SSRW starting at i, P(T_b < T_a) = (i - a) / (b - a), for a < i < b

Applications

Reliability, survival analysis, finance hitting barriers.

Higher-Dimensional Random Walks

Definition

Random walk on ℤ^d with i.i.d. increments in d-dimensional integer lattice.

Recurrence vs Transience

Dimension-dependent behavior. d=1,2 recurrent; d≥3 transient.

Green’s Function and Potential Theory

Green’s function G(x,y) = expected number of visits to y starting from x. Used to analyze recurrence and hitting probabilities.

Applications

Physics (diffusion), ecology (animal movement), network theory.

Continuous Limit and Brownian Motion

Donsker’s Invariance Principle

Scaled random walk converges in distribution to Brownian motion as step size → 0, time → ∞.

Brownian Motion as Limit Process

Continuous-time, continuous-space stochastic process with stationary, independent increments.

Scaling Relations

Space scaled by √n, time scaled by n for convergence.

W(t) = limit of (1/√n) X_{[nt]} as n → ∞where {X_k} is SSRW

Applications

Physics, finance (Black-Scholes model), biology.

Applications

Physics and Chemistry

Diffusion processes, molecular motion, polymer chains.

Economics and Finance

Stock price modeling, option pricing, risk analysis.

Computer Science

Randomized algorithms, network routing, Monte Carlo methods.

Biology and Ecology

Animal foraging patterns, population genetics, neuronal firing sequences.

Mathematical Theory

Probabilistic proofs, ergodic theory, harmonic analysis.

Simulation and Algorithms

Basic Simulation Procedure

Generate i.i.d. increments ξ_n; compute cumulative sum for position X_n. Pseudorandom number generators used.

Algorithm Example

Initialize X_0 = 0For n = 1 to N: Generate ξ_n ∈ {+1, -1} with probability p, 1-p X_n = X_{n-1} + ξ_nOutput {X_0,...,X_N}

Variance Reduction Techniques

Antithetic variates, control variates to improve estimator accuracy.

Applications of Simulation

Estimating hitting probabilities, expected times, random walk visualization.

Step	Description
1	Initialize X_0
2	Generate random step ξ_n
3	Update position X_n = X_{n-1} + ξ_n
4	Repeat until desired steps completed

References

Feller, W. "An Introduction to Probability Theory and Its Applications." Vol. 1, Wiley, 1968, pp. 1-509.
Spitzer, F. "Principles of Random Walk." 2nd ed., Springer, 1976, pp. 1-300.
Durrett, R. "Probability: Theory and Examples." 4th ed., Cambridge University Press, 2010, pp. 1-400.
Lawler, G. F., Limic, V. "Random Walk: A Modern Introduction." Cambridge University Press, 2010, pp. 1-300.
Grimmett, G., Stirzaker, D. "Probability and Random Processes." 3rd ed., Oxford University Press, 2001, pp. 1-450.