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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ 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))$. $\endgroup$– usulCommented Aug 28, 2017 at 14:28
-
$\begingroup$ Also, note that for $p=\eta$, for instance, then the right sample complexity is linear in $1/\varepsilon$, not quadratic. $\endgroup$– Clement C.Commented Aug 28, 2017 at 15:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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))$.
-
$\begingroup$ What about the dependence on $\eta$? When the latter shrinks to $0$, so should the sample complexity. $\endgroup$– AryehCommented Aug 28, 2017 at 11:50
-
1$\begingroup$ 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.). $\endgroup$ Commented Aug 28, 2017 at 15:03
-
$\begingroup$ Indeed If $\eta \le \epsilon$ the complexity is zero, otherwise $\eta$ does not matter. $\endgroup$ Commented Aug 29, 2017 at 9:23
$\begingroup$
$\endgroup$
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)$).
