Re: Random Probability

Hi all,

I tried to look at 'Coupon collector' but I cannot find anything really
comprehensive.. most said it is a classic problem with an obvious
result :-p

Anyway, What I need is

the Probability of getting a complete set on exactly the Nth instance
(ie, set was incomplete in the first N-1 instances)

Can someone please help to derive and explain a general expression in
terms of N and k?

Thanks a million!!!

Johann Wiesenbauer wrote:
> > Suppose a computer can generate a whole number from 1
> > to k in one
> > instance randomly.
> >
> > What is the expected number of instances, n required
> > for each given k
> > such that a complete set of 1 to k has been produced?
> > Ie, the first
> > time where you get all of the numbers from 1 to k.
> >
> > What is the value of n such that Prob(set first
> > completed in exactly
> > nth instance) is highest?
> >
> > Thanks all!
> >
>
> Let X be the random variable for the number of tries to obtain a full set of numbers 1 to k. Then X can be written in the form
>
> X = X1+X2+...+Xk
>
> where Xi denotes the number of tries for a "new" number on condition that a total of i-1 distinct numbers had been produced so far (i = 1,2,..,k).
>
> Obviously Xi obeys a geometric distribution with mean
>
> E(Xi) = k/(k-i+1) (i = 1,2,..,k)
>
> Hence,
>
> E(X) = k(1/k + 1/(k-1) + ... + 1/1) ~ k log k
>
> Johann

.