Proof sketch of Theorem 2.1, PDF p. 2 — given |Y ∩ T| = r, the expected modified value of Y is (r/k)v
ProvedMultiChoiceSecretary.Alg.modVal_given_cardconditional-expectationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-ordersecretary-problem
Let be a finite set of non-negative reals, , the largest elements of and their sum. The modified value of a set is the sum of its elements lying in . Let be the set of the first arrivals of a uniformly random order of , independent. Conditional on , the expected modified value of is . Multiplied by the probability of the event, this reads: for every ,
This is the "second consequence" in the proof sketch of Theorem 2.1.
Formalization Note. The conditional expectation is stated multiplied by , which avoids dividing by a probability. The hypothesis is added, as for the distribution of .
Preamble
import Mathlib import Definitions.Def_MultiChoiceSecretary_Alg_Setting
Formal statement
namespace MultiChoiceSecretary.Alg
theorem modVal_given_card (S : Finset ℝ) (hS : ∀ x ∈ S, 0 ≤ x) (k : ℕ) (hk : 1 ≤ k)
(hkn : k ≤ S.card) :
∀ r : ℕ, splitAvg S (fun Y => if (Y ∩ topK S k).card = r then modVal S k Y else 0) =
(k.choose r : ℝ) / 2 ^ k * ((r : ℝ) / k * topSum S k) := by sorry
end MultiChoiceSecretary.Alg
Source
Kleinberg, A multiple-choice secretary algorithm with applications to online auctions, SODA 2005, PDF p. 2, proof sketch of Theorem 2.1, "Second, conditional on the event |Y ∩ T| = r, the expected modified value of Y is (r/k)v."
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.