## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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 (mn)/(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, ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required