O'Reilly logo

Classic Problems of Probability by Prakash Gorroochurn

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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) equation

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

Now suppose img and img 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.

Start Free Trial

No credit card required