# Learning a coin's bias (localized)

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.

• 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 Aug 28 '17 at 14:28
• Also, note that for $p=\eta$, for instance, then the right sample complexity is linear in $1/\varepsilon$, not quadratic. – Clement C. Aug 28 '17 at 15:05

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))$.
• What about the dependence on $\eta$? When the latter shrinks to $0$, so should the sample complexity. – Aryeh Aug 28 '17 at 11:50
• 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. Aug 28 '17 at 15:03
• Indeed If $\eta \le \epsilon$ the complexity is zero, otherwise $\eta$ does not matter. – Yuval Peres Aug 29 '17 at 9:23
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)$).