Proof sketch of Theorem 2.1, PDF p. 2 — the first m arrivals, m ~ B(n, 1/2), form a uniform random subset of S
ProvedMultiChoiceSecretary.Alg.prefix_uniform_subsetbinomialp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-ordersecretary-problem
Let be a finite set of real numbers revealed in a uniformly random order, and let be independent of the order. Let be the set of the first arrivals. Then is uniformly distributed on the subsets of : for every ,
This is the first step of the proof sketch of Theorem 2.1; every later claim about rests on it.
Formalization Note. is the split average of the indicator of .
Preamble
import Mathlib import Definitions.Def_MultiChoiceSecretary_Alg_Setting
Formal statement
namespace MultiChoiceSecretary.Alg
theorem prefix_uniform_subset (S : Finset ℝ) :
∀ A ⊆ S, splitAvg S (fun Y => if Y = A then 1 else 0) = (1 / 2 : ℝ) ^ S.card := 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, "Since m has distribution B(n, 1/2), it follows that Y is a sample from the uniform distribution on all 2^n subsets of S."
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.