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
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
countedSequence p qis the set of all lists containing
-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
countedSequenceis the set of lists where candidate A is strictly ahead.
Main result #
ballot_problem: the ballot problem.