Manuscript Hawk01-A@1 · Hawk01-A.tex · theorem · 11979653

Theorem: Independent-attempt rejection certificate

Complete-attempt assessment and observability › A finite-sample certificate · lines 2092–2139 · proof included or linked

Hawk01-A@1#thm:sampling, Hawk01-A@1#eq:hoeffding, Hawk01-A@1#eq:rejection, Hawk01-A@1#eq:powerbound

Back to manuscript

Suppose $W_{1}, \dots, W_{n}$ are independent and each null mean is at most $b$ . Then for $t > 0$ ,

null Pr (Q_{n} \geq b + t) \leq e^{- 2 n t^{2}} .

Thus at significance level $ζ \in (0, 1)$ , the null is rejected whenever

Q_{n} > b + \frac{lo g ( 1/ ζ )}{2 n} .

If a model predicts a score lower bound $q_{-}$ and $q_{-} > b$ , then under independent attempts with means at least $q_{-}$ ,

Pr (Q_{n} \leq q_{-} - t) \leq e^{- 2 n t^{2}} .

Proof. For a bounded variable $W \in [0, 1]$ ,

E e^{s (W - E W)} \leq e^{s^{2} /8} .

For Bernoulli $W$ , this follows by differentiating the log moment-generating function twice: its second derivative is a Bernoulli variance and is at most $1/4$ ; the value and first derivative at zero vanish. Independence and Chernoff's inequality give

Pr (i \sum (W_{i} - E W_{i}) \geq n t) \leq s > 0 in f e^{- s n t + n s^{2} /8} = e^{- 2 n t^{2}} .

The null means satisfy $\sum_{i} E W_{i} \leq nb$ , proving (eq:hoeffding). Apply the same argument to $- W_{i}$ for (eq:powerbound).

Displayed formulas in this passage

Hawk01-A@1#eq:hoeffding · line 2096
$null Pr (Q_{n} \geq b + t) \leq e^{- 2 n t^{2}} .$
Hawk01-A@1#eq:rejection · line 2103
$Q_{n} > b + \frac{lo g ( 1/ ζ )}{2 n} .$
Hawk01-A@1#eq:powerbound · line 2111
$Pr (Q_{n} \leq q_{-} - t) \leq e^{- 2 n t^{2}} .$
unlabeled · line 2121
$E e^{s (W - E W)} \leq e^{s^{2} /8} .$
unlabeled · line 2130
$Pr (i \sum (W_{i} - E W_{i}) \geq n t) \leq s > 0 in f e^{- s n t + n s^{2} /8} = e^{- 2 n t^{2}} .$

Theorem: Independent-attempt rejection certificate

Displayed formulas in this passage

Nearby in this section