Reference for the number of samples needed to distinguish two probability distributions

Question

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.

Answer 1

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)>\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]

Answer 2

Edit I misinterpreted the problem! See Clement's answer instead.

I don't know the context of this paper (not having read it), so I'm not going to address the paper at all, but I can talk about sampling from classical probability distributions which seems to be the question.

In that context, the statement you give is only true fixing the support size of the distribution. The more precise statement was shown in [1], see also [2]. The right bound is $O\left(\max\left\{\frac{n^{2/3}}{\epsilon^{4/3}}, \frac{n^{1/2}}{\epsilon^2}\right\}\right)$ samples suffice when support size is $n$. If you fix $n$, then this is $O(1/\epsilon^2)$ as $\epsilon \to 0$ (as the second term in the max is larger). I think for a proof you have to see those papers, maybe my comments below are also helpful.

If the question is just to tell whether a distribution is uniform or far from uniform, which sounds relevant for the paper you mentioned, then the complexity of this is simply $O\left(\frac{n^{1/2}}{\epsilon^2}\right)$ whose upper bound goes back I'm not sure how far -- it is the idea of birthday paradox -- and whose lower bound was shown by [3].

To show the $\sqrt{n}/\epsilon^2$ upper bound (which is $O(1/\epsilon^2)$ if support size is fixed) is pretty easy: Draw $O(\sqrt{n}/\epsilon^2)$ samples and check the number of collisions. It will be much higher than expected if the distribution is nonuniform. I think you can find something like this in these lecture notes[4], which also mentions the distinguishing-two-distributions problem where similar ideas can be used. (I also have the uniformity-testing case written up in a paper I could reference if wanted.)

To get an idea of a counterexample when support size is not fixed, suppose $\epsilon < 0.5$ and imagine a distribution on support size $n$ where each probability $p_i = \frac{1}{n}\left(1 \pm 2\epsilon\right)$, where say a random half of the coordinates get probability $\frac{1}{n}\left(1 + 2\epsilon\right)$ and the other half get the lower probability. The total variation distance between such a distribution and the uniform distribution is $\epsilon$. But imagine trying to tell whether you have this or the uniform distribution. You can learn nothing if every sample you draw is unique -- you need a "birthday collision". But the chance of a birthday collision gets smaller and smaller as $n$ grows. This construction was used by Paninski to prove the lower bound in [3].

[1] "Optimal Algorithms for Testing Closeness of Discrete Distributions" by Chan, Diakonikolas, G. Valiant, and P. Valiant, 2013. https://arxiv.org/abs/1308.3946

[2] "A New Approach for Testing Properties of Discrete Distributions" by Diakonikolas and Kane, 2016. https://arxiv.org/abs/1601.05557

[3] "A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data", Paninski, 2008. http://neurotheory.columbia.edu/pdfs/Paninski_2008.pdf

[4] http://www.wisdom.weizmann.ac.il/~oded/PDF/pt-dist.pdf