How to find out number of possible outcomes by trying over and over?

Question

While working on my network exploration tool project, I've ran across the problem of reliably determining number of possible exit addresses of a tunnel with single entrance. I've came up with following formulation:

Given black box with infinite number of marbles of N different colors. What is minimal number of marbles should I get out of box to determine N with some level of confidence, if each color has the same probability to roll out?

I have no idea to where start from. Maybe this has some relation to Bayes, credible intervals, or confidence intervals? Really, I have no idea.

Answer 1

Suppose after some draws you've seen $k$ different colors. Furthermore, suppose you haven't seen any new colors in the previous $t$ draws.

If there are more than $k$ colors, the probability that you see a new color within $t$ draws is at least $1-\left(\frac{k}{k+1}\right)^t$. By letting $t$ (the number of draws since the last ($k^{\text{th}}$) new color was seen) get large, we can make the above probability get very close to 1. So if you haven't seen a new color, it is likely that there are no new colors to see.

The exact strategy to adopt may depend on how expensive it is to make draws.

Answer 2

If you draw $m$ marbles, the chance that you not have seen a particular color is $\left(\frac {N-1}N \right)^m$, so the chance you have seen it is $1-\left(\frac {N-1}N \right)^m$. If we make the incorrect assumption that the colors are independent, the chance that you have seen them all is $\left(1-\left(\frac {N-1}N \right)^m\right)^N$ This will be very close when $m$ is rather larger than $N$, as having more than expected of one color will not influence the chance to have seen another color very much.