Path: utzoo!utgpu!watserv1!watmath!att!att!tut.cis.ohio-state.edu!pt.cs.cmu.edu!PROOF.ERGO.CS.CMU.EDU!cokasaki
From: cokasaki@PROOF.ERGO.CS.CMU.EDU (Chris Okasaki)
Newsgroups: comp.theory
Subject: Re: Help!
Message-ID: <11185@pt.cs.cmu.edu>
Date: 24 Nov 90 20:43:52 GMT
References: <11801@hubcap.clemson.edu>
Organization: Carnegie-Mellon University, CS/RI
Lines: 50

In article <11801@hubcap.clemson.edu> grimlok@hubcap.clemson.edu (Mike Percy) writes:
>I am looking for a solution for this problem, 
> 
>I have a black box with an unknown number (k) of balls with colors 1..k
>
>While the box is not empty, I will pull out a ball.  I will either
>discard the ball I had and discard the ball I just withdrew, or vice
>versa.
> 
>At the end, I wish there to be an equal probability that I am holding
>ball colored i.  What function can I use to decide which ball to discard at each
>step?
> 
>I want f() to be such that I have a 1/3 probability of the ball I am
>holding to be red, blue, or green.  f() cannot depend on how many balls
>are in the box (unknown), but may use the number of balls already
>withdrawn.

How about this?  Let f(i) be the probability of retaining at turn i
the ball you just drew.  After any turn i, we want the probability that
we're currently holding any ball that we've already seen to be 1/i.  (This
will assure that after the last ball,  the probability that we're
holding any of the balls is 1/k, which is the desired result.)

Now, say we've just picked up the i-th ball.  After this turn we want the
probability that we're holding any of balls we've encountered to be 1/i.
In particular, we want the probability that we're holding THIS ball to be
1/i.  Therefore, we must retain it with probability 1/i, i.e. f(i) = 1/i.

This gives us the correct result for THIS ball, but what about the other
balls?  Well by our (implicit) inductive assumption, we came into this turn
with a probability of holding any ball that we'd already seen of 1/(i-1).
Since we keep the i-th ball with probability 1/i, we keep the ball that
we ALREADY had with probability (i-1)/i.  So the probability that we're holding
any of the earlier balls is now 1/(i-1) * (i-1)/i = 1/i.

Of course we need a base case for our induction.  As usual with induction, the
base case is almost embarassingly simple.  f(1) = 1/1 = 1 so after the first
turn we're holding the first ball with probability 1.  That's it!

--
-------------------------------------------------------------------------------
| Chris Okasaki       |                          Life is NOT a zero-sum game! |
| cokasaki@cs.cmu.edu |                                                       |
-------------------------------------------------------------------------------
-- 
-------------------------------------------------------------------------------
| Chris Okasaki       |                          Life is NOT a zero-sum game! |
| cokasaki@cs.cmu.edu |                                                       |
-------------------------------------------------------------------------------