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<b. 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/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: