The Ballot Problem and the Reflection Principle

An election has two candidates. Candidate A finishes with $a$ votes, candidate B with $b$ votes, $a > b$, and votes are counted one at a time in a uniformly random order. What's the probability that A was strictly ahead of B for the entire count — never tied, never behind, from the very first vote onward? With $a=3, b=1$ the answer turns out to be a clean fraction. Try counting all the orderings by hand for that small case before reading on.

The trap: enumerating every valid vote-counting order directly

There are $\binom{a+b}{a}$ equally likely orderings of the votes. You want to count how many of them keep A strictly ahead the whole way through — and directly characterising "stays ahead forever" among all sequences is fiddly, because "ahead" depends on a running cumulative comparison, not on any local property of the sequence.

The way around this is a beautiful geometric trick: turn each vote-counting order into a path on a grid, and then reflect the bad paths onto a different endpoint, so counting bad paths becomes counting paths to a fixed target — something you already know how to do.

Setting up the correspondence

Encode the count as a path from $(0,0)$: each A vote is a step up-right (+1), each B vote a step down-right (−1). The path ends at height $a-b$ after $a+b$ steps. "A stays strictly ahead the whole time" means the path stays strictly positive after the first step, i.e. never returns to height 0.

A path from $(0,0)$ to $(a+b,\ a-b)$ that does touch zero at some point can be reflected: take the segment from the start up to its first return to 0, and flip that segment's steps (up becomes down, down becomes up). This produces a new path that starts at $(0,0)$ with a down-step and ends at $(a+b,\ -(a-b))$ — because the reflected segment reverses the height change over that portion, and this reflection is a perfect bijection between "paths touching 0" and "all paths from $(0,0)$ ending at $-(a-b)$ instead of $a-b$."

$$P(\text{A always strictly ahead}) = \frac{a-b}{a+b}.$$

In words: the fraction of the total lead — the gap between the winning and losing vote counts, divided by the total number of votes — is exactly the probability that the winner never trailed or tied at any point in the count. This compact result is the ballot problem, first solved by Bertrand in 1887.

Worked example: a = 3, b = 1, checked by brute force

Formula: $\frac{a-b}{a+b} = \frac{3-1}{3+1} = \frac{2}{4} = \frac12$.

Check directly. There are $\binom{4}{3}=4$ orderings of 3 A-votes and 1 B-vote. Write them as sequences:

• AAAB: running tally 1,2,3,2 — always strictly positive (A leads 1–0, 2–0, 3–0, 3–1). Valid.
• AABA: running tally 1,2,1,2 — always strictly positive. Valid.
• ABAA: running tally 1,0,1,2 — touches zero after the second vote (a tie, 1–1). Invalid.
• BAAA: running tally −1,0,1,2 — goes negative immediately (B briefly "ahead"), and touches zero. Invalid.

Two of the four orderings keep A strictly ahead throughout: probability $2/4 = 1/2$, exactly matching the formula.

The transferable technique

The reflection principle is a general tool for counting lattice paths that avoid a barrier: whenever "bad" paths can be put in one-to-one correspondence with "all paths to some other, easy-to-count endpoint" by flipping the steps before the first violation, the count of bad paths becomes trivial, and subtracting it from the total gives you the count you actually wanted. The same trick computes first-return probabilities for random walks, the probability a gambler's fortune never dips below zero, and the arcsine law for lead times in a coin-flip race — anywhere a path needs to dodge a boundary, look for a reflection.