Maths WorkshopMaths problems with full solutions
Exercise 1942Combinatorics › Counting principlesOlympiadAdded 4 Nov 2026

The ballot problem

#ballot problem#reflection principle#lattice paths#probability

Statement

In an election, candidate AA receives aa votes and candidate BB receives bb votes, with a>ba>b. The votes are counted in a uniformly random order. Prove that the probability that AA is strictly ahead of BB throughout the count is a−ba+b\dfrac{a-b}{a+b}.

Hint

Represent the count as a sequence of +1+1 (vote for AA) and −1-1 (vote for BB). Bad sequences that start with +1+1 can be put in bijection with sequences starting with −1-1 by reflecting the part before the first tie.

Show solutionHide solution

Solution

Setup. There are (a+ba)\binom{a+b}a equally likely sequences of aa pluses and bb minuses. AA is strictly ahead throughout iff every partial sum is positive. Then the first vote must be +1+1.

Sequences starting with +1+1. There are (a+b−1a−1)\binom{a+b-1}{a-1} of them. Among them, call a sequence bad if some partial sum equals 00.

Reflection. Given a bad sequence, let tt be the first time its partial sum is 00, and flip the signs of the first tt entries. The result starts with −1-1, and has the same total a−ba-b. Conversely, every sequence starting with −1-1 and with total a−b>0a-b>0 has a first time tt where its partial sum is 00; flipping the first tt entries gives a bad sequence starting with +1+1. These maps are inverse to each other. Hence the number of bad sequences equals the number of sequences starting with −1-1 with aa pluses and bb minuses:
(a+b−1a).\binom{a+b-1}{a}.

Counting. The number of good sequences is
(a+b−1a−1)−(a+b−1a)=(a+ba)⋅a−ba+b.\binom{a+b-1}{a-1}-\binom{a+b-1}{a}=\binom{a+b}a\cdot\frac{a-b}{a+b}.

Probability. Dividing by (a+ba)\binom{a+b}a gives a−ba+b\dfrac{a-b}{a+b}.

Check. For a=5a=5, b=3b=3 a direct count over all 5656 sequences gives probability 14\frac14.

Lesson. The reflection principle turns "paths that touch a line" into "paths ending elsewhere".