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

Your Answer

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

Browse other questions tagged or ask your own question.