Optimal search cost for sparse support
ProvedMomentSearch.Supplement.sparse_support_opt_upper_boundinformation-theorysearch
Let be a probability distribution on an ordered domain of size . If at most positions have positive mass, then
The strategy must identify every target, including positions of zero probability.
Preamble
import Mathlib import Definitions.Def_MomentSearch_OPT
Formal statement
theorem MomentSearch.Supplement.sparse_support_opt_upper_bound {n q : ℕ} (hn : 2 ≤ n) (hq : 0 < q) (p : Fin n → ℝ)
(hp : p ∈ stdSimplex ℝ (Fin n)) (hs : (Function.support p).ncard ≤ q) :
0 < MomentSearch.OPT p ∧ MomentSearch.OPT p ≤ 1 + Real.logb 2 q := by sorrySource
Megow, Stein, Verschae, Distributionally Robust Search: The Power of Information and the Limits of Moments, arXiv:2611.04559 (held version, sha256 fbfa4b43350dfaea073a9c0a9a0850a9955ea82082a7163a2db90cc48b9339e3), Theorem 6, p.8 (PDF p.10)