# Estimate the number unique elements in a finite sample space via a finite sample without replacement

I have a pool of $N$ items. I know that there are $c$ distinct types of items in $N$ and the distribution of the distinct types is uniform, i.e. if I sample 1 item from the pool its chance of belonging to any of the $c$ distinct types is $\frac{1}{c}$.

I sampled $M$ items from this pool without replacement, and there were $d$ distinct types of items.

Can I construct an unbiased estimator of $c$ based on $N$, $M$, and $d$? What if the types are not uniformly distributed? Is there a general method for this?

I tried using MLE by saying that the likelihood of my observed sample is as below

$$L = \frac{1}{c^d}\left(1-\frac{d}{c}\right)^{M-d}$$

because I have observed $d$ distinct elements each with probability $\frac{1}{c}$ and the other $M-d$ times I observed an element that I have sampled before with probability $\left(1-\frac{d}{c}\right)$.

I can take $log$ and try to find the maximum but I got $c = M$ and I couldn't get further proving the properties of this estimator. So I am stuck at this point.

Notice that your likelihood doesn't include $N$, which is a pretty good sign you're not taking the finite nature of the sample into account.

The first thing you know, assuming you're sampling all units with equal probability of selection, is that there are exactly $\frac{N}{c}$ units of each type, since the probability of selecting from each type is $\frac{1}{c}$.

Given $c$ types, there are $c\choose d$ ways to choose which $d$ types are the only types in your sample. If you see $d$ different types, then you've selected at least one of each of these types, so you've fixed $d$ elements of the sample already. The remaining $M-d$ elements need to be selected from the remaining $d(\frac{N}{c}-1)$ units in the $d$ classes you're observing. Therefore the likelihood is:

$$L=\frac{{c\choose d}{d(\frac{N}{c}-1)\choose M-d}}{N\choose M}$$

We want to maximise with respect to $c$, but honestly I can't think of a neat way to do this at the moment.

• LogL and get rid N choose M as a constant Nov 14, 2017 at 12:22
• I think your solution is c = d/M*N, basically to scale up the estimate proportionally which is the sensible thing to do. I tried N = 250_000_000, c = 2_500_000, M = 1_000_000 and I got d = ~823_439, so the answer was too large. The fact that ~170_000 accounts were repeated was not taken into account. May be need to keep thinking Nov 14, 2017 at 21:00
• I don't think you've correctly maximised the likelihood. This needs to be maximised with respect to $c$, but $c$ must divide evenly into $N$, and this constraint makes it difficult to come up with a closed form solution. Running simulations show that maximising this function seems to converge to the correct answer but with huge variability, especially when $M$ is small. This makes sense, because if you have a small sample, then it's difficult to distinguish from a population where $c$ is medium vs $c$ is large. Nov 18, 2017 at 23:23