In a bag, there are two dice, each with sides weighted differently. I know the weighting of the two dice. I reach into the bag and pick one out with equal probability. I want to know how many rolls it will take for me to know, with high probability, which die I am rolling.

Put differently, I believe I am trying to find the sample complexity of an algorithm that distinguishes between two different discrete distributions. I believe I have a way to do this for two weighted coins (using a tail bound on the binomial distribution) and I'm pretty sure there should be a simple reduction, but I can't find a good explanation online, perhaps because I lack the proper vocabulary (I come from a CS background and don't know stats/probability super well).

Ultimately what I want is that if someone tells me the distribution of the two dice, I plug those distributions into a function that tells me how many rolls it will take for me to make a guess that will be correct (say) 90% of the time.


I'd be inclined to treat it as a Bayesian problem.

If you do that, you end up with the ratio of posterior probabilities of the two multinomials being the likelihood ratio times the ratio of prior probabilities

$P(M_1|x_1,x_2,...)/P(M_2|x_1,x_2,...) = P(x_1,x_2,...|M_1)/P(x_1,x_2,...|M_2)\times P(M_1)/P(M_2)$

Assuming your prior probabilities are both 0.5, you just get the likelihood ratio.

$P(x_1,x_2,...|M_1)/P(x_1,x_2,...|M_2) = {\Lambda}_{12}$

From that and the fact that the posterior probabilities sum to 1, you can back out the two posterior probabilities:

$P(M_2|x_1,x_2,...) =1/[1+\Lambda_{12}]$

$P(M_1|x_1,x_2,...) =1-1/[1+\Lambda_{12}]$

(And if the prior probabilities aren't equal, it's only a simple additional term in the calculation).

From here you can figure out what the chances are for concluding correctly at some sample size. If you set some cutoff for what constitutes 'high probability', you can find a suitable $n$.

  • $\begingroup$ Hi Glen_b, I'll edit my question to make it more clear, but precisely what I'm wondering is how to decide ahead of time how big my sample size should be, as a function of the distributions. So if the distributions are close, I'll need more samples, and vice versa if the distributions are very different. $\endgroup$ – dodger487 Nov 5 '14 at 15:22
  • 1
    $\begingroup$ Glen has sketched an excellent answer to precisely that problem (+1). $\endgroup$ – whuber Nov 5 '14 at 15:35

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.