Abrazolica

There are 2 candidates in an election. Call them \(A\) and \(B\). \(A\) gets \(a\) votes, and \(B\) gets \(b\) votes with \(a>b\). During the counting of the votes, \(A\) is always ahead of \(B\). What is the probability of this happening assuming that the ballots are counted in random order?

The total number of ways the \(a+b\) ballots can be counted is \(\binom{a+b}{a}\). To find how many ways there are where \(A\) is always ahead of \(B\) it helps to look at the counting process as a random walk on a line. The walk starts at the origin (point 0). Every vote for \(A\) is a step to the right, and every vote for \(B\) is a step to the left. As the votes are counted the walk moves randomly left and right and eventually ends \(a-b\) steps to the right of the origin. The total number of walks equals the total number of ways the ballots can be counted, \(\binom{a+b}{a}\).

The counts where \(A\) is always ahead of \(B\) are walks that start with a step to the right and never return to the origin. To find how many of these walks there are, we first have to find the number of walks that start with a step to the right and the number that start with a step to the left.

For a walk that begins with a right step, there are \(a+b-1\) steps remaining of which \(a-1\) are to the right, so the number of such walks is \(\binom{a+b-1}{a-1} = \binom{a+b-1}{b}\). Likewise the number of walks that begin with a step to the left is \(\binom{a+b-1}{b-1} = \binom{a+b-1}{a}\).

Now note that every walk that starts with a step to the left must eventually return to the origin. If you reverse the steps of such a walk up to the point where it returns to the origin, then it becomes a walk that starts with a step to the right and returns to the origin. There is a one to one correspondence between origin returning walks that start with a step to the right and those that start with a step to the left. So the number of walks that start with a step to the right and don't return to the origin is equal to the difference

\[\binom{a+b-1}{b} - \binom{a+b-1}{a} = \frac{a-b}{a+b}\binom{a+b}{a}\]

If you divide this difference by the total number of walks, you get the probability that \(A\) is always ahead of \(B\). The probability is

\[\frac{a-b}{a+b}\]

It is equal to the difference between the votes for \(A\) and \(B\) divided by the total number of votes. The probability is greater than \(1/2\) whenever \(A\) gets 3 times the votes of \(B\), \(a > 3b\). Most of the time the margin of victory is much smaller. If \(A\) wins by 100 votes out of a total of 100,000 cast, then the probability of him always being ahead during the count is 0.001.

This result is known as Bertrand's ballot theorem.