Lower bound on number of samples for an epsilon delta approximation matching the Chernoff bound

Question

So we have two biased coins, one comes out head w.p. $1/2+\epsilon$ and the other w.p. $1/2-\epsilon$. How many times should we flip these two coins to be able to tell them apart w.p. at least $\delta$? Using the Chernoff bound we know that $\frac{1}{\epsilon^2}\log(1/\delta)$ is enough. And I know that this is also a lower bound but I cannot prove it. By doing coupling I can only show that the lower bound is $\frac{1}{\epsilon}\log(1/\delta)$. Does anybody know the proof?

Answer 1

This argument based on modification of [2].

(1) Let A be the event that $\frac{1}{n}\sum_{i=1}^{n}X_{i}\geq\frac{1}{2}$ , let $X_{i}=0$ mean heads of coin and $X_{i}=1$ mean tails.

$Pr(A)\leq Pr\left\{ \left|\frac{1}{n}\sum_{i=1}^{n}X_{i}-\left(\frac{1}{2}-\epsilon\right)\right|\geq\epsilon\right\} $

But $E(X_{i})=\left(\frac{1}{2}+\epsilon\right)\cdot0+\left(\frac{1}{2}-\epsilon\right)\cdot1=\left(\frac{1}{2}-\epsilon\right)$ and from Chernoff bound we know that

$Pr\left\{ \left|\frac{1}{n}\sum_{i=1}^{n}X_{i}-\left(\frac{1}{2}-\epsilon\right)\right|\geq\epsilon\right\} =Pr\left\{ \left|\frac{1}{n}\sum_{i=1}^{n}X_{i}-E(X_{i})\right|\geq\epsilon\right\} \leq2\exp\left(-\frac{2\cdot\epsilon^{2}}{n}\right)$

If we plug in and solve $\delta\leq P(A)\leq2\exp\left(-\frac{2\cdot\epsilon^{2}}{n}\right)$, then $n\ge\frac{1}{\epsilon^{2}}log(\frac{1}{\delta})$.

(2) Let B be the event that $\left|\frac{1}{n}\sum_{i=1}^{n}X_{i}-\left(\frac{1}{2}-\epsilon\right)\right|\geq0$

$Pr(B)=2Pr\left\{ \frac{1}{n}\sum_{i=1}^{n}X_{i}-\left(\frac{1}{2}-\epsilon\right)\geq0\right\}$ due to symmetry of head-tail probabilities.

By classical result like Theorem 2.1 in [1], since $p=\left(\frac{1}{2}-\epsilon\right)\leq\frac{1}{2}$ now we conclude that $Pr\left\{ \frac{1}{n}\sum_{i=1}^{n}X_{i}-\left(\frac{1}{2}-\epsilon\right)\geq\epsilon\right\} \geq Pr\left\{ Z\geq\frac{n\epsilon}{\sqrt{n\left(\frac{1}{2}+\epsilon\right)\left(\frac{1}{2}-\epsilon\right)}}\right\} $ And we can yield an upper tail control $\frac{1}{2}exp\left(-\frac{\epsilon^{2}}{3n}\right)$ on standard normal $Pr\left(Z\geq z\right)=1-\Phi(z)\sim O(1-\sqrt{1-exp(-z^{2})})$, like [2] Theorem 2. We solve the inequality $\delta\geq\frac{1}{2}exp\left(-\frac{\epsilon^{2}}{3n}\right)$ to yield that the upper bound on $n$.

If you just want a counterexample to show the bound is tight, then try $[n/2]+1$ heads and $[n/2]$ tails.

[1]Slud, Eric V. "Distribution inequalities for the binomial law." The Annals of Probability (1977): 404-412.

[2]Mousavi, Nima. "How tight is Chernoff bound." (2010). https://ece.uwaterloo.ca/~nmousavi/Papers/Chernoff-Tightness.pdf

Answer 2

In this paper with Iosif Pinelis, we give the exact constants for the lower bound (whose dependence on $\epsilon$ is $\frac1{\epsilon^2}$): https://arxiv.org/abs/1606.08920

Actually, our result is stronger since the bound holds for any estimator -- not just the natural one you get by counting the outcomes and normalizing by the number of flips.