Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Fact 2 — the number of satisfied bin sequences is at least ℓ(1−2∣R∣/ec)−εdn−O(ℓ/n)\ell(1 - 2^{|R|}/e^c) - \varepsilon d n - O(\ell/n)ℓ(1−2∣R∣/ec)−εdn−O(ℓ/n)

Proved
OnlineStochMatching.TSM.fact_2

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

balls-in-binsconcentrationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1probability

Throw nnn balls independently and uniformly into nnn bins. Let B1,…,BℓB_1, \dots, B_\ellB1​,…,Bℓ​ be sequences of bins, each consisting of ccc distinct bins Ba=(b1,…,bc)B_a = (b_1, \dots, b_c)Ba​=(b1​,…,bc​), such that no bin lies in more than ddd of the sequences. Fix a set R⊆{1,…,c}R \subseteq \{1, \dots, c\}R⊆{1,…,c} of positions. A sequence BaB_aBa​ is satisfied if

  1. some bin bjb_jbj​ with j∉Rj \notin Rj∈/R receives at least one ball, or
  2. some bin bjb_jbj​ with j∈Rj \in Rj∈R receives at least two balls.

Let SSS be the number of satisfied sequences. If c2<nc^2 < nc2<n and ε>0\varepsilon > 0ε>0, then with probability at least 1−2e−ε2n/21 - 2e^{-\varepsilon^2 n/2}1−2e−ε2n/2,

S  ≥  ℓ(1−2∣R∣ec)−εdn−2∣R∣c2ec⋅ℓn−c2.S \;\ge\; \ell\Big(1 - \frac{2^{|R|}}{e^{c}}\Big) - \varepsilon d n - \frac{2^{|R|} c^2}{e^{c}} \cdot \frac{\ell}{n - c^2}.S≥ℓ(1−ec2∣R∣​)−εdn−ec2∣R∣c2​⋅n−c2ℓ​.

In the analysis of the two suggested matchings algorithm this bound, with c=2c = 2c=2 and d=2d = 2d=2, counts the advertisers of ABRA_{BR}ABR​, ABBA_{BB}ABB​ and ARA_RAR​ that end up assigned.

Formalization Note Positions are 0,…,c−10, \dots, c-10,…,c−1 (Fin c) rather than 1,…,c1, \dots, c1,…,c. Two hypotheses that the proof (Appendix A, pp. 12–13) uses without stating are made explicit: the ccc bins of each sequence are distinct, and c2<nc^2 < nc2<n, so that n−c2>0n - c^2 > 0n−c2>0. With a repeated bin the bound fails (for c=2c = 2c=2, R=∅R = \emptysetR=∅ and Ba=(b,b)B_a = (b, b)Ba​=(b,b) the sequence is unsatisfied with probability about 1/e>1/e21/e > 1/e^21/e>1/e2).

Preamble
import Mathlib
import Definitions.Def_OnlineStochMatching_TSM_Model
Formal statement
namespace OnlineStochMatching.TSM

open Finset

/-- **Fact 2** (Feldman, Mehta, Mirrokni, Muthukrishnan, *Online Stochastic Matching: Beating
1-1/e*, arXiv:0905.4100v1, §2.1, p. 4; proof App. A, pp. 12–13). Throw `n` balls i.i.d. uniformly
into `n` bins (`balls t` is the bin of ball `t`). Let `B 0, …, B (ℓ-1)` be sequences of `c`
distinct bins each (`B a j` is the `j`-th bin of the `a`-th sequence, positions `0, …, c-1`), with
no bin in more than `d` sequences, and fix a set `R` of positions. Sequence `a` is *satisfied* if
some bin at a position outside `R` has at least one ball, or some bin at a position in `R` has at
least two balls; `S` is the number of satisfied sequences. If `c² < n` and `ε > 0`, then with
probability at least `1 - 2 exp(-ε² n / 2)`,
`S ≥ ℓ (1 - 2^{|R|}/e^c) - ε d n - (2^{|R|} c² / e^c) · ℓ / (n - c²)`.

The hypotheses `c² < n` (so that `n - c² > 0`) and that the bins of each sequence are distinct are
used by the proof (the factor `(1 - c/n)^{n - |R'|}`) without being stated on the page; with
repeated bins the bound fails. -/
theorem fact_2 (n c ℓ d : ℕ) (hcn : c ^ 2 < n) (B : Fin ℓ → Fin c → Fin n)
    (hB : ∀ a, Function.Injective (B a))
    (hd : ∀ b : Fin n, (Finset.univ.filter fun a : Fin ℓ => ∃ j, B a j = b).card ≤ d)
    (R : Finset (Fin c)) (ε : ℝ) (hε : 0 < ε) :
    1 - 2 * Real.exp (-(ε ^ 2 * n / 2)) ≤
      prob n (fun balls : Fin n → Fin n =>
        (ℓ : ℝ) * (1 - 2 ^ R.card / Real.exp 1 ^ c) - ε * d * n
            - (2 ^ R.card * (c : ℝ) ^ 2 / Real.exp 1 ^ c) * ((ℓ : ℝ) / ((n : ℝ) - (c : ℝ) ^ 2)) ≤
          ((Finset.univ.filter fun a : Fin ℓ =>
              (∃ j, j ∉ R ∧ 1 ≤ (Finset.univ.filter fun t => balls t = B a j).card) ∨
              (∃ j, j ∈ R ∧ 2 ≤ (Finset.univ.filter fun t => balls t = B a j).card)).card : ℝ)) := by sorry

end OnlineStochMatching.TSM
Source
Feldman, Mehta, Mirrokni, Muthukrishnan, Online Stochastic Matching: Beating 1-1/e, arXiv:0905.4100v1, p. 4, Fact 2 (Section 2.1); restated p. 12 and proved p. 13, Appendix A
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me