# Bag with infinite number of colored balls

Consider a situation with a bag with infinity number of balls. Each ball is of some color. Number of colors is finite but it is not known. Balls are drawn from the bag one by one and checked for the color. We want to stop drawing balls when there is small probability that we will find color that is not already drawn. Or more exact, we want to be very sure (with large probability) that there is small portion of balls in bag with colors that are not already drawn. Is there a statistical model to describe when to stop?

-
You probably want to assume some things about iid and so forth. Are we to take that the colour of the next ball you draw is independent of the balls you have already seen, and that the probability that the next ball is of a given colour is $1/N$ where $N$ is the (unknown) number of colours? –  Willie Wong Nov 2 '10 at 19:04
Problem is that we have to assume some things :-) –  Ante Nov 2 '10 at 19:21
Sorry, I wanted to write more. I'm looking for a model that assumes as less as possible. Drawing of balls can be viewed as process of learning colour distribution. –  Ante Nov 2 '10 at 19:24
You are right that you are learning the color distribution. Unfortunately, if a color is rare, it takes a lot of draws to find it. Without some a priori model of the distribution of colors, you won't know when to stop. If you have (and trust) such a model you have a chance. Say you think the colors are distributed in a power law with some termination. Then from the more common colors you estimate the power law, and when the next color hasn't shown up enough you conclude that it isn't there. But you are banking on the model. You can say there is no color at some frequency with some prob. –  Ross Millikan Nov 3 '10 at 4:22
Fyi this situation is sometimes called the palette extreme. For example, Mehlum's "Island problem revisited" 2009. Preprint > folk.uio.no/hmehlum/publications/TASMehlum.pdf –  alancalvitti Dec 11 '12 at 3:21

This problem often comes up in Biology when one is interested in estimating the number of species in an area based on some survey. There are a wide variety of methods developed to suit the specific application in hand. For example, it is very hard to come up with a good estimator for the number of biological species in a rain forest since there are too many "extremely rare" species to take into account. There is no one unique estimator that is globally optimal and you would have to customize your own estimator based on your needs. A good starting point is this link and references therein.

-
Thanks for your answer. I heard this problem from friend of mine who is biologist. This kind of article I was looking for. –  Ante Nov 2 '10 at 22:19
@Dinesh, +1, can you please provide key citations? –  alancalvitti Dec 11 '12 at 3:13

If you assume there are N colored balls, with equal frequency p=1/N, then this should be pretty do-able. Of course, you're desired confidence interval will affect the answer.

Without working out all the details, consider that you have drawn the point where you see a few colors 2 or 3 times. By considering how many balls you have drawn, and how many uniques have been witnessed, you can make an estimate of that N within a confidence bounds.

I can give the details if you like, but if these assumptions are acceptable you can probably take it from here?

-