Observation 5 — for every partition
ProvedPandoraComb.observation_5combinatorial-costoptimal-stoppingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1pandoras-problemsequential-searchsubmodular-cost
Let be an impulsive strategy (distinct boxes) on a Bernoulli instance with probabilities , and let be a partition of the set of boxes of . With and for the impulsive strategies with dummies,
The probability that finds a non-zero value splits along the partition; this is used together with Lemma 3.3 in the proof of Lemma 3.1.
Differences from the source:
- generalization: probabilities p_i ∈ [0, 1] (p_i > 0 in §3.1), boxes in [n] → any real numbers p i, boxes in any type ι with decidable equality; reason: the identity is algebraic (a telescoping sum); the paper's probabilities and boxes are an instance
- encoding: p(π), p(π_A), p(π_B) as probabilities of the events "some inspected box is non-zero" (pp.10–11) → the closed forms pL p l = 1 − ∏(1 − p_i) and pD p l P; reason: these are the paper's own formulas: Observation 2 (p.10) and the dummies example (p.11)
Preamble
import Definitions.Def_PandoraComb_ClosedForms
Formal statement
namespace PandoraComb
/-- **Observation 5** (arXiv:2303.01078v1, p.12): "For any impulsive strategy π ⊆ [n] and for any
partition π = A ⊍ B of the set of boxes corresponding to π, we have p(π) = p(π_A) + p(π_B)."
**Formalization Note.** The impulsive strategy is the tuple `l` without repetition; `p(π)` is
`pL p l = 1 − ∏ (1 − p_i)` (p.10) and `p(π_A)`, `p(π_B)` are the probabilities `pD` for the
strategies with dummies (p.11). The probabilities `p i` may be any reals. -/
theorem observation_5 {ι : Type*} [DecidableEq ι] (p : ι → ℝ) (l : List ι) (hl : l.Nodup)
(A B : Finset ι) (hAB : Disjoint A B) (hcover : A ∪ B = l.toFinset) :
pL p l = pD p l A + pD p l B := by sorry
end PandoraComb
Source
Berger, Ezra, Feldman & Fusco, Pandora’s Problem with Combinatorial Cost, arXiv:2303.01078v1, Observation 5, p.12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.