You have N bags. Bag 1 has a black ball, Bag 2 has a black ball and a white ball, Bag 3 has a black ball and two white balls, and so on. Bag N has a black ball and N-1 white balls. You pick a ball from each bag at random and record the numbers of the bags that you picked a black ball from. For example, if you had 100 bags, then your sequence might be 1, 2, 3, 10, 14, 37. Call the last number in your sequence X. Prove that X is a random number from 1 to N with a uniform distribution.

Since we want the largest number, only this one matters.  So for X to have a uniform distribution we need only show that for any X from 1 to N the probability that X is the largest number is 1/N.

For this we need bag X to yield a black ball, and also all the bags from X+1 to N to yield white.  Since the bags are independent we can just take the product of each of these probabilities:

1/X * X/(X+1) * (X+1)/(X+2) * ... * (N-2)/(N-1) * (N-1)/N

Which clearly reduces to 1/N

Posted by Jer on 2011-04-21 01:24:22