Today’s post is going to be about politics. Consider an election where there are two candidates, call them A and B, who receive votes respectively, and let us assume that . Assume that all possible “trajectories” 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 .

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 where each is either a vote for A or B. Clearly, since there are votes for A, there are 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 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 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 such paths so now the probability is .  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/