AFTD Auto-Formalizing Theoretical Domains

team_tail

def

Poisson-binomial upper tail: team_tail [q₁, …, qₙ] t is the probability that at least t of n independent events with success probabilities q₁, …, qₙ occur (first-step recursion; team_tail_eq_sum below identifies it with the explicit sum over outcome vectors).

Statement

noncomputable def team_tail : List ℝ → ℕ → ℝ
Defined in
The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2); formalized by the operator (Claude), 2026-10-05
Verified
05 Oct 2026
Axioms
none listed
Used by 11
  • team_tail_eq_sumteam_tail equals the explicit sum over outcome vectors Σ_ω [t ≤ #wins(ω)] Π_i (q_i if ω_i else 1 - q_i).
  • team_winProbWinning probability of a line-up in the Team Order problem of arXiv:2605.21234: team 1 wins if it wins at least ⌊n/2⌋ + 1 of the n…
  • team_T_tailIn the alternating list 0,1,...,0 with m ones, at least m successes happen surely and more than m never.
  • team_tail_gtThe probability of more successes than there are events is 0.
  • team_tail_zeroThe probability of at least 0 successes is 1.
  • team_tail_nonnegUpper-tail probabilities of independent events with probabilities in [0,1] are nonnegative.
  • team_T2_tailFor the list 0,b,...,0 with m copies of b, the probability of at least m successes is at least b^m.
  • team_half_oddAn odd number 2m+3 of fair coins: at least m+2 heads with probability 1/2.
  • team_O_tailWith m sure wins, m+1 sure losses and two matches won with probability 3/4, winning at least m+2 matches has probability 9/16.
  • team_half_symmSymmetry of the fair binomial: S_k(t) + S_k(k+1-t) = 1.
  • team_rot_winProb2The rotation line-up of the strengthened instance wins with probability at least 1/2 + 1/40.

Lean source view module on GitHub

/-- Poisson-binomial upper tail: `team_tail [q₁, …, qₙ] t` is the probability that at least `t` of `n` independent events with success probabilities `q₁, …, qₙ` occur (first-step recursion; `team_tail_eq_sum` below identifies it with the explicit sum over outcome vectors). -/
noncomputable def team_tail : List ℝ → ℕ → ℝ := fun
  | [], t => if t = 0 then 1 else 0
  | p :: ps, t => p * team_tail ps (t - 1) + (1 - p) * team_tail ps t
See it in the graphDiscuss this resultChallenge it