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? 



Lower bound on number of samples for an epsilon delta approximation matching the Chernoff bound
**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>


