Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!att!emory!hubcap!grimlok
From: grimlok@hubcap.clemson.edu (Mike Percy)
Newsgroups: comp.theory
Subject: Help!
Message-ID: <11801@hubcap.clemson.edu>
Date: 23 Nov 90 21:37:33 GMT
Organization: Clemson University, Clemson, SC
Lines: 26

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?
 
For example
I first pull out a red ball.
I then pull out a green ball.  Based on some predicate f, I discard a
ball.
I then pull out a blue ball.  Again, I must discard one.
The box is now empty.
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.
 
Can anyone give me a decent f?  One that is only approximate woul be
good.  I am currently using f() = random(0,1) < 0.50, but this is no
good.