Bertrand's ballot theorem

From Wikipedia, the free encyclopedia

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

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.