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!!!
>

For topics like this you should look up D. Knuth, "The Art of Computer Programming" (more precisely, vol 2, p 64)

Here is the gist of it in my own words. Suppose that the sequence

a_1a_2a_3...a_n (*)

is "complete" (as to occurrences of the numbers 1,..,k), whereas

a_1a_2a_3...a_(n-1) (**)

is still incomplete. The probability for the latter event is

S2(n-1,k-1)k!/k^(n-1)

where S2(n-1,k-1) is referring to Stirling numbers of the second kind. In fact, S2(n-1,k-1) gives by definition the number of all partitions of an (n-1)-element set into exactly k-1 subsets, corresponding to the k-1 numbers, which actually occur. Furthermore, those numbers can be arbitrarily permuted in (k-1)! ways and the missing number can be chosen in k ways, accounting for the factor k! above. Finally, the total number of sequences of length n-1 is k^(n-1), which is the denominator of the fraction above.

The combined probability p(n,k) that (*) is complete, while (**) was still incomplete, i.e. the probability you were asking for, is then

p(n,k) = S2(n-1,k-1)k!/k^n

because a_n is the missing number with probability 1/k.

Johann
.

Relevant Pages

  • Re: My views on evolution
    ... >> The simple fact is that the probability calculations proposed by IDers ... > to the scientific evidence, but that the scientific evidence is ... How 'incomplete' is the Bible story, ...
    (talk.origins)
  • Re: card counters and dice counters
    ... my opinion is that current probability ... Evil Nigel ... considered incomplete until they were proven beyond any doubt to be ... current probability theory seems to hold up under the most critical ...
    (rec.gambling.craps)
  • Re: Where Was Jesus Born?
    ... >and credentialled authority, it seems to me there is as much ... >probability that it was complete as there is that it was incomplete. ... Prev by Date: ...
    (soc.religion.mormon)