# How many times do I need to toss to differentiate between two biased coins?

Let's say I am promised that a coin is biased to have probability of heads either $$p_1$$ and $$p_2$$. How many times should I toss it to ensure that I know which coin I got, assuming I can be wrong in my conclusion with probability $$\varepsilon$$?

According to this video, if $$p_1 = \frac{1}{d}$$ and $$p_2 = \frac{2}{d}$$ for some $$d\geq 2$$, one needs $$d$$ tosses. There is no $$\varepsilon$$ mentioned there and it is claimed as a straightforward fact. The exact statement is, ""If you want to confidently distinguish between these biases ($$\frac{1}{d}$$ and $$\frac{2}{d}$$), you need around $$d$$ tosses".

Can anyone explain how to arrive at that result and how to generalize it for arbitrary $$p_1, p_2$$? To be specific:

1. I am promised that my coin yields heads with probability either $$p_1$$ or $$p_2$$.
2. I have to decide how many times to toss it.
3. After that many tosses, I can see the results and I should be able to correctly answer which coin I got with error at most $$\varepsilon$$.
• The result quoted can't possibly be right. However many tosses there are, you can't obtain certainty. Commented Dec 4, 2023 at 18:26
• So $p_1$ and $p_2$ are known? Commented Dec 4, 2023 at 18:55
• I don't quite follow the coin analogy, it seems the goal is rather to distinguish between a uniform and non-uniform distribution for all $d$ possible outcomes. In the previous video he gave a formula $E(||p_d-\hat{p_d}||_1) \le \sqrt d / \sqrt n$ alongside the claim that '$n$ modestly bigger than $d$, that is a big constant times $d$' would thus result in 'the expectation of a very small error'. I'm guessing that's what this is building on, and that the '$\approx d$' sample size is more to be interpreted in big-$O$-like notation. The $\sqrt d$ after that is $n\gg \sqrt d$ in the paper as well. Commented Dec 4, 2023 at 20:28
• @Mohan the quote in the video doesn't say distinguish with certainty. It says, "If you want to confidently distinguish between these biases, you need around $d$ measurements". I didn't understand why exactly, nor how to do it for a general case of $p_1$ and $p_2$ (where both are known). Commented Dec 4, 2023 at 22:07
• I don’t know how this can be done rationally without positing a prior distribution for Pr(heads) and a zone of equivalence. Pr(heads) will never be 0.5 exactly, so a Bayesian posterior probability that Pr(heads) is outside of for example [0.49, 0.51] would provide evidence for consequential bias. Commented Dec 7, 2023 at 13:18

As @PBulls points out in a comment, this quote from the video is probably a very informal summary of some probabilistic bound on $$|\hat p - p|$$.

One simple example of how to approach this is to use Chebyshev's inequality.
(But I haven't watched the full video; nor the one before it, mentioned in the comments; so I apologize if this doesn't match the video's context exactly.)

You say that you are only considering the two options $$p_1$$ and $$p_2$$.
Once you use a sample to estimate $$\hat p$$, you'll probably want to pick the $$p_i$$ closest to your $$\hat p$$.
But the sample could mislead you. Maybe $$p_1$$ is true, but you get an unlucky sample whose $$\hat p$$ is closer to $$p_2$$ just due to sampling variation. This is less likely to happen for larger $$n$$.

From a Frequentist perspective, you might wonder: Before collecting data, how large should I choose $$n$$ to be, to minimize the risk of something like this?

Let's say you choose $$n$$ large enough to ensure that $$|\hat p - p| < |p_1 - p_2|/2$$ will happen with some high probability $$1-\epsilon$$. Then you only have at most probability $$\epsilon$$ of getting a sample in which $$\hat p$$ is closer to the wrong $$p_i$$ than to the correct $$p_i$$.

To do this, you need to write

$$P(|\hat p - p| \geq |p_1-p_2|/2) \leq \epsilon$$

in terms of $$n$$, and choose $$n$$ large enough. One way to do this is to rewrite it to line up with Chebyshev's inequality:

$$P(|\hat p - p| \geq k \sqrt{Var(\hat p)}) \leq 1/k^2$$

where $$Var(\hat p) = p(1-p)/n$$ for the binomial "biased coin flip" setup you describe, and $$k$$ is up to you.

If you are specifically interested in $$p_1=1/d$$ and $$p_2=2/d$$, plug everything into Chebyshev and choose appropriate $$k$$ to get

$$P(|\hat p - p| \geq 1/(2d)) \leq c (d-1)/n$$

(where the constant $$c$$ just depends on which $$p_i$$ you plugged in for $$p$$). When you set $$\epsilon = c (d-1)/n$$, you conclude that $$n$$ basically needs to be a constant multiple of $$d$$ to ensure a fixed $$\epsilon$$.

In other words, the video probably doesn't mean that you can literally use $$n=d$$. It just means that $$n$$ and $$d$$ can be on the same order of magnitude. You don't need $$n$$ to be polynomial or exponential or some other fast-growing function of $$d$$.

• To add a few other quotes from the videos: their claim only really works for quite large $d$ (>100 is used, their 'rigged' example in the prior video clearly breaks down if you use $d=2$) and make statements like $\approx d$ being "proportional to $d$, for example $50*d$ or $100*d$" (where I would argue that the latter is actually $d^2$ for $d=100$). Anyway, I very much agree with your closing paragraph. Commented Dec 7, 2023 at 14:32