Theorem: Sampling with explicit dependence assumptions

For a score in $[0,1]$, actual null mean at most $a$, alternative mean at least $b$, and $g=b-a>0$, a midpoint test on $N$ independent attempted runs has

Thus $N\ge 2g^{-2}\log (1/{\alpha }_{\ast })$ bounds each error by ${\alpha }_{\ast }$.

The same result holds under dependence if these mean bounds hold conditional on every past record. Unconditional mean bounds alone do not suffice.

Proof. Hoeffding's bound gives the independent result Hoeffding. For dependence, the conditional Hoeffding lemma gives

Iterate and optimize the exponential bound. Repeating one common Bernoulli variable supplies a counterexample under arbitrary dependence.