Number of selections with replacement to choose every object at least $n$ times

95 Views Asked by At

Let $n > 1, m > 0$ be natural numbers. How many times would I have to choose from $n$ distinct objects (with replacement) so that I have chosen each one at least $m$ times, with probability $0.95$ or greater? I've seen the coupon collector's problem, and specifically, the generalization for $m$ objects, but I don't know how I can compute the value I want given that is shown there.

My goal is to have a formula or expression that I could 'plug' $n,m$ into and get an answer. If it is of any help, my $n$ is fixed to $100$ for what I need to do, but I would prefer a more general answer (hence my formulation above) so I can understand what is going on.

1

There are 1 best solutions below

5
On BEST ANSWER

We make the slightly incorrect assumption that the number of objects you get of one type is independent of the number you get of any other type. It is not correct because if you get lots of one you get fewer of another, but if there are lots of types the dependence will be small. In that case, the distribution of the number you draw of a given type is close to Poisson. Say you draw $N$ objects. The average number is $\frac Nn$, which corresponds to the parameter $\lambda$ in the distribution. The chance you get $k$ of a given object is then $\frac {\lambda^ke^{-\lambda}}{k!}$. The chance that you have less than $m$ of a given type is $q=\sum_{i=0}^{m-1}\frac {\lambda^i e^{-\lambda}}{i!}$. The chance that you have at least $m$ of a given type is $1-q$ The chance that you have at least $m$ of all the types is then $(1-q)^n$

Given your target probability $p$ you can then write $$p=(1-q)^n\\\log p=n \log(1-q)\\q \approx \frac {-\log p}n$$ where the approximation comes from taking the first term in the Taylor series for $\log (1+x) \approx x$, valid when $|x| \ll 1$. You can compute the required $q$, then find the proper $\lambda$ to make $q=\sum_{i=0}^{m-1}\frac {\lambda^i e^{-\lambda}}{i!}$. This is a one dimensional root finding problem. As the sum is monotonic in $\lambda$, it is an easy one. Once you get $\lambda$, you get $N=n\lambda$ as the number of objects to draw.