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, ...
