Computing sample size for having at least one individual of each level for a categorical variable? Imagine a categorical variable with 10 levels. I would like to know how many individual I need to sample from the whole population to have a .95 or .99 probability of having at least one individual of each category for that variable?
 A: One very pragmatic way to find the answer is with simulation. Let's first adress an easier question: given a number N of trials what is your confidence that you will have at least class once. In the equiprobable case with 200 classes you could for example do a simulation like this: 
sim.runs <- 10000 # simulations run, increase to get higher accuracy
outcome.all.classes.in <- vector("logical", sim.rums)
n.classes <- 200 # number of classes
n.samples <- 1000 # number of samples
for (i in 1:sim.runs)
{
random.sample <- ceiling(runif(n.samples, 0, n.classes)) # generate simulated sample
outcome.all.classes.in[i] <- length(unique(random.sample)) == n.classes # find out if all classes are in
}
estimated.conf <- sum(outcome.all.classes.in)/sim.runs # output frequency of all classes being

You would need to find out how many simulation runs you need to have the precision you need (i.e. the needed digits should be stable over multiple runs). You can then experiment with the number of samples (n.samples). There is probably also a more fancy combinatorial way to calculate this, but I think this method is more adaptable to various more complicated cases. Depending on your sample sizes computation might be an issue.
A: If the probability of the most rare category $c$ is $p$, then the probability that there is no category $c$ in the population of $N$ individuals is $(1-p)^N$. That is, the probability that there is at least one individual $c$ is $1 - (1-p)^N$. So, from the minimal $\epsilon$ confidence you can get $\epsilon = 1 - (1-p)^N$ and find $N$ from here.
A: I think I found the answer:
In this paper from Thompson et al., there is a explanation and a demonstration of how to compute the sample size $n$ for a multinomial law, which is what I want here (a categorical variable with k classes).
The short answer is :
$n = max_{m} \left( z^2 \frac{(\frac{1}{m})(1-\frac{1}{m})}{d^2} \right) $, 
where $n$ is the sample size we want to compute, $z$ is the upper $\left(\alpha/2m\right)$x100th percentile of the standard normal distribution, $m$ is an integer as $0<m\leq k$ and $d$ is the precision ny which we want to estimate the proportion of each class.
Interestingly, the author shows that the max sample size $n$ is obtained for relatively small value of $m$ and that it is not necessary to know ahead of time the number of classes in the population.
However, I think that when $k$ is big (as it is the case for me, $k=256$), the number $k$ will influence the sample size, because one will have to decrease the precision $d$ he wants to achieve. For example, if $k=3$, the theorical distribution would be all classes have a proportion of $1/3$. In this case, having a precision of 1% or 5% ($ d = 0.01$ or $d=0.05$) is fine. Now, with $k=256$, the theoretical proportion is $\frac{1}{256} \simeq 0.0039$. If one choose $d = 0.01$, it means that 0 will be a possible proportion. To avoid that, one would like to choose $d < \frac{1}{k}$.
In my case, with a risk $\alpha = 0.01$ and a precision $d = 0.003$, the needed sample size is : 218 828 !! 
I hope this will be useful for someone else.
