Ballot problem

Candidate A receives a votes and candidate B receives b votes, with a > b so A wins. The ballots are counted one at a time in a uniformly random order. What is the probability that A is strictly ahead of B throughout the entire counting process?

The answer is beautifully simple:

P (A strictly ahead throughout) = \frac{a - b}{a + b}

P(always ahead) theory

40.0%

(a−b)/(a+b) = (7−3)/10

Simulated (2000 runs)

38.3%

a (A's votes) 7 b (B's votes, must be < a) 3 simulations 2000

Six example ballot sequences: blue = A strictly ahead the whole count, rose = B ties or leads at some point. The remarkably clean formula (a−b)/(a+b) holds exactly, proved by the reflection principle.

What to notice

Blue trajectories: A was strictly ahead at every step. Rose trajectories: B tied or led at some point.
Change a and b and the theoretical probability matches the simulation immediately.
With a=7, b=3: P = (7−3)/(7+3) = 40%. With a=9, b=1: P = 80%.

The reflection principle

The proof uses the reflection principle, a beautiful geometric argument. Consider all ballot sequences as lattice paths from (0,0) to (a+b, a−b). We want paths that stay strictly above the x-axis after step 0.

A bad path (one that touches or crosses zero) can be reflected at its first zero-crossing to produce a bijection with paths from (0,0) to (a+b, b−a) — paths ending at the wrong height. Counting these:

Total paths: C(a+b, a)
Bad paths: C(a+b, a+1) (paths to the reflected endpoint)
Good paths: C(a+b, a) − C(a+b, a+1) = C(a+b, a) · (a−b)/(a+b)

So P(good) = (a−b)/(a+b).

History and connections

The ballot problem was first solved by Désiré André in 1887. The reflection principle he used reappears throughout probability:

Pricing barrier options in finance
Calculating ruin probabilities for random walks
Proving the arc-sine law for Brownian motion

The Gambler’s ruin problem is closely related — both deal with first-passage times in random walks.