3
$\begingroup$

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.

$\endgroup$
  • 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$ – usul Aug 28 '17 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. Aug 28 '17 at 15:05
5
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.