Friday, August 24, 2012

The "ballot" problem

There are two candidates contesting for a post, A and B. Elections have ended and A got total a votes and B got total b votes, with a > b. Every person voted must vote for either A or B. They shuffled the ballot box and started counting. A is declared winner only if he leads at every point of counting. What is the probability that A will win the elections?

Courtesy : Prof. S.B. Pillai


Sravan said...

Ok. My method is a little long. But bear with me.

Look at it as a random walk problem. Let (p+q, p-q) represent the path of length p+q, with p +1's and q -1's. So the final sum will be p-q. In this problem, for candidate A, +1 means he's got that vote and -1 means his opponent got that vote.

Let the first coordinate correspond to the length of path axis (L axis)and the second coordinate correspond to the sum axis (S axis).

So, in the problem we need to go from the point M(0,0) to N(a+b, a-b) with the condition that, the we never cross the S-axis.

Clearly, the number of paths from M to N with the given condition is the same as the number of paths from (1,1) to N.

Claim: Paths where we cross the S-axis atleast once when going from X(x1,y1) to Y(x2,y2) is the same as that from
X'(x1,-y1) to Y(x2,y2)

Proof: Let the path first intersect the s-axis at the point P. Since X and X' are symmetric with respect to the s-axis, the number of paths from X to P and X' to P are the same. From P, the path is similar. QED.

Now back to our problem, the number of paths from M to N without crossing s-axis
= All paths from (1,1) to N - Paths which cross s-axis from (1,1) to N
=All paths from (1,1) to N - Paths which cross s-axis from (1,-1) to N
=All paths from (1,1) to N - All paths from (1,-1) to N (Since every path from (1,-1) to (a+b,a-b) crosses the s-axis)

Here C is the choose function.

Probability of A winning = (C(a+b-1, a-1)-C(a+b-1,a)) / C(a+b,a)

pathankhan salman said...

Yes it is correct.