Fact 1 — occupancy of a subset of bins concentrates
ProvedOnlineStochMatching.SuggestedMatching.fact_1balls-in-binsconcentrationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Throw balls independently and uniformly into bins. For any fixed subset and any , let count its occupied bins. Then
This concentration fact controls how many advertisers of a selected matching are chosen. The printed Fact 1 has in the exponent; its Appendix A proof gives the squared exponent encoded here.
Preamble
import Definitions.Def_OnlineStochMatching_SuggestedMatching_BallsInBins
Formal statement
namespace OnlineStochMatching.SuggestedMatching
/-- Fact 1, with the squared exponent established by its Appendix A proof. -/
theorem fact_1 (n : ℕ) (hn : 0 < n) (B : Finset (Fin n))
(ε : ℝ) (hε : 0 < ε) :
uniformProbability (fun ω : Fin n → Fin n =>
(B.card : ℝ) * (1 - Real.exp (-1)) - ε * (n : ℝ) ≤
(occupiedIn n B ω : ℝ) ∧
(occupiedIn n B ω : ℝ) ≤
(B.card : ℝ) *
(1 - Real.exp (-1) + 1 / (Real.exp 1 * (n : ℝ))) + ε * (n : ℝ)) ≥
1 - 2 * Real.exp (-(ε ^ 2) * (n : ℝ) / 2) := by sorry
end OnlineStochMatching.SuggestedMatching
Source
Feldman, Mehta, Mirrokni, Muthukrishnan, Online Stochastic Matching: Beating 1-1/e, arXiv:0905.4100v1, p. 4, Fact 1; p. 12, Appendix A, Proof of Fact 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.