<p>Write $p=p_0=1-q$. We may assume that $\epsilon&lt;\eta \le p\le 1/2$. Then the sample complexity is of order $\log(1/\delta)$ times the reciprocal of the relative entropy  $D((p,q)||(p+\epsilon,q-\epsilon))$. 
This yields sample complexity  $\Theta(p\epsilon^{-2}\log(1/\delta))$.</p>

CC BY-SA 3.0
2017-08-28T11:50:04.210Z
What about the dependence on $\eta$? When the latter shrinks to $0$, so should the sample complexity.
Aryeh
CC BY-SA 3.0
2017-08-28T15:03:25.287Z
Well, if $\eta < \varepsilon/2$, the sample complexity is $0$. otherwise, still the same (since that's as hard as deciding $p_0-\eta$ vs. $p_0-\eta+\varepsilon$, which is captured by the above.).
Clement C.
CC BY-SA 3.0
2017-08-29T09:23:48.840Z
Indeed If $\eta \le \epsilon$ the complexity is zero, otherwise $\eta$ does not matter.
Yuval Peres
CC BY-SA 3.0
2017-08-28T11:47:13.050Z
2017-08-28T11:47:13.050Z
Yuval Peres
<p>Yuval Peres gave the answer in terms of the Kullback-Leibler divergence. Another way is to recall that the sample complexity will be captured by the inverse of the squared Hellinger distance between the two coins.</p>

<p>Now, letting $D_p$ and $D_{p+\varepsilon}$ be the distributions of a Bernoulli random variable with parameter $p$ and $p+\varepsilon$ respectively,
$$\begin{align}
d_H(D_p,D_{p+\varepsilon})^2 &amp;= \frac{1}{2}\lVert D_p-D_{p+\varepsilon}\rVert^2_2 = \frac{1}{{2}}\left((\sqrt{p}-\sqrt{p+\varepsilon})^2+(\sqrt{1-p}-\sqrt{1-p-\varepsilon})^2\right) \\
&amp;= \frac{1}{2}\left({p(1-\sqrt{1+\varepsilon/p})^2+(1-p)(\sqrt{1}-\sqrt{1-\varepsilon/(1-p)})^2}\right) 
\end{align}$$
Assuming wlog $p\leq 1/2$, we can see easily by a Taylor expansion that this is
$$\begin{align}
d_H(D_p,D_{p+\varepsilon})^2 &amp;= \Theta\left(\frac{\varepsilon^2}{p}\right) 
\end{align}$$
leading to the same answer as Yuval Peres' (from a different method).</p>

<p>Interestingly, this also shows the usual observation, that the quadratic relation between TV and Hellinger distance can matter a lot: for $p=1/2$, the bound $1/TV$ (i.e., $\Omega(1/\varepsilon^2)$ here) is tight; but for $p=O(\varepsilon)$, then it is quadratically worse than the optimal, which is $1/d_H^2$ (that is, $\Omega(1/\varepsilon)$).</p>

CC BY-SA 3.0
2017-08-28T15:16:07.613Z
2017-08-28T15:28:48.877Z
2017-08-28T15:28:48.877Z
Clement C.
<p>It's well known that the minimax sample complexity for estimating the bias $p$ of a coin to additive error $\epsilon$ with confidence $\delta$ is 
$\Theta(\epsilon^{-2}\log(1/\delta))$. What if we know that $p$ lies in some specified range, say $[p_0-\eta,p_0+\eta]$ -- is the minimax sample complexity known in terms of $p_0$ and $\eta$? Note that $p_0=\eta=1/2$ recovers the general setting as a special case.</p>

CC BY-SA 3.0
2017-08-28T14:28:43.917Z
The number of samples needed to decide whether $p = \frac{1}{2} + \epsilon$ or $p = \frac{1}{2} - \epsilon$ is still $\Theta(\epsilon^{-2} \log(1/\delta))$.
usul
CC BY-SA 3.0
2017-08-28T15:05:00.127Z
Also, note that for $p=\eta$, for instance, then the right sample complexity is linear in $1/\varepsilon$, not quadratic.
Clement C.
<machine-learning><lg.learning><st.statistics>
Learning a coin's bias (localized)
Aryeh
# Learning a coin's bias (localized)

(Asked by: username_0 on 2017-08-28)

It's well known that the minimax sample complexity for estimating the bias $p$ of a coin to additive error $\epsilon$ with confidence $\delta$ is
$\Theta(\epsilon^{-2}\log(1/\delta))$. What if we know that $p$ lies in some specified range, say $[p\_0-\eta,p\_0+\eta]$ -- is the minimax sample complexity known in terms of $p\_0$ and $\eta$? Note that $p\_0=\eta=1/2$ recovers the general setting as a special case.

**Tags:** machine-learning, lg.learning, st.statistics
> **Comments:**
> **username_1**: The number of samples needed to decide whether $p = \frac{1}{2} + \epsilon$ or $p = \frac{1}{2} - \epsilon$ is still $\Theta(\epsilon^{-2} \log(1/\delta))$.  
> **username_2**: Also, note that for $p=\eta$, for instance, then the right sample complexity is linear in $1/\varepsilon$, not quadratic.  

---

## 2 answers

### Answer by username_3 on 2017-08-28. Score: 6 | Accepted answer

Write $p=p\_0=1-q$. We may assume that $\epsilon<\eta \le p\le 1/2$. Then the sample complexity is of order $\log(1/\delta)$ times the reciprocal of the relative entropy $D((p,q)||(p+\epsilon,q-\epsilon))$.
This yields sample complexity $\Theta(p\epsilon^{-2}\log(1/\delta))$.

> **Comments:**
> **username_0**: What about the dependence on $\eta$? When the latter shrinks to $0$, so should the sample complexity.  
> **username_2**: Well, if $\eta < \varepsilon/2$, the sample complexity is $0$. otherwise, still the same (since that's as hard as deciding $p_0-\eta$ vs. $p_0-\eta+\varepsilon$, which is captured by the above.).  
> **username_3**: Indeed If $\eta \le \epsilon$ the complexity is zero, otherwise $\eta$ does not matter.  

---

### Answer by username_2 on 2017-08-28. Score: 5

Yuval Peres gave the answer in terms of the Kullback-Leibler divergence. Another way is to recall that the sample complexity will be captured by the inverse of the squared Hellinger distance between the two coins.

Now, letting $D\_p$ and $D\_{p+\varepsilon}$ be the distributions of a Bernoulli random variable with parameter $p$ and $p+\varepsilon$ respectively,
$$\begin{align}
d\_H(D\_p,D\_{p+\varepsilon})^2 &= \frac{1}{2}\lVert D\_p-D\_{p+\varepsilon}\rVert^2\_2 = \frac{1}{{2}}\left((\sqrt{p}-\sqrt{p+\varepsilon})^2+(\sqrt{1-p}-\sqrt{1-p-\varepsilon})^2\right) \\
&= \frac{1}{2}\left({p(1-\sqrt{1+\varepsilon/p})^2+(1-p)(\sqrt{1}-\sqrt{1-\varepsilon/(1-p)})^2}\right)
\end{align}$$
Assuming wlog $p\leq 1/2$, we can see easily by a Taylor expansion that this is
$$\begin{align}
d\_H(D\_p,D\_{p+\varepsilon})^2 &= \Theta\left(\frac{\varepsilon^2}{p}\right)
\end{align}$$
leading to the same answer as Yuval Peres' (from a different method).

Interestingly, this also shows the usual observation, that the quadratic relation between TV and Hellinger distance can matter a lot: for $p=1/2$, the bound $1/TV$ (i.e., $\Omega(1/\varepsilon^2)$ here) is tight; but for $p=O(\varepsilon)$, then it is quadratically worse than the optimal, which is $1/d\_H^2$ (that is, $\Omega(1/\varepsilon)$).


---

