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?


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


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.


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.