# Estimate number of distinct items

I have a large array of $n$ integers, some of which may be repeated, and I want to estimate how many distinct integers are in the array. Say the number of distinct integers is $N$. I can sample with replacement easily but can't afford to sample anything like $n$ samples as $n$ is too big. If I sample $y$ positions uniformly with replacement, let $X$ be the number of distinct integers I get in the sample. How can we use $X$ to give an estimate for $N$?

When $y$ is $\Omega(n \log n)$ then we expect to have seen every position in the array and so $X=N$ with high probability by an application of http://en.wikipedia.org/wiki/Coupon_collector%27s_problem . When $y$ is much smaller than $n$ it seems we might only be able to give probabilistic upper and lower bounds as estimates for $N$ depending on the distribution of duplicates in the input array.

EDIT: As pointed out in the comments, there was an error in the original question (now fixed).

-
By "sample with replacement" and "sample $y$ positions", do you mean that you take $y$ samples, each at a position independently uniformly selected from the $n$ positions in the array (so a position may be sampled repeatedly)? – joriki Nov 22 '12 at 14:01
@joriki, yes. Sorry that wasn't clear. – Arnott Nov 22 '12 at 14:02
Then your formula is wrong. As $y\to\infty$, $E(X)\to N$ and $n/y\to0$, so $E(nX/y)\to0\ne N$. – joriki Nov 22 '12 at 14:04
@joriki. Oh dear. Do you know how to fix it? – Arnott Nov 22 '12 at 14:05
This is commonly known as the problem of species richness estimation. A web-search on this phrase should turn up lots of references. – r.e.s. Nov 22 '12 at 19:40