Bertrand's ballot theorem

From Wikipedia, the free encyclopedia

You have new messages (last change).

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 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 {n \choose {n-m \over 2}}{m \over n}. When m=1 and n is odd, this gives the Catalan numbers.

Retrieved from "http://en.wikipedia.org../../../b/e/r/Bertrand%27s_ballot_theorem.html"
In other languages