The Ballot Problem

Question

Candidate A receives 5 votes and candidate B receives 3 votes. The 8 votes are counted one at a time in a uniformly random order. In how many of the orderings is A strictly ahead of B after every single vote is counted?

Accepted Answer

Bertrand's ballot theorem. With A getting p votes and B getting q votes (p > q), the number of count orderings in which A is strictly ahead throughout is fracp-qp+qbinomp+qp. Here p = 5, q = 3. The total number of orderings is binom85 = 56, and frac5-35+3cdot 56 = frac28cdot 56 = mathbf14. So 14 of the 56 orderings keep A strictly in front, a probability of frac14. Why the formula holds (reflection). Every valid ordering must start with an A. Among orderings that start with A, the "bad" ones (where a tie occurs later) are in bijection, via reflecting the path up to the first tie, with orderings that start with B. Since starting-with-A and starting-with-B orderings each number binomp+q-1cdot, subtracting gives the clean fracp-qp+q fraction. This is the same reflection principle behind Catalan counts and lattice paths kept below a diagonal. The trap: confusing "strictly ahead the whole time" with "ahead at the end" (which is automatic since p > q) or with "never behind" (the weak version, which allows ties and gives a different count). State precisely which inequality you are enforcing before reaching for a formula. Random-walk first-passage and ruin problems in trading wear this exa

The Ballot Problem

Problem

Your answer

Hints

More Combinatorics to train on