<p>I suggest you use the framework found in the following paper:</p>

<p><a href="http://infoscience.epfl.ch/record/88161?ln=en">How Far Can We Go Beyond Linear Cryptanalysis?</a>, Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.</p>

<p>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</p>

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

<p>with the convention that $0 \log \frac0p = 0$.</p>

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

<p>For justification, see the paper.</p>

<hr>

<p>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.</p>

<p>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.</p>

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

<p>For the general case... see the paper.</p>

CC BY-SA 3.0
2014-04-29T01:56:33.863Z
2014-04-29T04:24:00.380Z
2014-04-29T04:24:00.380Z
D.W.
<p>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?</p>

<reference-request><time-complexity>
Distinguishing between two coins
elexhobby
# Distinguishing between two coins

(Asked by: username_0 on 2014-04-28)

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?

**Tags:** reference-request, time-complexity

---

## 1 answers

### Answer by username_1 on 2014-04-29. Score: 15 | Accepted answer

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

[How Far Can We Go Beyond Linear Cryptanalysis?](http://infoscience.epfl.ch/record/88161?ln=en), 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.


---

