Lemma 11 — signed corrections give two distributions with the same moments
ProvedMomentSearch.lemma_11distributionally-robust-optimizationlower-boundsmomentsp2o-gran-per-chapterp2o-plan-paperp2o-v1search
Let , , , and let solve the signed-correction system
Then there are two distributions with the same first moments ( for ) such that
It reduces the construction of moment-matching distributions with separated peaks to finding a signed correction of small -norm.
Differences from the source:
- encoding: m, m₀ ∈ [n]₀ and a ∈ ℝⁿ → m m₀ : Fin n and a : Fin n → ℝ; reason: Lean convention; same instances
Preamble
import Mathlib import Definitions.Def_MomentSearch_moment import Definitions.Def_MomentSearch_SolvesCorrection
Formal statement
namespace MomentSearch
/-- **Lemma 11** (signed corrections and distributions), Megow, Stein, Verschae, *Distributionally Robust Search: The Power of Information and the Limits of Moments*, arXiv:2611.04559 (held version, sha256 fbfa4b43…), §4.1, p.11 (PDF p.13);
restated App. C.1, p.21 (PDF p.23).
Let `m, m₀ ∈ [n]₀`. If `a` solves Equation (3) (`∑_t a_t τ_t^i = τ_m^i − τ_{m₀}^i`, `i = 0, …, k`),
then there are two distributions `p, p'` on `[n]₀` with the same first `k` moments and
`p_m, p'_{m₀} ≥ 1 − ½‖a‖₁`.
**Formalization Note.** Distributions are points of `stdSimplex ℝ (Fin n)`; "the same first `k`
moments" is `µ_i(p) = µ_i(p')` for `i = 0, …, k`; `‖a‖₁ = ∑_t |a_t|`; `n ≥ 2` is the paper's
standing assumption (§2.1). -/
theorem lemma_11 {n : ℕ} (hn : 2 ≤ n) (k : ℕ) (m m₀ : Fin n) (a : Fin n → ℝ)
(ha : SolvesCorrection n k m m₀ a) :
∃ p p' : Fin n → ℝ, p ∈ stdSimplex ℝ (Fin n) ∧ p' ∈ stdSimplex ℝ (Fin n) ∧
(∀ i : ℕ, i ≤ k → moment p i = moment p' i) ∧
1 - (1 / 2) * ∑ t : Fin n, |a t| ≤ p m ∧
1 - (1 / 2) * ∑ t : Fin n, |a t| ≤ p' m₀ := by sorry
end MomentSearch
Source
Megow, Stein, Verschae, Distributionally Robust Search: The Power of Information and the Limits of Moments, arXiv:2611.04559 (held version, sha256 fbfa4b43…), §4.1, Lemma 11, p.11 (PDF p.13); restated App. C.1, p.21 (PDF p.23)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.