Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!ncar!boulder!frontier!tigger!rolandh
From: rolandh@tigger.Colorado.EDU (Roland Hubscher)
Newsgroups: comp.theory
Subject: Re: Help!
Message-ID: <1990Nov24.022222.24134@csn.org>
Date: 24 Nov 90 02:22:22 GMT
References: <11801@hubcap.clemson.edu>
Sender: news@csn.org
Organization: University of Colorado, Boulder
Lines: 50
Nntp-Posting-Host: tigger.colorado.edu

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?
> 
>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.

Let f(i) = 1 - 1/i where i = 1, ..., k is the ith ball your drawing.
Discard the new ball with probability f(i). The first time you don't
discard the new ball since f(1) = 0, the second ball is destryed with
probability f(2) = 1/2, etc.

It's easy to show that yoy really get what you want.

Let p(i) = not f(i) = 1/i the probability that the ith ball is kept
and the old ball is discarded. P(i) is the probability that you end up
with the ball drawn in round i.

P(i) = p(i) * (1-p(i+1)) * (1-p(i+1)) * ... * (1-p(k))
     = 1/i * (1-1/(i+1)) * (1-1/(i+2)) * ... * (1-1/k)
     = 1/i * ((i+1)-1)/(i+1) * ((i+2)-1)/(i+2) * ... * (k-1)/k
     = [1 * i * (i+1) * ... * (k-2) * (k-1)] /
           [i * (i+1) * (i+2) * ... * (k-1) * k]
     = 1/k

I used this function to pick a random move without having to store all the
moves generated by the move generator.

roland