Bertrand's Ballot Theorem
In combinatorics, Bertrand's ballot problem is the question: "In an election where candidate A receives p votes and candidate B receives q votes with p > q, what is the probability that A will be strictly ahead of B throughout the count?" The answer is
The problem is named after Joseph Louis François Bertrand who introduced it in 1887; it is also credited to W. A. Whitworth who published an equivalent proof in 1878.
In Bertrand's original paper, he sketches a proof based on a general formula for the number of favourable sequences using a recursion relation. He remarks that it seems probable that such a simple result could be proved by a more direct method. Such a proof was given by Désiré André, based on the observation that the unfavourable sequences can be divided into two equally probable cases, one of which (the case where B receives the first vote) is easily computed; he proves the equality by an explicit bijection. A variation of his method is popularly known as André's reflection method, although André did not use any reflections.
Read more about Bertrand's Ballot Theorem: Example, Equivalent Problems, Proof By Reflection, Proof By Induction, Bertrand's and André's Proofs, Variant: Ties Allowed
Famous quotes containing the words ballot and/or theorem:
“I do not think the mere extension of the ballot a panacea for all the ills of our national life. What we need to-day is not simply more voters, but better voters.”
—Frances Ellen Watkins Harper (1825–1911)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)