Bertrand's ballot theorem
In combinatorics, Bertrand's ballot theorem is the solution to the question: "In an election where one candidate receives p votes and the other q votes with p≥q, what is the probability that the first candidate will be strictly ahead of the second candidate throughout the count?" The answer is
- (p−q)/(p+q).
It is related to random walks and can be proved several different ways. One is by mathematical induction:
- Clearly it is true if p>0 and q=0 when the probability is 1, given that the first candidate receives all the votes; it is also true when p=q>0 since the probability is 0, given that the first candidate will not be strictly ahead after all the votes have been counted.
- Assume it is true both when p=a−1 and q=b, and when p=a and q=b−1, with a>b>0. Then considering the case with p=a and q=b, the last vote counted is either for the first candidate with probability a/(a+b), or for the second with probability b/(a+b). So the probability of the first being ahead throughout the count to the penultimate vote counted (and also after the final vote) is:
- And so it is true for all p and q with p>q>0.
It can then be used to calculated the number of one-dimensional walks of n steps from the origin to the point m which do not return to the origin. Assuming n and m have the same parity and n≥m>0, it is
When m=1 and n is odd, this gives the Catalan numbers.