Manuscript En03-A@1 · En03-A.tex · section · 5398614e

Independent-run sampling

Conditional approximation and verification interfaces › Independent-run sampling · lines 3049–3079

En03-A@1#ip:record-sampling, En03-A@1#eq:complete-record-radius

A run, or a fresh sequence, is the independent unit CheungPsy03A,CheungPsy03D. Dependence between observations within a run does not increase $N$ . Failure and aborted outcomes must be included in the attempted-run law and assigned a prespecified score. Conditional successful-run sampling estimates a different law unless its selection correction is separately certified.

Let $P_{0}, P_{1}$ be complete laws on one finite alphabet $Ω$ , with $m = ∣ Ω ∣$ , and let $P_{j}$ be empirical laws from $N_{j}$ independent runs of each protocol. Put

r_{j} = \frac{lo g ( 4 m / α )}{2 N _{j}}, Δ = d_{TV} (P_{0}, P_{1}) .

With probability at least $1 - α$ ,

max {0, Δ - \frac{m}{2} (r_{0} + r_{1})} \leq d_{TV} (P_{0}, P_{1}) \leq min {1, Δ + \frac{m}{2} (r_{0} + r_{1})} .

Displayed formulas in this passage

En03-A@1#eq:complete-record-radius · line 3071
$max {0, Δ - \frac{m}{2} (r_{0} + r_{1})} \leq d_{TV} (P_{0}, P_{1}) \leq min {1, Δ + \frac{m}{2} (r_{0} + r_{1})} .$
unlabeled · line 3065
$r_{j} = \frac{lo g ( 4 m / α )}{2 N _{j}}, Δ = d_{TV} (P_{0}, P_{1}) .$

Independent-run sampling

Displayed formulas in this passage

Nearby in this section