Manuscript Oai280-B@1 · Oai280-B.tex · proposition · 6d92ab75

Proposition: Best-case Hoeffding acceptance

Feasibility, binomial inversion, and channel structure › The sample requirement comes before an experiment · lines 1488–1528 · proof included or linked

Oai280-B@1#prop:samples, Oai280-B@1#eq:hoeffsamples

Back to manuscript

Fix $0 < ε < 1$ , equal counts $n_{A j} = n$ , and zero allowances. Even the best possible scores can pass $U_{A} \leq ε$ only if

n \geq \frac{18}{ε ^{4}} lo g \frac{6 K}{α _{s}} .

Conversely, this inequality permits acceptance for best-case scores.

With nonzero allowances, define

t_{A} = \frac{( ε - b _{A} ) ^{2}}{4} - b_{cal, A} .

For finite best-case acceptance one needs $ε > b_{A}$ , $t_{A} > 0$ , and

n \geq \frac{9}{8 t _{A} ^{2}} lo g \frac{6 K}{α _{s}} .

Proof. For equal counts,

R_{A} = \frac{3}{4} \frac{2}{n} lo g \frac{6 K}{α _{s}} .

Since $F_{A} \leq 1$ , its best possible lower fidelity is $[1 - R_{A} - b_{cal, A}]_{[0, 1]}$ . For $ε < 1$ , acceptance is equivalent to

R_{A} + b_{cal, A} \leq \frac{( ε - b _{A} ) ^{2}}{4},

with the stated positive margins. Squaring and rearranging gives the second formula. With zero allowances, $t_{A} = ε^{2} /4$ , which gives (eq:hoeffsamples).

Displayed formulas in this passage

Oai280-B@1#eq:hoeffsamples · line 1493
$n \geq \frac{18}{ε ^{4}} lo g \frac{6 K}{α _{s}} .$
unlabeled · line 1502
$t_{A} = \frac{( ε - b _{A} ) ^{2}}{4} - b_{cal, A} .$
unlabeled · line 1507
$n \geq \frac{9}{8 t _{A} ^{2}} lo g \frac{6 K}{α _{s}} .$
unlabeled · line 1515
$R_{A} = \frac{3}{4} \frac{2}{n} lo g \frac{6 K}{α _{s}} .$
unlabeled · line 1521
$R_{A} + b_{cal, A} \leq \frac{( ε - b _{A} ) ^{2}}{4},$

Proposition: Best-case Hoeffding acceptance

Displayed formulas in this passage

Nearby in this section