Manuscript Psy04-B@1 · Psy04-B-v1.tex · lemma · 62c2b6f0

Lemma: Conditional bounded-score concentration

Finite-sample exclusion conditional on the cut · lines 2058–2107 · proof included or linked

Psy04-B@1#lem:concentration

For $S_{i} \in [0, 1]$ , set

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

For real $u$ ,

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

For fixed $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]$ , let

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

Its value and first derivative vanish at zero, 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$ .

Iterated conditional expectation bounds the centered sum's moment by $e^{N u^{2} /8}$ . Markov's inequality yields

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 2061
$μ_{i} = E [S_{i} ∣ F_{i - 1}] .$
unlabeled · line 2065
$E [e^{u (S_{i} - μ_{i})} F_{i - 1}] \leq e^{u^{2} /8} .$
unlabeled · line 2072
$P {\frac{1}{N} i = 1 \sum^{N} (S_{i} - μ_{i}) \geq r} \leq e^{- 2 N r^{2}},$
unlabeled · line 2082
$E [e^{u S_{i}} ∣ F_{i - 1}] \leq 1 - μ_{i} + μ_{i} e^{u} .$
unlabeled · line 2087
$K_{p} (u) = lo g (1 - p + p e^{u}) - p u .$
unlabeled · line 2091
$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 2101
$e^{- u N r + N u^{2} /8} .$