Mathwords logoMathwords

Random Walk — Definition, Formula & Examples

A random walk is a path formed by taking successive steps in random directions, where each step is determined by a chance process. The simplest version is a walk on the integers where you move +1 or −1 at each step, each with equal probability.

A random walk is a stochastic process {Sn}n≥0\{S_n\}_{n \geq 0} defined by Sn=S0+∑i=1nXiS_n = S_0 + \sum_{i=1}^{n} X_i, where X1,X2,…X_1, X_2, \ldots are independent, identically distributed random variables. In the simple symmetric case on Z\mathbb{Z}, each XiX_i takes values +1+1 or −1-1 with probability 12\tfrac{1}{2} each, and S0=0S_0 = 0.

Key Formula

Sn=S0+∑i=1nXiS_n = S_0 + \sum_{i=1}^{n} X_i
Where:
  • SnS_n = Position after n steps
  • S0S_0 = Starting position (often 0)
  • XiX_i = Random step at time i (e.g., +1 or −1 each with probability 1/2)
  • nn = Total number of steps taken

How It Works

Start at a position, typically the origin. At each discrete time step, a random variable determines the direction and size of your move. After nn steps, your position SnS_n is the cumulative sum of all individual steps. For a simple symmetric random walk, the expected position after any number of steps is 0 because positive and negative steps are equally likely. However, the spread of possible positions grows: the standard deviation of SnS_n is n\sqrt{n}. A classic result is that a simple random walk on the integers returns to the origin with probability 1, though the expected time to return is infinite.

Worked Example

Problem: A simple symmetric random walk starts at 0. After 4 steps, what is the probability that the walker is at position +2?
Step 1: To reach position +2 in 4 steps, the walker needs 3 steps of +1 and 1 step of −1, since 3(+1) + 1(−1) = +2.
Step 2: The number of ways to choose which 3 of the 4 steps are +1 is given by the binomial coefficient.
(43)=4\binom{4}{3} = 4
Step 3: Each specific sequence of 4 steps has probability (1/2)4(1/2)^4. Multiply by the number of favorable sequences.
P(S4=2)=(43)(12)4=4⋅116=14P(S_4 = 2) = \binom{4}{3}\left(\frac{1}{2}\right)^4 = 4 \cdot \frac{1}{16} = \frac{1}{4}
Answer: The probability of being at position +2 after 4 steps is 14=0.25\frac{1}{4} = 0.25.

Why It Matters

Random walks are foundational models in quantitative finance (stock price movements), physics (diffusion of particles), and computer science (randomized algorithms). Understanding them is essential in any probability or stochastic processes course, and they underpin more advanced models like Brownian motion and Markov chains.

Common Mistakes

Mistake: Assuming that after many steps, the walker is likely near the origin because the expected position is 0.
Correction: The expected position is 0, but the typical distance from the origin grows as n\sqrt{n}. The variance Var(Sn)=n\text{Var}(S_n) = n increases with each step, so the walker drifts farther from the start over time.