13
$\begingroup$

It is well known that the complexity of distinguishing an $\epsilon$ biased coin from a fair one is $\theta(\epsilon^{-2})$. Are there results for distinguishing a $p$ coin from a $p+\epsilon$ coin? I can see that for the special case of $p=0$, the complexity will be $\epsilon^{-1}$. I have a hunch that the complexity will depend on whether $p$ is of the order of $\epsilon$, but can't prove so rigorously. Any hints/references?

$\endgroup$
15
$\begingroup$

I suggest you use the framework found in the following paper:

How Far Can We Go Beyond Linear Cryptanalysis?, Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.

The crucial result says that you need $n \sim 1/D(D_0 \,||\, D_1)$, where $D(D_0 \,||\, D_1)$ is the Kullback-Leibler distance between the two distributions $D_0$ and $D_1$. Expanding out the definition of the K-L distance, we see that in your case

$$D(D_0 \,||\, D_1) = p \log \frac{p}{p+\epsilon} + (1-p) \log \frac{1-p}{1-p-\epsilon},$$

with the convention that $0 \log \frac0p = 0$.

When $p \gg \epsilon$, we find $D(D_0 \,||\, D_1) \approx \epsilon^2/(p(1-p))$. Thus, when $p \gg \epsilon$, we find that you need $n \sim p(1-p)/\epsilon^2$ coin flips. When $p = 0$, we find $D(D_0 \,||\, D_1) = -\log(1-\epsilon) \approx \epsilon$, so you need $n \sim 1/\epsilon$ coin flips. Thus, this formula is consistent with the special cases you already know about... but it generalizes to all $n,\epsilon$.

For justification, see the paper.


When $p \gg \epsilon$, the justification is easy to work through by hand. With $n$ observations, the number of heads is either $\text{Binomial}(n,p)$ or $\text{Binomial}(n,p+\epsilon)$, so you want to find the smallest $n$ such that these two distributions can be distinguished.

You can approximate both of these by a Gaussian with the right mean and variance, and then use standard results on the difficulty of distinguishing two Gaussians, and the answer should fall out. The approximation is fine if $p \ge 5/n$ or so.

In particular, this comes down to distinguishing $\mathcal{N}(\mu_0,\sigma_0^2)$ from $\mathcal{N}(\mu_1,\sigma_1^2)$ where $\mu_0 = pn$, $\mu_1 = p+\epsilon)n$, $\sigma_0^2 = p(1-p)n$, $\sigma_1^2 = (p+\epsilon)(1-p-\epsilon)n$. You'll find that the probability of error in the optimal distinguisher is $\text{erfc}(z)$ where $z = (\mu_1-\mu_0)/(\sigma_0+\sigma_1) \approx \epsilon \sqrt{n / 2p(1-p)}$. Thus, we need $z \sim 1$ to distinguish with constant success probability. This amounts to the condition that $n \sim 2p(1-p)/\epsilon^2$ (up to a constant factor)... when $p \gg \epsilon$.

For the general case... see the paper.

$\endgroup$

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.