Optimal algorithm to distinguish given black box access

This is a variant of this question. Consider two probability distributions $$D$$ and $$U$$, over $$n$$-bit strings, where $$U$$ is the uniform distribution. Assume that $$D$$ and $$U$$ are far apart in total variation distance, ie, $$$$d_{\text{TV}}(D, U) \geq \frac{2}{3}.$$$$

We are not given an explicit description of $$D$$: we are only given black-box access, ie, we are only given a sampling device that can sample from $$D$$. Consider a sample $$z \in \{0, 1\}^{n}$$, taken from either $$D$$ or $$U$$. We want to know which one is the case and to do that, we consider polynomial-time algorithms that use the sampling device. I am looking for a single optimal deterministic algorithm that works optimally for all $$D$$.

Let $$A$$ be this optimal algorithm. For each $$D$$, our algorithm $$A$$ is optimal in the sense that

$$\Pr_{z \sim D} [A(z) = 1] \geq \frac{3}{4}, \\ \Pr_{z \sim U} [A(z) = 0] \geq \frac{3}{4},$$

Output $$1$$ is interpreted as "the sample comes from $$D$$, and output $$0$$ is interpreted as "the sample comes from $$U$$."

Let $$A$$ use the black-box sampling device a polynomial number of times (at most) and get samples $$z_{1}, z_{2}, \ldots, z_{k}$$ from $$D$$, for some polynomial $$k$$. My intuition is that, if this best algorithm decides that $$z$$ indeed came from $$D$$, then it must be true that $$z_{i} = z$$ for at least one $$i \in [k]$$. In other words, since we know nothing about $$D$$ or its support, we have to "see" $$z$$ at least once in the samples we collect from $$D$$ to ascertain that $$z$$ indeed came from $$D$$. How do I mathematically formalize this statement?

Also, does this same intuition hold if we are given a polynomial number of samples as input (taken from either $$D$$ or $$U$$) instead of just one and are also given access to a black-box sampler for $$D$$?

You need $$\Omega(2^n)$$ samples in order to accomplish your task.

Consider an algorithm that gets $$m$$ samples from $$D$$ and then another sample, either from $$D$$ or from $$U$$, and has to guess which it is. Its input thus consists of $$m+1$$ samples $$X_1,\ldots,X_m,Y$$.

We will generate the distribution $$D$$ at random by choosing a random set $$V \subseteq \{0,1\}^n$$ of size $$2^{n-2}$$ and letting $$D$$ be a uniform sample from $$V$$. Note that $$d_{\mathrm{TV}}(D,U) = 3/4$$.

Consider now the following two distributions:

• Distribution $$\mathcal{D}$$: Choose $$D$$ at random as above. Generate $$m+1$$ samples from $$D$$.
• Distribution $$\mathcal{U}$$: Choose $$D$$ at random as above. Generate $$m$$ samples from $$D$$ and one sample from $$U$$.

Let $$S$$ be the set of vectors appearing in the first $$m$$ samples. We can describe the distribution of the final sample as follows:

• Distribution $$\mathcal{D}$$: With probability $$|S|/2^{n-2}$$, output a random element in $$S$$ (each one is output with probability $$1/2^{n-2}$$). Otherwise, output a random element not in $$S$$.
• Distribution $$\mathcal{U}$$: Output a random element.

To see where the alternative description of $$\mathcal{D}$$ comes from, notice that given $$S$$, the conditional distribution of $$V$$ is a random set of size $$2^{n-2}$$ containing $$S$$. When sampling a random element from $$V$$, we have a probability of $$|S|/2^{n-2}$$ to choose one of the elements from $$S$$, with probability $$1/2^{n-2}$$ each. Otherwise, we choose an element from $$V \setminus S$$, which given the distribution of $$V$$, is just a random element not in $$S$$.

This shows that the TV distance between the two distributions is $$\mathbb{E}\left[|S|(1/2^{n-2} - 1/2^n)\right] < \frac{m}{2^{n-2}}.$$ In particular, any algorithm whatsoever will behave almost the same in both cases unless $$m = \Omega(2^n)$$. Indeed, your algorithm $$A$$ satisfies $$\Pr_{\mathcal{D}}[A=1] - \Pr_{\mathcal{U}}[A=1] \geq \frac{3}{4} - \frac{1}{4} = \frac{1}{2},$$ showing that the variation distance between $$\mathcal{D}$$ and $$\mathcal{U}$$ is at least $$1/2$$. This is only possible if $$m/2^{n-2} \geq 1/2$$, that is, if $$m \geq 2^{n-3}$$.

• Why is the TV $\mathbb{E}\left[|S|(1/2^{n-2} - 1/2^n)\right]$? As in, why the expectation and what is the expectation over? Shouldn't the TV just be $\frac{1}{2}\left[|S|(1/2^{n-2} - 1/2^n)\right]$? – BlackHat18 Nov 22 '20 at 13:49
• You might or might not need the $1/2$ factor – it makes little difference anyway. As for the expectation, it is needed since $|S|$ depends on the random variable $V$. – Yuval Filmus Nov 22 '20 at 13:50
• Even given $V$, the size of $S$ is still random, since it depends on the sample. – Yuval Filmus Nov 22 '20 at 14:03
• If $V$ is given, the size of $S$ is $m$, right? Which is fixed? – BlackHat18 Nov 22 '20 at 14:08
• You can sample the same element twice. – Yuval Filmus Nov 22 '20 at 14:12