Learning-guided sampling: finite classes and one-sided reliability

Abstract

We study sampling from an unknown member of a known finite class using approximate prefix masses. Under pointwise guidance with factor 9/4 and error 1/16, the worst-case query complexity is min{M, n√(log M), n²} up to logarithms. We show that one-sided safety and bounded stopped reciprocal capacity can change the cost of a specified class from logarithmic to linear, with exact linear caps at fixed error and for exact sampling. For a known background plus an unknown atom of weight α, we determine the worst-case rate over backgrounds as Θ(1 + min{αM, α⁻¹log(1 + 2ⁿα²)}) at error at most α/4. A uniform background admits a sharper rate. The upper bounds derive membership tests and atom recovery from the guide; independent fallback sampling controls the complete output law. A composition theorem separates global certification from difficult fixed-error sampling. We also give a self-contained quadratic upper bound under weak guidance. The general fixed-error finite-class gap remains open. The numbered results are formalized in Lean 4, with the cited finite-class upper bound as an explicit hypothesis.