2
$\begingroup$

This question is very similar to this unanswered one https://math.stackexchange.com/questions/242607/estimate-number-of-distinct-items .

Suppose I have a large array of $n$ integers and I want to estimate how many distinct integers it contains. I can sample uniformly from the positions of the array (with replacement) and suppose the true number of distinct integers is $N$ . I would like to do as few samples as possible. What is the best way to get an estimate for $N$?

This appears to be closely related to the problem of estimating species richness, but having looked at as much literature as I could (being a non-expert) I didn't see a perfect fit.

Improve this question
$\endgroup$
5
  • $\begingroup$ There is a tension here between taking fewer samples and obtaining a more accurate estimate. You need to specify how you want to balance these competing demands before "best" is well-defined. $\endgroup$
    – Qiaochu Yuan
    Commented Nov 24, 2012 at 4:03
  • 1
    $\begingroup$ The problem is that the worst case scenario is dismal here: take $N\ll n$ and put in the numbers $1,2,\dots,N,1,1,1,\dots,1$. The beginning part, which is the only important one, is virtually invisible in the sea of ones when you are doing the uniform sampling: until you've done at least $n/N$ samples, there is a good chance it is not detected at all and it is quite a question whether you are willing to get up to linear in $n$ when choosing the sample size. $\endgroup$
    – fedja
    Commented Nov 24, 2012 at 4:36
  • $\begingroup$ A good point. Does it help if I put a limit on the maximum number of times the most frequent item can occur? Also, if I just want to answer the question "How likely is the number of distinct items to be more than $x$, say?", is that any easier (depending on what $x$ is)? $\endgroup$
    – Arnott
    Commented Nov 24, 2012 at 8:19
  • $\begingroup$ @QiaochuYuan, Ideally I would like to do a constant number of samples but I am also in just understanding the stats so I can see if I can change the setup to make something else work. I may, for example, be able to get away with just answering "the number is large" or "the number is small" but as pointed out, in the worst case you can't even do that. $\endgroup$
    – Arnott
    Commented Nov 24, 2012 at 8:32
  • $\begingroup$ This problem seems very difficult. Consider just the case where your array is the elements of an $n \times n$ multiplication table. Then the problem reduces to one first studied by Erdos in the mid 1950s. See, for example, mathoverflow.net/questions/31663/… $\endgroup$
    – Benjamin Dickman
    Commented Nov 24, 2012 at 10:20

4 Answers 4

Reset to default
3
$\begingroup$

This is a standard statistical problem. It goes under a number of names, which is probably why you haven't been able to find it by Googling. In ecology, it's called "estimating species richness", and in computer science it's called "stream estimates for $L_0$.". The classic solution is Good–Turing frequency estimation, which was developed during the second World War. It's still good enough for many practical purposes. I'd start by reading about that, and if that's not good enough for your application, following the literature forward from there.

Arthur B is right that you can do it using MCMC. But that's using a bulldozer to pluck a flower. It works, but MCMC is really meant for much harder jobs.

Improve this answer
$\endgroup$
0
$\begingroup$

You could model the problem by assuming that your $n$ numbers are drawn from a multinomial distribution with a parameter drawn from a flat Dirichlet prior.

Draw a fixed number $p$ of integers, then run a MCMC on the space of parameters of the multinomial distribution. Integrate the random variable $N$ over this chain.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @ArthurB, Thanks. I was looking for something computationally quick really. The information at math.stackexchange.com/questions/75758/… is the closest things I have found so far. It seems curious that such a basic question doesn't have a standard answer. $\endgroup$
    – Arnott
    Commented Dec 5, 2012 at 22:00
0
$\begingroup$

You don't say what your motivating application is. It would be more effective to sample without replacement, but maybe that is not an option. You also suggest that you might be willing to limit the maximum number of times the most frequent item occurs. I think a lower bound on the least frequent color might be more helpful (equivalently, posit that anything below a certain relative frequency is an "anomaly" and does not count). I am just going to assume that a puzzle-master, unknown to us, has put $n$ colored balls in a bag according to some private scheme she made up. We sample $s$ times with replacement and must draw conclusions as best we can. I will assume that $n$ is known.

I think that you don't find a good match with species richness because you are not asking the right questions. What you can say something about is the possible frequency of the colors you have already seen. Indirectly that tells you something about the number of colors, but very little.

Do a thought experiment about various outcomes and what you can conclude. Suppose first that as you keep drawing (then replacing) balls they are all green. You can say that there seem to be lots of green balls. You can say "With $95\%$ confidence the number of green balls is at least $m=m(n,s)$" , equivalently the number of non-green balls is estimated to be no more than $n-m.$ However I do not think that you can make any conclusion about their colors. Even if you get a hint: " There are at least $q$ balls which are not green and they are either all the same color or else each has a color unique to itself" I do not think you have any way of saying which is more likely. And with no hint the only change is that perhaps $q=0$.

I don't think that a limit such as "no color occurs more than one third of the time" will help. Suppose instead that (for a not too small $s$) the balls come out "red, white, blue, yellow, pink" with frequencies roughly $2:2:2:1:1$. Then you can say "With $95\%$ confidence the number of red,white,blue,yellow and pink balls" balls is at least $m$" for the same $m=m(n,s)$ as in the all green scenario. AND you can say that whatever the number of balls of those five colors the frequencies will be roughly 1/4,1/4,1/4,1/8,1/8. But you are no better of on the question of how many unseen colors might there be.

I am less confident what one might say in the $2:2:2:1:1$ scenario above if along the way you say a single black ball, but I do not think that you could say much.

Another extreme is if you have made a reasonable number of samples and never seen the same color twice. Would that occur in your application? Then you might be able to say with some confidence that few, if any, colors repeat. Then you could (I would think) answer the "more than x colors" question as likely having seen many less than $x$ balls.

Improve this answer
$\endgroup$
0
$\begingroup$

A very similar question was asked at https://cstheory.stackexchange.com/questions/16582/l-0-estimation-not-in-a-stream where links to two particularly useful looking papers were given. Those were http://dl.acm.org/citation.cfm?id=335230 where you get worst case upper and lower bounds and http://theory.stanford.edu/~sergei/papers/distinct-analco.pdf where you get a good method if the input data has a power law distribution.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .