The ballot problem
Statement
In an election, candidate receives votes and candidate receives votes, with . The votes are counted in a uniformly random order. Prove that the probability that is strictly ahead of throughout the count is .
Hint
Represent the count as a sequence of (vote for ) and (vote for ). Bad sequences that start with can be put in bijection with sequences starting with by reflecting the part before the first tie.
Show solutionHide solution
Solution
Setup. There are equally likely sequences of pluses and minuses. is strictly ahead throughout iff every partial sum is positive. Then the first vote must be .
Sequences starting with . There are of them. Among them, call a sequence bad if some partial sum equals .
Reflection. Given a bad sequence, let be the first time its partial sum is , and flip the signs of the first entries. The result starts with , and has the same total . Conversely, every sequence starting with and with total has a first time where its partial sum is ; flipping the first entries gives a bad sequence starting with . These maps are inverse to each other. Hence the number of bad sequences equals the number of sequences starting with with pluses and minuses:
Counting. The number of good sequences is
Probability. Dividing by gives .
Check. For , a direct count over all sequences gives probability .
Lesson. The reflection principle turns "paths that touch a line" into "paths ending elsewhere".