Reference for the number of samples needed to distinguish two probability distributions I am looking for a reference (and/or a full proof) for this statement:


  $O(1/\epsilon^2)$ samples suffice to distinguish any two probability
  distributions with variation distance $\epsilon$.


I would be very grateful for any pointers.
So here, you only have two options: either your samples come from $p$, or from $q$ (and you know explicitly both).

By definition of the statistical/total variation distance, we have
$$
d_{TV}(p,q) = \sup_S( p(S)-q(S))
$$
where the supremum is taken over all measurable sets $S$. I haven't looked at the paper, but assuming all is nice (finite), the $\sup$ is a $\max$ and achieved for some particular set $S^\ast$, that you can compute given $p,q$.

So at this point, you have an explicit set $S^\ast$, the values $p(S^\ast)$, $q(S^\ast)$ which by definition satisfy
$$
p(S^\ast) = q(S^\ast) + \varepsilon
$$
and you know that the unknown distribution $h$ is either $p$ or $q$. So to distinguish between the two cases, it suffices to estimate $h(S^\ast)$ up to an additive $\frac{\varepsilon}{2}$, which can be done straightforwardly with $O(1/\varepsilon^2)$ samples.



Side remark: this can be improved a little if both $p(S^\ast), q(S^\ast)$ are both $O(\varepsilon)$ themselves. In which case, distinguishing between the two cases only requires $O(1/\varepsilon)$ samples. (The "hard case" basically is to distinguish $1/2$ from $1/2+\varepsilon$, which requires $\Omega(1/\varepsilon^2)$ samples.)



Second remark: usul refers,in his answer, to a harder problem, composite hypothesis testing. In this problem, you only have one distribution $p$, and want to distinguish between (i) $h=p$ and (ii) $d_{TV}(h,p)&gt;\varepsilon$ (that is, the second option is not a singleton $\{q\}$, but the much larger set of all distributions that are $\varepsilon$-far from $p$). In this case, you need a lot more samples: as a function of the (explicitly known) $p$, this will be basically* $\lVert p^{-\max}_{-\Theta(\varepsilon)}\rVert _{2/3}/\varepsilon^2$ (see [VV14]), where $\lVert p^{-\max}_{-\Theta(\varepsilon)}\rVert _{2/3}$ is a functional of the distribution $p$ (equal to $\Theta(\sqrt{n})$, for instance, when $p$ is the uniform distribution on a set of $n$ elements). See also [BCG16] for an alternative, also tight* characterization of this quantity in terms of another functional.

$*$ The two characterizations are tight in most cases, except some pathological/strange ones.



[VV14]  G. Valiant and P. Valiant. An automatic inequality prover and instance optimal identity testing. In Proceedings of FOCS, 2014. [full version]

[BCG16] E. Blais, C. Canonne, and T. Gur. Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)
Manuscript, 2016. [ECCC TR16-168]