Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Observation 5 — p(π)=p(πA)+p(πB)p(\pi)=p(\pi_A)+p(\pi_B)p(π)=p(πA​)+p(πB​) for every partition π=A⊎B\pi=A\uplus Bπ=A⊎B

Proved
PandoraComb.observation_5

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatorial-costoptimal-stoppingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1pandoras-problemsequential-searchsubmodular-cost

Let π=(i1,…,ik)\pi=(i_1,\dots,i_k)π=(i1​,…,ik​) be an impulsive strategy (distinct boxes) on a Bernoulli instance with probabilities pip_ipi​, and let A,BA,BA,B be a partition of the set of boxes of π\piπ. With p(π)=1−∏j=1k(1−pij)p(\pi)=1-\prod_{j=1}^k(1-p_{i_j})p(π)=1−∏j=1k​(1−pij​​) and p(πP)=∑j: ij∈P∏l<j(1−pil) pijp(\pi_P)=\sum_{j:\,i_j\in P}\prod_{l<j}(1-p_{i_l})\,p_{i_j}p(πP​)=∑j:ij​∈P​∏l<j​(1−pil​​)pij​​ for the impulsive strategies with dummies,

p(π)=p(πA)+p(πB).p(\pi)=p(\pi_A)+p(\pi_B).p(π)=p(πA​)+p(πB​).

The probability that π\piπ 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
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me