Proof sketch of Theorem 2.1, PDF p. 2 — |Y ∩ T| has the distribution B(k, 1/2)
ProvedMultiChoiceSecretary.Alg.card_inter_top_binomialbinomialp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-ordersecretary-problem
Let be a finite set of real numbers, , and let be the largest elements of . Let be the set of the first arrivals of a uniformly random order of , with independent. Then has the binomial distribution : for every ,
This is the "first consequence" of being a uniform random subset in the proof sketch of Theorem 2.1.
Formalization Note. The hypothesis is added: the page leaves it implicit. For the set has elements and , not .
Preamble
import Mathlib import Definitions.Def_MultiChoiceSecretary_Alg_Setting
Formal statement
namespace MultiChoiceSecretary.Alg
theorem card_inter_top_binomial (S : Finset ℝ) (k : ℕ) (hk : 1 ≤ k) (hkn : k ≤ S.card) :
∀ r : ℕ, splitAvg S (fun Y => if (Y ∩ topK S k).card = r then 1 else 0) =
(k.choose r : ℝ) / 2 ^ 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, "First, the random variable |Y ∩ T| has the distribution B(k, 1/2)."
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.