Absolute Values of Centered Random Walks

Why Absolute Values Create Drift

A martingale has no average one-step change once the present information is known. Applying a nonlinear function can change that: positive and negative fluctuations no longer cancel in the same way. For the absolute-value function, conditional Jensen’s inequality makes the direction of the change precise. In a simple symmetric random walk, the resulting conditional drift has an especially clear form: it is positive at the origin and zero at every other integer.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\) with a filtration \((\mathcal{F}_n)_{n\ge0}\), an increasing sequence of information sigma-fields. A process \((M_n)_{n\ge0}\) is a martingale with respect to this filtration if each \(M_n\) is integrable and \(\mathcal{F}_n\)-measurable and \(\mathbb{E}[M_{n+1}\mid\mathcal{F}_n]=M_n\) almost surely for every \(n\). A process \((Y_n)\) is a submartingale if it is integrable and adapted and \(\mathbb{E}[Y_{n+1}\mid\mathcal{F}_n]\ge Y_n\) almost surely for every \(n\).

The inequality needed here is the conditional version of the absolute-value case of Jensen’s inequality. The short proof also indicates why it applies even when the information in \(\mathcal{F}_n\) distinguishes different outcomes.

Proof. Fix \(n\), and let \(Z=\mathbb{E}[M_{n+1}\mid\mathcal{F}_n]\), which is \(\mathcal{F}_n\)-measurable. Define the \(\mathcal{F}_n\)-measurable random variable \(H\) by \(H=1\) on \(\{Z\ge0\}\) and \(H=-1\) on \(\{Z<0\}\). Then \(|H|\le1\), \(HZ=|Z|\), and the defining properties of conditional expectation give \(\lvert Z\rvert=H\mathbb{E}[M_{n+1}\mid\mathcal{F}_n]=\mathbb{E}[HM_{n+1}\mid\mathcal{F}_n]\). Since \(HM_{n+1}\le |M_{n+1}|\) pointwise, monotonicity of conditional expectation implies \(\lvert Z\rvert\le\mathbb{E}[|M_{n+1}|\mid\mathcal{F}_n]\) almost surely. The martingale property says \(Z=M_n\) almost surely, so this is the required inequality. Each \(|M_n|\) is integrable because \(\mathbb{E}|M_n|<\infty\), and it is \(\mathcal{F}_n\)-measurable because \(M_n\) is. Thus \((|M_n|)\) is a submartingale. \(\square\)

The theorem does not say that \((|M_n|)\) is itself a martingale. It only gives a nonnegative conditional drift; the drift can vanish at some states and be strictly positive at others. The next calculation identifies those states for a simple symmetric random walk.

Conditional Drift of a Simple Symmetric Random Walk

Let \((\Omega,\mathcal{F},\mathbb{P})\) carry independent random variables \((\xi_n)_{n\ge1}\), each equal to \(1\) and \(-1\) with probability \(\tfrac12\) each. Set \(S=\mathbb{Z}\), use discrete time \(n\ge0\), define \(S_0=0\) and \(S_n=\sum_{r=1}^n\xi_r\), and take \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). The increments have conditional mean zero given \(\mathcal{F}_n\), so the simple symmetric random walk is a martingale. Its absolute value has the following more detailed drift formula.

Proof. Given \(\mathcal{F}_n\), the value \(S_n=x\) is known, and the next increment is independent of \(\mathcal{F}_n\), with conditional probabilities \(\tfrac12\) for each of \(1\) and \(-1\). Therefore \(\mathbb{E}[|S_{n+1}|\mid\mathcal{F}_n]=\tfrac12|S_n+1|+\tfrac12|S_n-1|\) almost surely. Evaluate the right-hand side for each possible integer \(x=S_n\). If \(x=0\), it is \(\tfrac12|1|+\tfrac12|-1|=1\), so the drift is \(1-|0|=1\). If \(x\ge1\), then \(x+1\ge0\) and \(x-1\ge0\), so the conditional expectation is \(\tfrac12(x+1)+\tfrac12(x-1)=x=|x|\), and the drift is \(0\). If \(x\le-1\), then \(x+1\le0\) and \(x-1\le0\), so the conditional expectation is \(\tfrac12(-x-1)+\tfrac12(-x+1)=-x=|x|\), and again the drift is \(0\). These cases exhaust the integer state space and prove the formula. \(\square\)

In particular, the submartingale inequality is strict on the event \(\{S_n=0\}\), and it is an equality on \(\{S_n\ne0\}\). The event in this statement is random: at a fixed time \(n\), it can have positive probability, or it can be impossible, depending on the parity of \(n\).

From Conditional Drift to Expected Absolute Position

Taking expectations in the drift identity gives a recurrence for the ordinary expected absolute position. All the expectations are finite: \(|S_n|\le n\), since \(S_n\) is a sum of \(n\) increments, each of absolute value \(1\). The defining property of conditional expectation then gives \(\mathbb{E}|S_{n+1}|-\mathbb{E}|S_n|=\mathbb{P}(S_n=0)\). Starting at \(S_0=0\), this yields, for each \(n\ge1\), \(\mathbb{E}|S_n|=\sum_{r=0}^{n-1}\mathbb{P}(S_r=0)\). The term at time \(r\) is zero when \(r\) is odd, because a sum of an odd number of \(1\)'s and \(-1\)'s cannot equal zero. For \(r=2k\), there are \(\binom{2k}{k}\) sequences of increments with exactly \(k\) plus signs and \(k\) minus signs, out of \(2^{2k}\) equally likely sequences. Hence \(\mathbb{P}(S_{2k}=0)=\binom{2k}{k}/2^{2k}\).

The recurrence also explains the pattern behind the calculation: expected absolute position increases only through paths that are at zero at the preceding time. For example, starting at zero, the step from time \(0\) to time \(1\) contributes an expected increase of \(1\). The next step contributes no increase because the walk cannot be at zero at time \(1\). At the following step, paths at zero at time \(2\) contribute an increase weighted by their probability, \(\tfrac12\).

Common Mistake: Adding the Absolute Increment

A tempting but incorrect calculation is to treat \(|S_{n+1}|\) as \(|S_n|+|\xi_{n+1}|\). The triangle inequality gives \(|S_n+\xi_{n+1}|\le |S_n|+|\xi_{n+1}|\), not equality in general. At \(S_n=1\), the current absolute position is \(1\), and \(|\xi_{n+1}|=1\) for either possible increment. The incorrect calculation would therefore predict an expected next absolute position of \(1+1=2\). In fact, the next absolute position is \(2\) or \(0\), each with probability \(\tfrac12\), so its conditional expectation is \(\tfrac12(2)+\tfrac12(0)=1\). The correct drift is \(1-1=0\).

At the origin, the same mistaken rule happens to give the right numerical answer: the absolute position changes from \(0\) to \(1\). That special case does not justify using the rule elsewhere. The conditional calculation must retain both possible next positions, especially when a step can move the walk toward zero as well as away from it.