Classic Problems of Probability

Problem 17

Bertrand's Ballot Problem (1887)

Problem. In an election, candidate M receives a total of m votes while candidate N receives a total of n votes, where m > n. Prove that, throughout the counting, M is ahead of N with probability (m − n)/(m + n).

Solution. We use mathematical induction to prove that the probability of M being ahead throughout is

(17.1)

If m > 0 and n = 0, A will always be ahead since N receives no votes. The formula is thus true for all m > 0 and n = 0 because it gives . Similarly, if m = n > 0, M cannot always be ahead of N since they clearly are not at the end. The formula is thus true for all m = n > 0 because it gives .

Now suppose and are both true. Then M with m votes will always be ahead of N with n votes if and only if either (i) in the penultimate count, M with m votes is ahead of N with n − 1 votes, followed by a last vote for N or (ii) in the penultimate count, M with m − 1 votes is ahead of N with n votes, followed by a last vote for M. Therefore, ...