Bertrand's ballot theorem

Statement

Let $p$ and $q$ be natural numbers with $p > q$. In an election, candidate $A$ gets $p$ votes and candidate $B$ gets $q$ votes. The votes are counted one at a time, in an order chosen uniformly at random among all orders. Then the probability that $A$ is strictly ahead of $B$ after each vote is counted is $$\frac{p - q}{p + q}.$$

Remarks

Equivalently, the number of such counting orders, as words with $p$ letters $A$ and $q$ letters $B$, is $\frac{p - q}{p + q} \binom{p + q}{p}$. Example: for $p = 3$ and $q = 1$, the probability is $\frac{1}{2}$. Of the $4$ orders, $AAAB$ and $AABA$ work. A short proof uses the reflection principle for lattice paths.

History

William Allen Whitworth published the result in 1878. Joseph Bertrand found it again in 1887, and the theorem has his name.

Explanations

L1 human

If the winner gets many more votes than the loser, the winner is likely to lead the whole time. The formula makes this precise: the chance of an unbroken lead is the margin divided by the total number of votes.