Theorem: Finite-confidence recovery certificate

Under the contract and Assumption ass:statistics, suppose $\left|F_{\mathrm{obs}}-F_e\right|\le b_{\mathrm{cal}}$ on $G$. Set

Uniformly over the channels and nuisance parameters satisfying the contract,

For direct certification $b=0$, the same event gives

If “certified” is declared only when $U\le \epsilon$, then

Proof. Hoeffding's inequality Hoeffding gives, conditional on $\mathcal{Z}$,

A union bound gives simultaneous coverage at least $1-{\alpha }_{\mathrm{s}}$. On this event,

Intersecting with $G$ gives $|\hat{F}-F_e|\le R_{\mathrm{s}}+b_{\mathrm{cal}}$. Clipping preserves coverage because $F_e\in [0,1]$. Proposition prop:bellbounds gives the error interval. Integrate the conditional statistical failure bound and add $\mathrm{Pr}(G^c)\le \beta$. An invalid acceptance is contained in the upper-certificate failure event.