-1

If things are chosen randomly from n possible choices, then number of selections that all possible choices are selected at least once is approximated by $nH_n$, where $H_n$ is $nth$ Harmonic Number.

The lower bound of number of selections seems to be $n$ i.e in a rare event, one may be able to select all choices at least once after n selections.

Is this possible? is this lower bound right?

What is the likelihood of such a rare event?

What is the probability that a collection of size x has all the possible choices at least once

What is the probability P(x, n) such that it takes x or less than x draws to obtain all n distinct elements, when drawing with replacement from a set of n distinct elements.

I ran a simulation 10000 times for n=100 ($nH_n$=521), it shows that minimum_number_of_selections = 279 and maximum_number_of_selections = 1302.

crypt
  • 143
  • The lower bound on the number of selections (not the expected number) is indeed $n$, as you need one of each of $n$ types. Your $279$ is higher than $100$ because you didn't try enough. The chance of getting $100$ different ones in $100$ tries is very small. What have you tried? – Ross Millikan Feb 16 '23 at 06:23
  • i ran simulation 10000 times (question updated). – crypt Feb 16 '23 at 06:35
  • 1
    Don't put such a big $n$ in your simulation. It will "never" be achieved with that :DDDDD!!!!!!!! – ploosu2 Feb 16 '23 at 06:36
  • Btw, it isn't the expected number of selections, that's in question here. That is just a number, it doesn't vary. You should say "the number of selections" (before seeing all choices). – ploosu2 Feb 16 '23 at 06:49

1 Answers1

2

Yes, $n$ is possible to achieve if all the $n$ first draws are different.

The probability is $\frac{n!}{n^n} = \frac{(n-1)!}{n^{n-1}}$ because you need to get a permutation of the objects but all in all you can get any sequence.

ploosu2
  • 8,707