3
$\begingroup$

For example, say you have a black box that has a number of n-sided dice in it. You have 4-sided dice, 6-sided, 8, 10, 12, 20 and so on. The die sides are all A except for one side that says B, e.g.

dice

You select one of these dice in the black box. You aren't sure which one. You start rolling it and the output you see from the black box is either A or B. What is the minimum number of times would you need to roll the die to determine which which n-sided die you have?

My initial thoughts would be to track the probability of B coming up as you make more and more rolls and look at the coefficient of variation. Once the coefficient of variation had dropped below some threshold, the probability of rolling B would have stabilized. Then you relate that probability to the number of sides the die has (16.6% = 6 sided die). The number of rolls required to reach this stabilization would then be the minimum number of rolls.

Alternatively, my other thought was to look at standard error and confidence intervals. Make a number of rolls and keep track of the probability of rolling a B. Once the confidence interval for the mean probability of a B has dropped below whatever threshold you have (e.g. +/- 1%) that would be your criterion for saying the probability had stabilized and reached its 'true' value, and you then get the minimum number of rolls.

Both of these approach I think would require multiple runs. You could have have a succession of B rolls (or a longer string of A rolls) that would then throw of the coefficient of variation / standard error and make it take longer to drop below whatever threshold you decide on.

Is there another / better way of approaching this? It seems to be similar to a coin toss problem, like how many tosses you would need to determine if a coin is fair or not, but I haven’t been able to follow / apply that to my problem when the 'true' probability is unknown (.e. not 50%).

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What do you know about the contents of the box? Do you have the full distribution of all the dice in it? $\endgroup$ – whuber♦ Sep 9 '18 at 19:43
  • $\begingroup$ Without a prior distribution on the size of the dice, and the distribution of its faces, it's impossible to resolve this. As an example the standard 6-sided dice is equivalent in its outcomes to a 12 sided dice where we doubled the number of times each face occurs. So you wouldn't be able to deduce $n$ unless you can also keep track of which side came up, by say, marking it with a pen. $\endgroup$ – Alex R. Sep 9 '18 at 19:47
  • $\begingroup$ I don't know the contents of the box or have an idea of what the size distribution of all the dice is. For background, this is for a set of experiments with a pass/fail outcome (A/B in the picture, not necessarily 5/6, could be 7/10, 3/20 etc.). I'm interested in knowing how many repeat tests would be necessary before you can say you've gotten to the 'true' pass probability. Relating it to dice faces was me trying to give a better / more easily visualised example (maybe it isn't better). $\endgroup$ – Aaron Sep 9 '18 at 23:58
  • $\begingroup$ My intuition is that this problem would be unsolvable unless you know the distribution of the dice in the box. Because while you could use probabilistic arguments to differ between a 6-sided and an 8-sided dice, the number of rolls to distinguish between an n-sided and an (n+1)-sided dice will depend on n. So there would not be a general solution to the problem without knowing, at least, the upper bound of n in the box. $\endgroup$ – Phil Oct 9 '18 at 11:28
0
$\begingroup$

Per the comments above, this appears unsolvable as-is without knowledge about the sizes of the dice (or at least some prior distribution on it).

However, your comment indicates that your actual problem is a different one, namely, how many trials of a binomial experiment with unknown $p$ you need to run to estimate $p$ with a prespecified precision. This is a question of a confidence interval for a binomial distribution, so our questions carrying both tags may be useful.

If you can bound $p$ away from 0 and 1, Confidence interval for Bernoulli sampling gives you a couple of ways to calculate CIs that you can backsolve for the number $n$ or trials. Conversely, Confidence interval around binomial estimate of 0 or 1 is helpful for the degenerate cases. It's the very small (but nonzero) and very large (but non-one) $p$s that will give you trouble, so once again, some prior information on $p$ may be indispensable.

| cite | improve this answer | |
$\endgroup$

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.