Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
    
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
2  
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
show 12 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.