The Simple Symmetric Random Walk as a Martingale

Fair Steps and Conditional Prediction

A simple symmetric random walk moves one unit to the right or left at each step, with equal probability. Its increments have mean zero, but that fact alone does not explain the martingale property: the key is that, given all the steps observed so far, the next increment still has mean zero. Thus the current position is the best conditional mean prediction of the next position.

Work on the probability space \((\Omega,\mathcal{F},\mathbb{P})\) of infinite sequences of independent fair coin tosses. Write \(H\) for a heads outcome and \(T\) for tails, and encode each toss by \(\xi_k=1\) for heads and \(\xi_k=-1\) for tails. Thus \(\mathbb{P}(\xi_k=1)=\mathbb{P}(\xi_k=-1)=\tfrac12\), and the random variables \((\xi_k)_{k\ge1}\) are independent. The walk has state space \(S=\mathbb{Z}\), discrete time \(n\ge0\), and position

The natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\), the information generated by the positions observed through time \(n\). Because \(X_k-X_{k-1}=\xi_k\), this is also \(\sigma(\xi_1,\ldots,\xi_n)\); at \(n=0\), it contains only the initial information. A sequence \((M_n)_{n\ge0}\) is a martingale with respect to \((\mathcal{F}_n)\) if each \(M_n\) is \(\mathcal{F}_n\)-measurable, \(\mathbb{E}|M_n|<\infty\), and \(\mathbb{E}[M_{n+1}\mid\mathcal{F}_n]=M_n\) almost surely for every \(n\ge0\).

The mean condition says that there is no directional bias in the next step once the observed history is known. The variance condition says that uncertainty about that next step remains: it is not a claim that the increment itself is zero. Both statements are conditional on the information available at time \(n\).

Proof. Fix \(n\ge0\). The position \(X_n\) is \(\mathcal{F}_n\)-measurable by the definition of the filtration. Also, each increment has absolute value \(1\), so \(|X_n|\le n\) for every outcome. Consequently \(\mathbb{E}|X_n|\le n<\infty\).

For each possible history \(h=(\xi_1,\ldots,\xi_n)\), the event that the first \(n\) increments equal \(h\) is an atom of \(\mathcal{F}_n\) and has probability \(2^{-n}>0\). For \(n=0\), there is one empty history, with probability \(1\). Independence of the coin tosses implies that, conditional on any such history, \(\xi_{n+1}\) equals \(1\) and \(-1\) with probability \(\tfrac12\) each. Therefore its conditional mean on that history is \(\tfrac12(1)+\tfrac12(-1)=0\), and its conditional second moment is \(\tfrac12(1^2)+\tfrac12((-1)^2)=1\). Since \(X_{n+1}=X_n+\xi_{n+1}\) and \(X_n\) is known at time \(n\), on each history \(\mathbb{E}[X_{n+1}\mid\mathcal{F}_n]=X_n+0=X_n\). The conditional variance of the increment is its conditional second moment minus the square of its conditional mean, so it is \(1-0^2=1\). The histories partition the sample space, which gives both conditional identities almost surely. Adaptedness, integrability, and the conditional-expectation identity establish the martingale claim. \(\square\)

Computing Along Observed Paths

For a specific history with positive probability, conditioning on \(\mathcal{F}_n\) fixes the observed position \(X_n\), but not the next toss. The next increment remains equally likely to be \(1\) or \(-1\). The examples below calculate conditional expectations and variances directly, so that the role of the information being conditioned on is explicit.

Reading the Martingale Condition Correctly

The martingale statement is an equality of conditional expectations: after observing the position at time \(n\) and, in the natural filtration, the entire path through time \(n\), the expected next position is \(X_n\). It does not say that the next position equals \(X_n\) on every outcome. A fair walk can go up or down; those two possible changes balance in conditional mean.

It is also important to distinguish the conditional mean of the next position from its unconditional mean. For example, after the history \(HH\), the current position is \(2\), and the conditional mean of the next position is \(2\), not \(0\). The unconditional mean averages over all possible histories as well. The martingale condition compares the conditional mean with the current position, not with a fixed number independent of the observed history.

Common mistake. After observing \(HH\), one might incorrectly argue that the next position has conditional mean zero because heads and tails are equally likely. That calculation confuses the mean of the next increment with the mean of the next position. The increment has conditional mean \(\tfrac12(1)+\tfrac12(-1)=0\), but the position includes the already observed value \(X_2=2\). The correct calculation is \(\mathbb{E}[X_3\mid\mathcal{F}_2]=X_2+\mathbb{E}[\xi_3\mid\mathcal{F}_2]=2+0=2\).

The same distinction matters when interpreting variance. In every history, the conditional variance of the one-step increment is \(1\), because the next increment is \(1\) or \(-1\) with equal probability. This does not mean the conditional variance of the current position is \(1\): given \(\mathcal{F}_n\), \(X_n\) is already known and has conditional variance zero. Nor does the one-step calculation by itself state a result about a stopping time or a long-run limit.

The walk provides a basic example of how conditional drift identifies a martingale. The proof rests on the actual information available at each time and on the independence and fairness of the next toss. If either feature is changed, the conditional calculation must be checked again rather than inferred from the name of the process.