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.
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))$.