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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
