1
$\begingroup$

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, \begin{equation} d_{\text{TV}}(D, U) \geq \frac{2}{3}. \end{equation}

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$?

$\endgroup$
1
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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]$? $\endgroup$ – BlackHat18 Nov 22 at 13:49
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Nov 22 at 13:50
  • $\begingroup$ Even given $V$, the size of $S$ is still random, since it depends on the sample. $\endgroup$ – Yuval Filmus Nov 22 at 14:03
  • $\begingroup$ If $V$ is given, the size of $S$ is $m$, right? Which is fixed? $\endgroup$ – BlackHat18 Nov 22 at 14:08
  • 1
    $\begingroup$ You can sample the same element twice. $\endgroup$ – Yuval Filmus Nov 22 at 14:12

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.