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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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