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 (as a function of the two distributions) for me to know, with high probability, which die I am rolling. The closer the
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). What I've found is that if I one coin has Pr[H] = 0.5 and one has Pr[H] = p > 0.5, after $n \geq -\frac{2p}{(p - \frac{1}{2})^2} \ln \epsilon$ coin flips, I can guess which type of coin it is with accuracy $1 - \epsilon$.
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).
I don't know if that'll answer fully your question, but to distinguish between a fair coin and a $\varepsilon$-biased one (for $\varepsilon$ being less than some absolute constant), you need $\Omega(1/\varepsilon^2)$ independent coin tosses (to be right with probability greater than, say, $2/3$). This is a ''folklore result'' and can be derived from the total variation distance between two Binomial distributions, see e.g. Fact 1 in this paper.
For the complexity of distinguishing between two discrete distributions, see e.g. Optimal Algorithms for Testing Closeness of Discrete Distributions by Chan et al. and the references therein.
More generally, the following article (an introduction to property testing of distributions) by R. Rubinfeld may be of interest to you. Some relevant slides are also available from a workshop (STOC '14): look at the first talk of Session 1.