# The Ballot Theorem

Today’s post is going to be about politics. Consider an election where there are two candidates, call them A and B, who receive $a,b$ votes respectively, and let us assume that $a. Assume that all possible “trajectories” $(0,0) \rightarrow (a,b)$ are equally likely. What is the probability that candidate B is ahead of A throughout the vote counting procedure? This problem is known as the ballot problem. The following theorem answers this question.

Ballot Theorem: The probability equals $\frac{b-a}{a+b}$.

Since once you get the idea, the proof becomes easy, I give you the idea

Proof Sketch:  We count. How many trajectories are there in total? Well, we have to choose a sequence $x_1,\ldots,x_{a+b}$ where each $x_i$ is either a vote for A or B. Clearly, since there are $a$ votes for A, there are ${a+b \choose a}$ trajectories. Now, how many trajectories have the property that B is ahead of A? Well, notice that the first step has to be a vote for B. There are ${a+b-1 \choose a}$ paths. We have to subtract from this number the number of paths that violate the desired property. But the paths that violate the property need to go through the point $(k,k)$ for some k, i.e., at some state the counted votes for A and B have to be equal. The key now is to observe that there is a bijection between each bad path and paths that start with a vote for A. A figure follows since a picture is worth at least 1000 words.

”]There are ${a+b-1 \choose a-1}$ such paths so now the probability is $p = \frac{{a+b-1 \choose a}-{a+b-1 \choose a-1}}{{a+b \choose a}}=\frac{b-a}{a+b}$.  QED

A source that contains links and material for this neat problem and this elegant solution is [1].

[1] http://webspace.ship.edu/msrenault/ballotproblem/