1
$\begingroup$

Consider (over $n$-bit strings) the uniform distribution $U$, and another distribution $D$ such that \begin{equation} \text{Distance}(D, U) \geq \frac{1}{e}, \end{equation} where $\text{Distance}$ stands for the total variation distance, given by \begin{equation} \text{Distance}(D, U) = \sum_{z \in \{0, 1\}^{n}} \left|\underset{\text{Z} \sim D}{\text{Pr}}[\text{Z}=z] - \underset{\text{Z} \sim U}{\text{Pr}}[\text{Z}=z]\right|, \end{equation} for a random variable $\text{Z}$. In other words, $D$ and $U$ are quite far from each other. Even then, it seems intuitively true to me that we should not be able to distinguish between these two distributions with a polynomial-time algorithm if we are given one (and just one) sample as input, with the promise that the sample comes from one of these two distributions.

By this, I mean that it seems intuitive to me the quantity \begin{equation} \left|\underset{x \sim D}{\text{Pr}}[A(x) =1] - \underset{x \sim U}{\text{Pr}}[A(x) =1]\right| \end{equation} is small, for a polynomial time algorithm $A$.

Is my intuition correct? If not, it just doesn't seem obvious to me how we could distinguish these distributions with just one sample. Isn't it too little information? Can you show how we are to distinguish by any explicit description of such an algorithm for any such $D$?

$\endgroup$
6
  • $\begingroup$ The first step would be to formally define "to be able to distinguish between two distributions given one sample". $\endgroup$ – Yuval Filmus Nov 14 '20 at 16:18
  • 1
    $\begingroup$ By definition, the variation distance between two distributions is the amount by which the best distinguisher can distinguish between them, in a certain sense. In that sense, and ignoring complexity issues, variation distance does capture distinguishability. But you might have a difference sense in mind. $\endgroup$ – Yuval Filmus Nov 14 '20 at 16:20
  • $\begingroup$ I modified the question. $\endgroup$ – BlackHat18 Nov 14 '20 at 16:59
  • $\begingroup$ Are you aware of the equivalent definition of variation distance, as the maximum over $|\Pr_{x \sim D}[A(x)=1] - \Pr_{x \sim U}[A(x)=1]|$ over all algorithms $A$? It agrees with your definition up to a multiplicative factor of 2. $\endgroup$ – Yuval Filmus Nov 14 '20 at 17:07
  • 1
    $\begingroup$ The optimal algorithm $A$ outputs $1$ if $\Pr[D(x)] \geq \Pr[U(x)]$, and $0$ otherwise. $\endgroup$ – Yuval Filmus Nov 14 '20 at 17:08
1
$\begingroup$

Total variation distance, which is exactly half of your notion of distance, is equal to $$ d_{TV}(D,U) = \frac{1}{2} \operatorname{Distance}(D,U) = \max_A \bigl|\Pr_{x \sim D}[A(x)] - \Pr_{x \sim U}[A(x)] \bigr|. $$ You can take $A$ to be the indicator of $\Pr[D(x)] \geq \Pr[U(x)]$. The event $A$ might be hard to compute, but it could also be easy to compute. In the latter case, you will be able to efficiently distinguish between $D$ and $U$, even using only one sample. This may even be possible in the former case, though with an advantage less than the total variation distance.


Here is a proof of the equivalence between the two formulations.

Since $$ \Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] = -\left(\Pr_{x \sim D} [\overline{A(x)}] - \Pr_{x \sim U}[\overline{A(x)}]\right), $$ where the overline represents negation, we have $$ \delta_{TV}(D,U) = \max_A \bigl( \Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] \bigr). $$ Let $S = \{ x : A(x) \}$. Then $$ \Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] = \sum_{z \in S} \bigl(\Pr_{Z \sim D}[Z = z] - \Pr_{Z \sim U}[Z = z]\bigr). $$ This formula makes it clear that an optimal choice for $S$ is $$ S = \{ z : \Pr_{Z \sim D}[Z = z] \geq \Pr_{Z \sim U}[Z = z] \}. $$ For this choice of $S$, we have \begin{align} d_{TV}(D,U) &= \Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] \\ &= \Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] \\ &= \bigl(1-\Pr_{x \sim D}[x \notin S]\bigr) - \bigl(1-\Pr_{x \sim U}[x \notin S]\bigr) \\ &= \Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S]. \end{align} By definition of $S$, we have \begin{align} \Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] &= \sum_{z \in S} \Pr_{Z \sim D}[Z = z] - \sum_{z \in S} \Pr_{Z \sim U}[Z = z] \\ &= \sum_{z \in S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr|. \end{align} Similarly, we have $$ \Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S] = \sum_{z \notin S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr|. $$ It follows that \begin{align} \mathrm{Distance}(D,U) &= \sum_{z \in S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr| + \sum_{z \notin S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr| \\ &= \Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] + \Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S] \\ &= 2\bigl(\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)]\bigr) \\ &= 2d_{TV}(D,U). \end{align}

$\endgroup$
12
  • $\begingroup$ Though it isn't too important, when I'm deriving, I get $d_{TV}(D,U) = \frac{1}{2} \operatorname{Distance}(D,U) = \frac{1}{2} \max_A \bigl|\Pr_{x \sim D}[A(x)] - \Pr_{x \sim U}[A(x)] \bigr|$. I'm just using the law of total probability and the triangle inequality. How do you get rid of the $\frac{1}{2}$? $\endgroup$ – BlackHat18 Nov 14 '20 at 17:36
  • $\begingroup$ Let $Z = \{ x : D(x) \geq U(x) \}$ and let $W = \{ x : D(x) < U(x) \}$. The point is that $\sum_{x \in Z} [D(x) - U(x)] = \sum_{x \in W} [U(x) - D(x)]$. $\endgroup$ – Yuval Filmus Nov 14 '20 at 17:44
  • $\begingroup$ That's a nice observation, but I can't figure out how it helps. Here is what I am doing: $\bigl|\Pr_{x \sim D}[A(x)] - \Pr_{x \sim U}[A(x)] \bigr| \leq \sum_{x} \bigl| \Pr[A(x)][D(x) - U(x)]\bigr| \leq \sum_{x} \bigl| D(x) - U(x) \bigr| = \text{Distance}(D, U)$. $\endgroup$ – BlackHat18 Nov 14 '20 at 18:05
  • $\begingroup$ Try using this observation to gain a factor of 2. $\endgroup$ – Yuval Filmus Nov 14 '20 at 18:07
  • 1
    $\begingroup$ You can remove the modulus sign. Given a solution in which the first summand is smaller than the second, you can complement $A$ to get a solution with the same magnitude in which the first summand is larger than the second. $\endgroup$ – Yuval Filmus Nov 15 '20 at 6:52

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.