Doob Martingales

SECTION 01From Independent Sums to General Functions

We have derived bounds for sums of independent random variables. Many problems instead require bounds for more general functions of random variables.

Setting · Control a Function’s Deviation from Its Mean

Let X₁, …, Xₙ be independent random variables, and consider f(X) = f(X₁, …, Xₙ), where f: ℝⁿ → ℝ and E[|f(X)|] < ∞. Our goal is to control f(X) − E[f(X)].

Definition · Doob Martingale

Reveal the inputs one at a time. After observing X₁, …, Xₖ, define

Y_{k} = E [f (X) | X_{1}^{k}], k = 1, \dots, n - 1

where we write $X_{1}^{k} = (X_{1}, \dots, X_{k})$ .

The endpoints are

Y_{0} = E [f (X)], Y_{n} = f (X)

The sequence {Yₖ} is called the Doob martingale.

f (X) - E [f (X)] = Y_{n} - Y_{0} = \sum_{k = 1}^{n} \underset{D_{k}}{\underset{⏟}{(Y_{k} - Y_{k−1})}}

The increments {Dₖ} form a martingale difference sequence.^[1] Since their sum equals f(X) − E[f(X)], we can control the deviation of f(X) from its mean by controlling the fluctuations of {Dₖ}.

Claim · Zero Conditional Mean

The Doob increments satisfy

E [D_{k} | X_{1}^{k−1}] = 0

Proof of the Claim

By definition,

Y_{k} = E [f (X) | X_{1}^{k}], D_{k} = Y_{k} - Y_{k−1}

Given X₁ᵏ⁻¹, the previous prediction Yₖ₋₁ is already known. Therefore,

E [D_{k} | X_{1}^{k−1}] = E [Y_{k} | X_{1}^{k−1}] - Y_{k−1}

E [D_{k} | X_{1}^{k−1}] = Y_{k−1} - Y_{k−1} = 0

The second equality uses the tower property: averaging the updated prediction over the unseen next input recovers the previous prediction.^[2]