Friday, November 25, 2011

Short commentary on Ballot Box problem

One of the problem in elementary course in probability is the ballot box problem. The statement of the problem goes as something "There are two candidates A and B competing in an election,  where after counting it is found that A has won the election. Now if we recount it what is the probability that we will find at least a  tie". The easiest way to think about this will be to conjure some numbers. Let there were 5 votes and out of 5 A had 3 and B had 2. We know from multinomial theorem that 5 things (when 3 are of same type and 2 are of other) can be arranged in 5!/(3! 2!) =10.
Lets list all those 10 possibilities
  1. AAABB (Bs together)
  2. AABAB (Moving 1 B and keeping other fixed)
  3. ABAAB (Moving 1 B and keeping other fixed)
  4. BAAAB (Moving 1 B and keeping other fixed) (Bs on both extreme)
  5. BAABA  (Moving the other B and keeping the other fixed)
  6. BABAA  (Moving the other B and keeping the other fixed)
  7. AABBA  (Bs together)
  8. ABBAA  (Bs together)
  9. BBAAA  (Bs together)
  10. ABBAA (As on both extreme)
 You should notice that out of these 10 except the first two we always have a tie sometimes during the counting. Question: When do you think when will any tie will happen ? Answer: It will always happen when you have counted some even number of ballots. Notice one more thing when the tie has happened if we replace As by Bs and  Bs by As we get another different way of tying. Also if number of Bs is smaller then we will always have some tie during the course of counting. Let a denote the number of As and b denote the number of Bs then the probability of  tie when we count b first  is b/(a+b) but for every sequence starting with B we saw there is a corresponding sequence starting with A which also gives a tie. Hence the total number of favorable cases is 2b and the corrected probability is 2b/(a+b)

0 Comments:

Post a Comment

<< Home

Site Meter