DiscreteDist
structure
A discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative probabilities summing to 1, and non-negative support elements.
Statement
structure DiscreteDist where support : Finset ℝ prob : ℝ → ℝ prob_nonneg : ∀ v ∈ support, 0 ≤ prob v sum_prob_one : ∑ v ∈ support, prob v = 1 val_nonneg : ∀ v ∈ support, 0 ≤ v
- Defined in
- arXiv:2610.13775, Sec. 2.1
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Used by 28
- two_box_pi01_validThe policy "open box 0, then box 1, then stop" is valid for the two-box instance.
- two_box_risky_value_meanThe mean of the risky distribution is 1.
- expected_utility_dus_le_opt_dusFor any Pandora's problem instance with deadlines
instand any valid policyπ,expectedUtilityDUS inst π ≤ optDUS inst. - pandora_is_reservationr is a vector of reservation values: for every box i, the expected excess E[(v_i - r_i)^+] of its value over r_i equals its opening cost…
- pandora_exists_deadline_orderLemma 2: a deadline-feasible set can be listed without repetition so that the j-th box (j from 1) has deadline at least j.
- two_box_dtd_le_oneUnder deferred-to-deadline commitment, every valid policy on the two-box instance gets expected utility at most 1.
- two_box_valid_stop_of_mem_oneIf a valid policy execution has box 1 in its already-opened list and at least one round has elapsed, then the remaining policy is
stop. - not_single_box_valid_is_partially_adaptiveThe statement
single_box_valid_is_partially_adaptiveis false: The statement is false.IsValidPolicyonly constrains the continuation… - two_box_pi01_dusThe DUS utility of the policy opening box 0 then box 1 is
2 - 1/M. - two_box_deadline_instTwo boxes with zero cost: box 0 has deadline 1 and deterministic value 1; box 1 has deadline 2, value
Mwith probability1/Mand 0… - expected_utility_dtd_le_dusFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstanceand every adaptive policy… - expectedUtilityDTDThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-to-deadline commitment on a Pandora's problem… - pandora_deadline_feasibleA set S of boxes is deadline-feasible if for every j at most j of its boxes have deadline at most j (equivalently, by Lemma 2, its boxes…
- opt_dtd_le_opt_dusFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, the optimal expected utility under… - two_box_dtd_after_box_zeroWith the history
[(0, 1)], any valid policy has deferred-to-deadline expected utility at most 1. - op184_partially_adaptive_half_approximationFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, there exists a valid partially adaptive policy… - pandora_threshold_policy_lower_boundLemma 3: for reservation values r, t >= 0 and a duplicate-free list of boxes each with positive capped surplus at t, the threshold policy…
- IsValidPolicyAuxA policy execution is valid if it never re-opens an already opened box, respects the deadline of each opened box, and remains valid on all…
- pandora_adaptive_surplus_upper_boundLemma 1: for reservation values r and any threshold t >= 0, every valid adaptive policy has expected DUS utility at most t plus the total…
- pandora_capped_surplusThe reservation-capped threshold surplus of box i at threshold t: w_i(t) = E[(min(v_i, r_i) - t)^+].
- two_box_fair_value_distThe degenerate discrete distribution taking the value
1with probability1. - expectedUtilityDUSThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-until-stopping commitment on a Pandora's problem… - PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
- two_box_risky_value_distThe distribution taking the value
Mwith probability1/Mand the value0with probability1 - 1/M. - pandora_threshold_policyThe threshold policy on a list of boxes: open them in the given order and stop as soon as an opened value exceeds t (stop after the last…
- pandora_exists_reservationEvery Pandora instance with deadlines has reservation values: for every box i there is r_i with E[(v_i - r_i)^+] = c_i.
- pandora_exists_balancing_thresholdThere is a threshold t >= 0 at which the maximum total capped surplus over deadline-feasible sets equals t, attained by some feasible set.
- pandora_threshold_policy_validA threshold policy on a duplicate-free list whose j-th box has deadline at least j is a valid policy and is partially adaptive.
Read back from the Lean
A structure DiscreteDist bundling:
1. support: a finite set of real numbers (Finset ℝ);
2. prob: a function from ℝ to ℝ;
3. prob_nonneg: a proof that for every v ∈ support, 0 ≤ prob v;
4. sum_prob_one: a proof that the sum of prob v over all v ∈ support equals 1;
5. val_nonneg: a proof that for every v ∈ support, 0 ≤ v (with a default proof given by sorry).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A discrete probability distribution with finite support on non-negative real numbers. -/ structure DiscreteDist where support : Finset ℝ prob : ℝ → ℝ prob_nonneg : ∀ v ∈ support, 0 ≤ prob v sum_prob_one : ∑ v ∈ support, prob v = 1 val_nonneg : ∀ v ∈ support, 0 ≤ v