Martingale Bernstein and Freedman's inequality

Let M_k start at zero and be a square-integrable real martingale adapted to a filtration F_k. Write X_k=M_k−M_(k−1), so E[X_k|F_(k−1)]=0. Its predictable quadratic variation V_k is the sum of E[X_j²|F_(j−1)]. Each contribution is known before the corresponding increment, though the accumulated V_k can itself be random. It is generally different from the optional sum of the realized X_j², which is observable only after those increments occur.

Assume X_k≤b almost surely for a deterministic b>0 at every step. This is an upper bound for an upper-tail result; controlling a negative crossing instead requires a bound on −X_k. Conditional Bennett-type estimates produce an exponential supermartingale with a variance compensator. Iterated conditioning replaces the independent product used earlier. The method does not require the increments to be independent, but conditional centering and the almost-sure bound must hold for the actual filtration and adaptive rule, not just for their marginal distributions.

For deterministic t≥0 and v>0, Freedman bounds the probability that there exists any time k with M_k≥t and V_k≤v by exp(−t²/(2(v+bt/3))). The time-uniform event permits a stopping-time interpretation: a large positive fluctuation occurs before too much predictable variance has accumulated. The same expression also bounds the corresponding joint event at any fixed time. If V_n≤v almost surely for a chosen horizon, it yields an ordinary upper-tail bound there.

One cannot replace v by the observed random value V_n inside the right-hand side and call the result an unconditional probability bound. The theorem compares one event with one deterministic budget. Uniform bounds over many variance levels can be obtained through additional arguments such as peeling, but their cost must be included. Likewise a small realized sum of squared increments does not imply a small predictable variance on that sample path. A process can repeatedly realize modest values while retaining a substantial conditional chance of a larger next increment.

Suppose fresh Bernoulli observations B_k of fixed probability p are independent of the past. Before seeing B_k, select an activation A_(k−1) between zero and one using only past information, then take X_k=A_(k−1)(B_k−p). Conditional centering survives because the activation is predictable. Its conditional variance is A_(k−1)²p(1−p), and the upper increment bound is 1−p. Selecting activation after seeing the current B_k would generally break the centering argument.

For activations restricted to zero or one, the predictable variance counts active trials times p(1−p). It does not require all active times to be fixed in advance. Independent-sum Bernstein is recovered when all activations equal one and the horizon is deterministic. This comparison clarifies what adaptive concentration adds: it allows the sampling rule to respond to observed history while retaining a quantified variance budget, rather than pretending the selected data remain an ordinary independent sample.