Always ahead in the count
In an election, candidate A receives votes and candidate B receives . The ballots are counted one by one in a uniformly random order.
What is the probability that A is strictly ahead of B after every ballot counted?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Count the orderings where A is not always ahead. If the first ballot is for B, A is behind at once. If the first ballot is for A but the counts are level at some point, reflect the part of the count before the first tie.
The reflection matches the bad orderings that start with A one-to-one with the orderings that start with B.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Count the bad orderings with a reflection argument: those that start with an A vote and later reach a tie are in bijection with those that start with a B vote.
Step 1: setting. All orderings are equally likely. An ordering is bad if A is not strictly ahead at some point. Since A finishes ahead, a bad ordering always passes through a tie.
Step 2: bad orderings starting with B. Any ordering that starts with B is bad. There are of them (the other ballots contain for B).
Step 3: bad orderings starting with A. Such an ordering reaches a first tie. Swap every vote (A B) before that first tie. The result starts with B, has the same final counts, and reaches the same tie. This is a bijection with the orderings that start with B, so there are also of them.
Step 4.
The ballot theorem. In general, with votes, the probability is . Here .