team_half_symm
lemmaverified
Symmetry of the fair binomial: S_k(t) + S_k(k+1-t) = 1.
Statement
lemma team_half_symm (k : ℕ) : ∀ t, t ≤ k + 1 →
team_tail (List.replicate k (1 / 2 : ℝ)) t
+ team_tail (List.replicate k (1 / 2 : ℝ)) (k + 1 - t) = 1- 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 3
- 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_tail_zeroThe probability of at least 0 successes is 1.
- team_tail_gtThe probability of more successes than there are events is 0.
- Used by 1
- team_half_oddAn odd number 2m+3 of fair coins: at least m+2 heads with probability 1/2.
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.
/-- Symmetry of the fair binomial: `S_k(t) + S_k(k+1-t) = 1`. -/lemma team_half_symm (k : ℕ) : ∀ t, t ≤ k + 1 → team_tail (List.replicate k (1 / 2 : ℝ)) t + team_tail (List.replicate k (1 / 2 : ℝ)) (k + 1 - t) = 1 := by induction k with | zero => intro t ht interval_cases t <;> simp [team_tail] | succ k ih => intro t ht rcases Nat.eq_zero_or_pos t with h0 | hpos · subst h0 rw [team_tail_zero, team_tail_gt _ _ (by simp)] ring · rcases Nat.lt_or_ge t (k + 2) with hlt | hge · -- 1 ≤ t ≤ k + 1 rw [List.replicate_succ] simp only [team_tail] have e1 := ih (t - 1) (by omega) have e2 := ih t (by omega) have h3 : k + 1 + 1 - t - 1 = k + 1 - t := by omega have h4 : k + 1 - (t - 1) = k + 1 + 1 - t := by omega rw [h3] rw [h4] at e1 linarith · have : t = k + 2 := by omega subst this rw [team_tail_gt _ _ (by simp), show k + 1 + 1 - (k + 2) = 0 by omega, team_tail_zero] ring