6
$\begingroup$

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$.
$\endgroup$
5
  • 4
    $\begingroup$ The result quoted can't possibly be right. However many tosses there are, you can't obtain certainty. $\endgroup$
    – Mohan
    Commented Dec 4, 2023 at 18:26
  • 1
    $\begingroup$ So $p_1$ and $p_2$ are known? $\endgroup$ Commented Dec 4, 2023 at 18:55
  • $\begingroup$ 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. $\endgroup$
    – PBulls
    Commented Dec 4, 2023 at 20:28
  • $\begingroup$ @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). $\endgroup$ Commented Dec 4, 2023 at 22:07
  • $\begingroup$ 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. $\endgroup$ Commented Dec 7, 2023 at 13:18

1 Answer 1

5
+50
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – PBulls
    Commented Dec 7, 2023 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.