tan@iwu1d.UUCP (William Tanenbaum) (04/26/84)
Ballot Counting Problem: In a two candidate election, the winner receives p votes and the loser receives q votes. (p>q obviously) The ballots are randomly shuffled and counted one at a time. What is the probability that the winner will always be ahead after the first vote is counted? Give a simple proof of the answer. Answer: (p-q)/(p+q) is the probability. Simple derivation/proof: 1) All possible orderings of the p+q ballots, all considered distinguishable, are equally probable, by the random shuffling assumption. 2) The probability that the first vote counted will go the loser is q/(p+q). Clearly, in all such cases the winner is not ahead at all times. 3) THE KEY STEP! What is the probability that the winner gets the first vote but also is not ahead at all times? It is also q/(p+q). PROOF of 3): a)Let A be the set of all orderings where the loser gets the first vote. Let B be the set of all orderings where the winner gets the first vote, yet is not always ahead. By definition, the sets are disjoint. b)Define the following transformation on members of set A or set B: Reverse the order of the counting of the ballots up to the first time a tie occurs. (A tie always must occur if the winner is not always ahead.) Later ballots are unaffected. This transformation transforms any member of set A into a unique member of set B, and vice-versa. Thus sets A and B must have the same number of members! Since all orderings are equally probable, 3) then follows. 4)The answer then is 1-(2q/(p+q)), or (p-q)/(p+q).