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 under the assumption that votes are counted in a randomly picked order?"
The answer is The result was first published by W. A. Whitworth in 1878, but is named after Joseph Louis François Bertrand who rediscovered it in 1887.
[1][2][3][4][5] 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é,[6] 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.
[7] Bertrand's ballot theorem is related to the cycle lemma.
They give similar formulas, but the cycle lemma considers circular shifts of a given ballot counting order rather than all permutations.
For the order AABBA the tally of the votes as the election progresses is: For this order, B is tied with A after the fourth vote, so A is not always strictly ahead of B.
Rather than computing the probability that a random vote counting order has the desired property, one can instead compute the number of favourable counting orders, then divide by the total number of ways in which the votes could have been counted.
; Bertrand's proof shows that the number of favourable orders in which to count the votes is
Another related problem is to calculate the number of random walks on the integers that consist of n steps of unit length, beginning at the origin and ending at the point m, that never become negative.
Thus the probability that a random walk is never negative and returns to origin at time
have the same parity] For A to be strictly ahead of B throughout the counting of the votes, there can be no ties.
Any sequence that begins with a vote for B must reach a tie at some point, because A eventually wins.
For any sequence that begins with A and reaches a tie, reflect the votes up to the point of the first tie (so any A becomes a B, and vice versa) to obtain a sequence that begins with B.
, so the probability that A always leads the vote is Another method of proof is by mathematical induction: A simple proof is based on the cycle lemma of Dvoretzky and Motzkin.
[8] Call a ballot sequence dominating if A is strictly ahead of B throughout the counting of the votes.
A's and B's in a circle and repeatedly remove adjacent pairs AB until only
Each of these A's was the start of a dominating cyclic permutation before anything was removed.
is the number of favourable sequences, but "it seems probable that such a simple result could be shown in a more direct way".
Indeed, a more direct proof was soon produced by Désiré André.
His approach is often mistakenly labelled "the reflection principle" by modern authors but in fact uses a permutation.
He shows that the "unfavourable" sequences (those that reach an intermediate tie) consist of an equal number of sequences that begin with A as those that begin with B.
Each unfavourable sequence that begins with A can be transformed to an arbitrary sequence of (q-1) B's and p A's by finding the first B that violates the rule (by causing the vote counts to tie) and deleting it, and interchanging the order of the remaining parts.
To reverse the process, take any sequence of (q-1) B's and p A's and search from the end to find where the number of A's first exceeds the number of B's, and then interchange the order of the parts and place a B in between.
From this, it follows that the number of favourable sequences of p A's and q B's is and thus the required probability is as expected.
The original problem is to find the probability that the first candidate is always strictly ahead in the vote count.
One may instead consider the problem of finding the probability that the second candidate is never ahead (that is, with ties are allowed).
Represent a voting sequence as a lattice path on the Cartesian plane as follows: Each such path corresponds to a unique sequence of votes and will end at (p, q).
A sequence is 'good' exactly when the corresponding path never goes above the diagonal line y = x; equivalently, a sequence is 'bad' exactly when the corresponding path touches the line y = x + 1.
