AFTD Auto-Formalizing Theoretical Domains

team_tail_eq_sum

theoremverified

team_tail equals the explicit sum over outcome vectors Σ_ω [t ≤ #wins(ω)] Π_i (q_i if ω_i else 1 - q_i).

Statement

open Finset in
theorem team_tail_eq_sum (n : ℕ) (q : Fin n → ℝ) (t : ℕ) :
    team_tail (List.ofFn q) t = ∑ ω : Fin n → Bool,
      (if t ≤ team_wins ω then (1 : ℝ) else 0) * ∏ i, (if ω i = true then q i else 1 - q i)
Source
step towards team_thm4_part2_false / team_thm4_part2_exists_false (The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2))
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • team_tailPoisson-binomial upper tail: team_tail [q₁, …, qₙ] t is the probability that at least t of n independent events with success probabilities…
  • team_winsNumber of successes in an outcome vector.
  • team_wins_consThe number of wins of an outcome vector with a prepended result b is [b] plus the number of wins of the rest.
  • team_sum_splitSplitting a sum over outcome vectors of length n+1 by the first outcome.

Lean source view module on GitHub

open Finset in/-- `team_tail` equals the explicit sum over outcome vectors `Σ_ω [t ≤ #wins(ω)] Π_i (q_i if ω_i else 1 - q_i)`. -/theorem team_tail_eq_sum (n : ℕ) (q : Fin n → ℝ) (t : ℕ) :    team_tail (List.ofFn q) t = ∑ ω : Fin n → Bool,      (if t ≤ team_wins ω then (1 : ℝ) else 0) * ∏ i, (if ω i = true then q i else 1 - q i) := by  induction n generalizing t with  | zero =>    simp [team_tail, team_wins]  | succ n ih =>    rw [List.ofFn_succ]    simp only [team_tail]    rw [ih, ih, team_sum_split, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib]    apply Finset.sum_congr rfl    intro ω _    simp only [team_wins_cons, Fin.prod_univ_succ, Fin.cons_zero, Fin.cons_succ, if_true,      Bool.false_eq_true, if_false, zero_add]    have : (t - 1 ≤ team_wins ω) ↔ (t ≤ 1 + team_wins ω) := by omega    by_cases h : t ≤ 1 + team_wins ω    · rw [if_pos (this.2 h), if_pos h]; ring    · rw [if_neg (fun h' => h (this.1 h')), if_neg h]; ring
See it in the graphDiscuss this resultChallenge it