Estimate number of distinct items 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.
 A: 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.
A: 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.
A: 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.
A: 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.
