Ballot problem

This file proves Theorem 30 from the 100 Theorems List.

The ballot problem asks, if in an election, candidate A receives p votes whereas candidate B receives q votes where p > q, what is the probability that candidate A is strictly ahead throughout the count. The probability of this is (p - q) / (p + q).

Main definitions

• countedSequence: given natural numbers p and q, countedSequence p q is the set of all lists containing p of 1s and q of -1s representing the votes of candidate A and B respectively.
• staysPositive: is the set of lists of integers which suffix has positive sum. In particular, the intersection of this set with countedSequence is the set of lists where candidate A is strictly ahead.

Main result

• ballot_problem: the ballot problem.

def Ballot.staysPositive : Set (List ℤ)

The set of nonempty lists of integers which suffix has positive sum.

Equations

• Ballot.staysPositive = {l : List ℤ | ∀ (l₂ : List ℤ), l₂ ≠ [] → l₂.IsSuffix l → 0 < l₂.sum}

@[simp]

theorem Ballot.staysPositive_nil : [] ∈ Ballot.staysPositive

theorem Ballot.staysPositive_suffix {l₁ : List ℤ} {l₂ : List ℤ} (hl₂ : l₂ ∈ Ballot.staysPositive) (h : l₁.IsSuffix l₂) : l₁ ∈ Ballot.staysPositive

theorem Ballot.staysPositive_cons {x : ℤ} {l : List ℤ} : x :: l ∈ Ballot.staysPositive ↔ l ∈ Ballot.staysPositive ∧ 0 < x + l.sum

theorem Ballot.sum_nonneg_of_staysPositive {l : List ℤ} : l ∈ Ballot.staysPositive → 0 ≤ l.sum

theorem Ballot.staysPositive_cons_pos (x : ℤ) (hx : 0 < x) (l : List ℤ) : x :: l ∈ Ballot.staysPositive ↔ l ∈ Ballot.staysPositive

def Ballot.countedSequence (p : ℕ) (q : ℕ) : Set (List ℤ)

countedSequence p q is the set of lists of integers for which every element is +1 or -1, there are p lots of +1 and q lots of -1.

This represents vote sequences where candidate +1 receives p votes and candidate -1 receives q votes.

Equations

• Ballot.countedSequence p q = {l : List ℤ | List.count 1 l = p ∧ List.count (-1) l = q ∧ ∀ x ∈ l, x = 1 ∨ x = -1}

theorem Ballot.mem_countedSequence_iff_perm {p : ℕ} {q : ℕ} {l : List ℤ} : l ∈ Ballot.countedSequence p q ↔ l.Perm (List.replicate p 1 ++ List.replicate q (-1))

An alternative definition of countedSequence that uses List.Perm.

@[simp]

theorem Ballot.counted_right_zero (p : ℕ) : Ballot.countedSequence p 0 = {List.replicate p 1}

@[simp]

theorem Ballot.counted_left_zero (q : ℕ) : Ballot.countedSequence 0 q = {List.replicate q (-1)}

theorem Ballot.mem_of_mem_countedSequence {p : ℕ} {q : ℕ} {l : List ℤ} (hl : l ∈ Ballot.countedSequence p q) {x : ℤ} (hx : x ∈ l) : x = 1 ∨ x = -1

theorem Ballot.length_of_mem_countedSequence {p : ℕ} {q : ℕ} {l : List ℤ} (hl : l ∈ Ballot.countedSequence p q) : l.length = p + q

theorem Ballot.counted_eq_nil_iff {p : ℕ} {q : ℕ} {l : List ℤ} (hl : l ∈ Ballot.countedSequence p q) : l = [] ↔ p = 0 ∧ q = 0

theorem Ballot.counted_ne_nil_left {p : ℕ} {q : ℕ} (hp : p ≠ 0) {l : List ℤ} (hl : l ∈ Ballot.countedSequence p q) : l ≠ []

theorem Ballot.counted_ne_nil_right {p : ℕ} {q : ℕ} (hq : q ≠ 0) {l : List ℤ} (hl : l ∈ Ballot.countedSequence p q) : l ≠ []

theorem Ballot.counted_succ_succ (p : ℕ) (q : ℕ) : Ballot.countedSequence (p + 1) (q + 1) = List.cons 1 '' Ballot.countedSequence p (q + 1) ∪ List.cons (-1) '' Ballot.countedSequence (p + 1) q

theorem Ballot.countedSequence_finite (p : ℕ) (q : ℕ) : (Ballot.countedSequence p q).Finite

theorem Ballot.countedSequence_nonempty (p : ℕ) (q : ℕ) : (Ballot.countedSequence p q).Nonempty

theorem Ballot.sum_of_mem_countedSequence {p : ℕ} {q : ℕ} {l : List ℤ} (hl : l ∈ Ballot.countedSequence p q) : l.sum = ↑p - ↑q

theorem Ballot.disjoint_bits (p : ℕ) (q : ℕ) : Disjoint (List.cons 1 '' Ballot.countedSequence p (q + 1)) (List.cons (-1) '' Ballot.countedSequence (p + 1) q)

theorem Ballot.count_countedSequence (p : ℕ) (q : ℕ) : ↑MeasureTheory.Measure.count (Ballot.countedSequence p q) = ↑((p + q).choose p)

theorem Ballot.first_vote_pos (p : ℕ) (q : ℕ) : 0 < p + q → ↑(ProbabilityTheory.condCount (Ballot.countedSequence p q)) {l : List ℤ | l.headI = 1} = ↑p / (↑p + ↑q)

theorem Ballot.headI_mem_of_nonempty {α : Type u_1} [Inhabited α] {l : List α} : l ≠ [] → l.headI ∈ l

theorem Ballot.first_vote_neg (p : ℕ) (q : ℕ) (h : 0 < p + q) : ↑(ProbabilityTheory.condCount (Ballot.countedSequence p q)) {l : List ℤ | l.headI = 1}ᶜ = ↑q / (↑p + ↑q)

theorem Ballot.ballot_same (p : ℕ) : ↑(ProbabilityTheory.condCount (Ballot.countedSequence (p + 1) (p + 1))) Ballot.staysPositive = 0

theorem Ballot.ballot_edge (p : ℕ) : ↑(ProbabilityTheory.condCount (Ballot.countedSequence (p + 1) 0)) Ballot.staysPositive = 1

theorem Ballot.countedSequence_int_pos_counted_succ_succ (p : ℕ) (q : ℕ) : Ballot.countedSequence (p + 1) (q + 1) ∩ {l : List ℤ | l.headI = 1} = List.cons 1 '' Ballot.countedSequence p (q + 1)

theorem Ballot.ballot_pos (p : ℕ) (q : ℕ) : ↑(ProbabilityTheory.condCount (Ballot.countedSequence (p + 1) (q + 1) ∩ {l : List ℤ | l.headI = 1})) Ballot.staysPositive = ↑(ProbabilityTheory.condCount (Ballot.countedSequence p (q + 1))) Ballot.staysPositive

theorem Ballot.countedSequence_int_neg_counted_succ_succ (p : ℕ) (q : ℕ) : Ballot.countedSequence (p + 1) (q + 1) ∩ {l : List ℤ | l.headI = 1}ᶜ = List.cons (-1) '' Ballot.countedSequence (p + 1) q

theorem Ballot.ballot_neg (p : ℕ) (q : ℕ) (qp : q < p) : ↑(ProbabilityTheory.condCount (Ballot.countedSequence (p + 1) (q + 1) ∩ {l : List ℤ | l.headI = 1}ᶜ)) Ballot.staysPositive = ↑(ProbabilityTheory.condCount (Ballot.countedSequence (p + 1) q)) Ballot.staysPositive

theorem Ballot.ballot_problem' (q : ℕ) (p : ℕ) : q < p → (↑(ProbabilityTheory.condCount (Ballot.countedSequence p q)) Ballot.staysPositive).toReal = (↑p - ↑q) / (↑p + ↑q)

theorem Ballot.ballot_problem (q : ℕ) (p : ℕ) : q < p → ↑(ProbabilityTheory.condCount (Ballot.countedSequence p q)) Ballot.staysPositive = (↑p - ↑q) / (↑p + ↑q)

The ballot problem.