Manuscript Psy04-A@1 · Psy04-A-v1.tex · lemma · d5800e2a

Lemma: Conditional bounded-score exponential estimate

Finite-sample exclusion certificates › A conditional exponential bound · lines 1166–1220 · proof included or linked

Psy04-A@1#lem:conditionalmgf, Psy04-A@1#eq:mgf, Psy04-A@1#eq:conditionaltail

If $S_{i} \in [0, 1]$ and

μ_{i} = E [S_{i} ∣ F_{i - 1}],

then for every real $u$ ,

E [e^{u (S_{i} - μ_{i})} F_{i - 1}] \leq e^{u^{2} /8} .

Consequently, for deterministic $N$ and $r > 0$ ,

P {\frac{1}{N} i = 1 \sum^{N} (S_{i} - μ_{i}) \geq r} \leq e^{- 2 N r^{2}},

and the same bound holds for the lower tail.

Proof. Convexity on $[0, 1]$ gives

E [e^{u S_{i}} ∣ F_{i - 1}] \leq 1 - μ_{i} + μ_{i} e^{u} .

For fixed $p \in [0, 1]$ , define

K_{p} (u) = lo g (1 - p + p e^{u}) - p u .

It satisfies $K_{p} (0) = K_{p}^{'} (0) = 0$ and

K_{p}^{''} (u) = p_{u} (1 - p_{u}) \leq \frac{1}{4}, p_{u} = \frac{p e ^{u}}{1 - p + p e ^{u}} .

Integrating twice gives $K_{p} (u) \leq u^{2} /8$ . This proves (eq:mgf), including the endpoint cases.

Iterate conditional expectation to bound the moment of the centered sum by $e^{N u^{2} /8}$ . Markov's inequality gives

P {i \sum (S_{i} - μ_{i}) \geq N r} \leq e^{- u N r + N u^{2} /8} .

Optimize at $u = 4 r$ . Use negative $u$ for the lower tail. This is the bounded-variable argument underlying Hoeffding's inequality Hoeffding.

Displayed formulas in this passage

unlabeled · line 1169
$μ_{i} = E [S_{i} ∣ F_{i - 1}],$
Psy04-A@1#eq:mgf · line 1173
$E [e^{u (S_{i} - μ_{i})} F_{i - 1}] \leq e^{u^{2} /8} .$
Psy04-A@1#eq:conditionaltail · line 1181
$P {\frac{1}{N} i = 1 \sum^{N} (S_{i} - μ_{i}) \geq r} \leq e^{- 2 N r^{2}},$
unlabeled · line 1192
$E [e^{u S_{i}} ∣ F_{i - 1}] \leq 1 - μ_{i} + μ_{i} e^{u} .$
unlabeled · line 1197
$K_{p} (u) = lo g (1 - p + p e^{u}) - p u .$
unlabeled · line 1201
$K_{p}^{''} (u) = p_{u} (1 - p_{u}) \leq \frac{1}{4}, p_{u} = \frac{p e ^{u}}{1 - p + p e ^{u}} .$
unlabeled · line 1212
$P {i \sum (S_{i} - μ_{i}) \geq N r} \leq e^{- u N r + N u^{2} /8} .$