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

:$frac\{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::$\{a\; over\; (a+b)\}\{(a-1)-b\; over\; (a+b-1)\}+\{b\; over\; (a+b)\}\{a-(b-1)\; over\; (a+b-1)\}=\{a-b\; over\; a+b\}.$
*And so it is true for all "p" and "q" with "p">"q">0.

It can then be used to calculate 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 $\{n\; choose\; \{n-m\; over\; 2\{m\; over\; n\}.$ When "m"=1 and "n" is odd, this gives the Catalan numbers.

External links

* [http://webspace.ship.edu/msrenault/ballotproblem/ The Ballot Problem, Marc Renault]