If I do not know how much sides a dice has, how often should I throw it to know the number of sides?

Question

Lets say we have a dice with an unknown number of sides, and we are only allowed to see the results of the rolls. How often do I have to throw the dice to know the number of sides?

Answer 1

There is no way to determine the number of sides with absolute certainty. Even if a die has a million sides, there's a chance that a googolplex of throws will all show the same side of the die.

You need to be more specific about what you want to do. Do you want an estimate of the number of sides? A confidence interval? Do you know that the sides are consecutively numbered from $1$ to some number $k$? Or would it be possible that the die has three sides that are numbered $1$, $2$ and $4898887931$?

Answer 2

If you know the faces are labelled $1,\ldots, n$, then even after a single row "$k$" you may make an educated guess that the die has $2k-1$ faces. While this is the best guess possible with just one roll, it is certainly not giving us a lot of confidence (after all, the probability of hitting "$k$" even if it really is a $(2k-1)$-faced die is only $\frac1{2k-1}$). For more confidence, you may keep rolling and at any stage guess that the number of faces is $2\bar x-1$ (rounded to next integer) where $\bar x$ is the average roll you got. Since the variance of an $n$-sided die is $\frac{n^2-1}{12}$, the standard deviation for $2\bar x-1$ obtained from $m$ rolls with an $n$-sided die is $\sqrt{\frac{n^2-1}{3m}} \approx \frac{n}{\sqrt{3m}}$ and you want that $\ll 1$, at least $<\frac16$, say, for a $3\sigma$ confidence, you should make sure that $m>12n^2$ to obtain a good estimate of $n$ from $\bar x$ alone.

However, if you really do as above, you can expect every single face to have appeared several times (about $12n$ times). Thus a more promising method is to collect die faces until you are confident to have seen them all (or maybe even earlier). (Another advantage: This works also if the faces are labelled by anything else but consecutive numbers).

If $n$ is large and we make about $n$ rolls (so much less than $12n^2$), we can expect from the Poisson distributon about $\frac ne$ of the faces to not have shown up yet and about $\frac ne$ to have shown up exactly once. So an estimate for $n$ can be obtained by rolling until the number of faces "collected" divided by the number of rolls is sufficiently close to $1-\frac1e$ and guess that the number of rolls then equals $n$. This estimate has a large error margin though (esp. as we did not specify what "sufficiently close" should mean). Alternatively, roll until the number of faces seen once equals the number of faces seen twice (which may not happen exactly) and guess that $n$ equals half the number of rolls.