A friend of mine inspired this question:

Given a fair die, can one accurately estimate (within some margin) the size of the die given enough rolls? For example: If I roll a die 1000 times and all the numbers fall on and between 1 and 5, I estimate the size of the die is 5.

My question is: is this an accurate estimate? Will we always be able to predict the size of the die within some margin of error?

Any help is appreciated.

  • $\begingroup$ Are you assuming that you know that it starts with a 1 and goes up (without skipping any numbers)? $\endgroup$ – TravisJ Mar 14 '15 at 21:13
  • $\begingroup$ Do you know how many sides the die has? $\endgroup$ – John Mar 14 '15 at 21:15
  • $\begingroup$ To clarify: We're assuming the die starts at 1 and goes up to some number n. The only information we are given is the results of k rolls. The question then becomes: How large does k have to be in order to get a good enough estimate? $\endgroup$ – Rambo V Mar 14 '15 at 21:28
  • $\begingroup$ I'm still unclear as to whether you know how many sides the die has. Does "goes up to some number $n$" mean it has n sides numbered $1$ to $n$, or that it has some known number of sides with a maximum value of $n$ on one (or more) of the sides? $\endgroup$ – John Mar 14 '15 at 22:11
  • $\begingroup$ Like the post says: the only information you are given is the result of k rolls. This does NOT include the size of the die. $\endgroup$ – Rambo V Mar 14 '15 at 23:49

As Bruce has said in the comments, the most obvious choice for the estimator of the number of sides is the maximum of all the $k$ rolls seen. Let's take that and see what we can learn about it.

Let $x_i$ be the result of the $i$th roll. Then our estimator is $$ \hat{N} \equiv \max_i \; x_i. $$ So the way that the estimator would fail, would be if the largest value of the die doesn't come up in the $k$ rolls. Because the die is assumed to be fair the probability distribution for each value is equal: $$ P(x_i = n) = \frac{1}{N}, \qquad \forall \quad i, \text{and for any } n. $$ The probability that $N$ doesn't get rolled would be $$ P(x_i \ne N) = 1 - P(x_i = N) = 1 - \frac{1}{N}. $$ Over the full course of $k$ rolls, we can calculate the probability of never rolling the largest value $(N)$ as $$ P\left(\bigcap_{i=1}^k (x_i \ne N)\right) = \prod_{i=1}^k P(x_i \ne N) = \left( 1- \frac{1}{N}\right)^k = \left(\frac{N-1}{N}\right)^k. $$ Now say that we want to compare this with some margin of error $\epsilon$. ( For example, an $\epsilon= 0.01$ would represent a 1% possibility that the largest number doesn't show up in our $k$ rolls.) $$ \begin{split} \left(1-\frac{1}{N}\right)^k &\le \epsilon \\ k\;\underbrace{\log\left(1 - \frac{1}{N}\right)}_{<\,0} &\le \log(\epsilon) \\ k &\ge \frac{\log{\epsilon}}{\log\left(1-\frac{1}{N}\right)} \end{split} $$ So, given a margin $\epsilon$ set to any arbitrary value (well, it must be positive and less than 1), and the number of sides of the die, we can tell how many rolls $(k)$ we need to achieve that confidence. A couple of tables below show some values of $k$ given an $N$. $$ \epsilon = 0.01 $$ $$ \begin{array}{l|cccccccccc} N & 2 & 4 & 6& 8& 10 &12 &20 &26 &40 &100\\ \hline k & 7 & 17 &26 &35 &44 &53 &90 &118 &182 &459 \end{array} $$ $$ \epsilon = 0.001 $$ $$ \begin{array}{l|cccccccccc} N & 2 & 4 &6 &8 &10 &12 &20 &26 &40 &100 \\ \hline k& 10 &25 &38 &52 &66 &80 &135 &177 &273 &688 \end{array} $$ Alternatively, we can plug in the number of rolls and see how large a die we can identify with a set margin for error. This can be found by backing out what $N$ can be identified within a margin $\epsilon$ with a given $k$. Working it backwards from above, you get something that looks like $$ N \le \frac{1}{1 - e^{\frac{\log(\epsilon)}{k}}}, $$ which says that for $k =1000$, you'd be able to identify a 216-sided die with a 99% probability, and an 87-sided die with a 99.999% probability.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.