[net.math] Ballot counting problem

tan@iwu1d.UUCP (William Tanenbaum) (02/29/84)

Here is a well known problem in probability which is difficult to
solve by brute force but yields easily to the proper insight:
---Two candidates run for office.  The winner receives p votes,
the loser receives q votes. (q<p obviously).  Suppose all the
ballots are mixed randomly before counting, and running totals
are kept as the votes are counted.  What is the probability that
the winner will always be ahead (never behind or tied) as the
votes are counted, (the inital 0-0 tie obviously excepted)?
Please prove that your answer is correct.  An answer without a proof
is no solution.  I will post the solution in a week if no one else
does first.
					Bill Tanenbaum
					A. T. & T. Bell Labs
					Naperville Il.

kpv@ulysses.UUCP (Phong Vo) (04/27/84)

William Tanenbaum has given a solution to the problem:
	In a two candidate election, the winner gets p votes
	and the loser gets q votes (p > q). The ballots are
	randomly shuffled and counted one at a time.
	What is the probability that the winner will always
		BE AHEAD
	at any point during the counting?

Now the variation:
	What is the probability that the winner will always
		DO AT LEAST AS WELL AS THE LOSER
	at any point during the counting?

That is, at any time t during the counting, if w(t) is the number of votes
that the winner receives and l(t) is the number of votes that the loser
receives, then w(t) >= l(t).
In the original problem, it is required that w(t) > l(t).