Manuscript En01-B@2 · En01-B-v2.tex · theorem · f226d1eb

Theorem: Route B: robust bounded-statistic certificate

Bounded complete-record certificates · lines 2260–2293 · proof included or linked

En01-B@2#thm:bounded

Suppose

g = Θ_{1} in f q_{1} - Θ_{0} sup q_{0} > 0.

If actual laws are within total variation $e_{h}$ of the corresponding specified family members, put

g_{*} = g - e_{0} - e_{1} .

For $g_{*} > 0$ , the midpoint threshold between the two enlarged expectation ranges, applied to $N$ independent attempted runs, has each error at most

e^{- N g_{*}^{2} /2} .

Consequently

N \geq \frac{2}{g _{*}^{2}} lo g \frac{1}{α}

is sufficient for each error to be at most $α$ . The reversed orientation is equally valid.

Proof. For $0 \leq f \leq 1$ , total variation bounds the expectation difference. This follows by integrating the events ${f > u}$ , $u \in [0, 1]$ . The enlarged ranges are separated by $g_{*}$ . The threshold is at least $g_{*} /2$ from either range. Hoeffding's one-sided bound gives $e^{- 2 N (g_{*} /2)^{2}}$ Hoeffding1963.

Displayed formulas in this passage

unlabeled · line 2263
$g = Θ_{1} in f q_{1} - Θ_{0} sup q_{0} > 0.$
unlabeled · line 2269
$g_{*} = g - e_{0} - e_{1} .$
unlabeled · line 2275
$e^{- N g_{*}^{2} /2} .$
unlabeled · line 2279
$N \geq \frac{2}{g _{*}^{2}} lo g \frac{1}{α}$

Theorem: Route B: robust bounded-statistic certificate

Displayed formulas in this passage

Nearby in this section