And lo On Wed, 17 Dec 2008 17:08:21 -0000, Phil Cook v2  
<phi### [at] nospamrocainfreeservecouk> did spake thusly:

> And lo On Wed, 17 Dec 2008 13:49:38 -0000, scott <sco### [at] scottcom> did  
> spake thusly:
>
>> If you have a box with N balls numbered 1 to N, and you repeatedly pull  
>> one out at random (replacing it each time), on average how many times  
>> would you expect to pull out a ball until you have seen all the balls 1  
>> to N?
>
> Do a search for Coupon Collector's Problem. For equal random drawings  
> it's roughly nHn that is n * Sum k=1-n of 1/k multiplied by n


Brain death! - n * Sum k=1-n of 1/k


-- 
Phil Cook

--
I once tried to be apathetic, but I just couldn't be bothered
http://flipc.blogspot.com

Post a reply to this message

scott wrote:
> If you have a box with N balls numbered 1 to N, and you repeatedly pull 

I have often wondered this, occasionally looked for the answer, and never 
really needed to know enough to work it out from first principles.

-- 
   Darren New, San Diego CA, USA (PST)
   The NFL should go international. I'd pay to
   see the Detroit Lions vs the Roman Catholics.

Post a reply to this message

On Wed, 17 Dec 2008 09:24:17 -0800, Darren New <dne### [at] sanrrcom> wrote:

>scott wrote:
>> If you have a box with N balls numbered 1 to N, and you repeatedly pull 
>
>I have often wondered this, occasionally looked for the answer, and never 
>really needed to know enough to work it out from first principles.

Strange, I've never wondered about it o_O
-- 

Regards
     Stephen

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> If we select one ball, the probability of it being ball #1 is 1/N.

  You are thinking it in the wrong way.

  The very first time you select one ball, the probability it's a ball you
have never seen before is 1.

  The second time you select a ball, the probability it's a ball you have
never seen before is (N-1)/N.

  With the third ball, the probability is (N-2)/N. And so on.

-- 
                                                          - Warp

Post a reply to this message

"scott" <sco### [at] scottcom> wrote:
> If you have a box with N balls numbered 1 to N, and you repeatedly pull one
> out at random (replacing it each time), on average how many times would you
> expect to pull out a ball until you have seen all the balls 1 to N?

For sufficiently large N, I'd expect to keep pulling out balls until I die. I
guess something in the order of N=1000 should be sufficient for this.

Post a reply to this message

Warp wrote:

>   You are thinking it in the wrong way.
> 
>   The very first time you select one ball, the probability it's a ball you
> have never seen before is 1.
> 
>   The second time you select a ball, the probability it's a ball you have
> never seen before is (N-1)/N.
> 
>   With the third ball, the probability is (N-2)/N. And so on.

As with most mathematical problems, it's trivially easy once you already 
know what the answer is... :-}

(And let's not forget, I have the lowest IQ in this newsgroup...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> >   The very first time you select one ball, the probability it's a ball you
> > have never seen before is 1.
> > 
> >   The second time you select a ball, the probability it's a ball you have
> > never seen before is (N-1)/N.
> > 
> >   With the third ball, the probability is (N-2)/N. And so on.

> As with most mathematical problems, it's trivially easy once you already 
> know what the answer is... :-}

  OTOH that only tells us the probability of getting distinct balls when
taking N balls out. It doesn't tell us how many balls must be taken in
average in order to get N distinct balls.

  Btw, if you didn't bother continuing that chaing of deductions, the
probability of getting all distinct balls when taking out N balls is
N!/(N^N).

-- 
                                                          - Warp

Post a reply to this message

>>> In other words, we have K/N - E, and I can't figure out how to compute 
>>> E.
>>
>> You can think of it the other way round, ie the probability of ball #1 
>> appearing after K tries is 1 minus the probability of ball #1 not 
>> occurring after K tries.
>
> Ah. So instead of a chain of non-exclusive OR events, you construct a 
> chain of independent AND events? Ingenius...

Yes, it's a useful trick to remember :-)

Post a reply to this message

>>I have often wondered this, occasionally looked for the answer, and never
>>really needed to know enough to work it out from first principles.
>
> Strange, I've never wondered about it o_O

Hehe, the exact problem I was applying it to was that I needed to save all 
the possible images generated by some website, I knew there was a certain 
number of possibilities and that it was random that each one appeared, so I 
just wondered how many times I would need to try before I got all of them.

I didn't need to know exactly, eg if N=100, am I expecting 150 tries, 200 
tries, 500 tries?  But knowing the exact formula would be cool as it seemed 
an interesting problem without an obvious result.

Another situation I can think of is if you need to check every item in a 
physical population, but you can only select ones at random (eg tagging fish 
in a lake or something).

Post a reply to this message

Am Wed, 17 Dec 2008 14:49:38 +0100 schrieb scott:

> If you have a box with N balls numbered 1 to N, and you repeatedly pull
> one out at random (replacing it each time), on average how many times
> would you expect to pull out a ball until you have seen all the balls 1
> to N?

Without looking at the other solutions (and excluding the trivial case), 
I would guess, that such average number does not exist. There is the real 
possibility of always pulling the same ball. In fact there is an infinite 
number of such combinations, where you can pull balls without ever 
getting all the balls. If the pulling of balls is truely random and 
independently, such combinations are not less likely (seems unintuitive, 
but there is no way of predicting which ball you will pull based on which 
balls you already pulled). In this case the infinite sum is diverging and 
you can't calculate an average.

Post a reply to this message