# Distinguishability of distributions that are not close given just one sample

Consider (over $$n$$-bit strings) the uniform distribution $$U$$, and another distribution $$D$$ such that $$$$\text{Distance}(D, U) \geq \frac{1}{e},$$$$ where $$\text{Distance}$$ stands for the total variation distance, given by $$$$\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|,$$$$ 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 $$$$\left|\underset{x \sim D}{\text{Pr}}[A(x) =1] - \underset{x \sim U}{\text{Pr}}[A(x) =1]\right|$$$$ 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$$?

• The first step would be to formally define "to be able to distinguish between two distributions given one sample". Commented Nov 14, 2020 at 16:18
• 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. Commented Nov 14, 2020 at 16:20
• I modified the question. Commented Nov 14, 2020 at 16:59
• 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. Commented Nov 14, 2020 at 17:07
• The optimal algorithm $A$ outputs $1$ if $\Pr[D(x)] \geq \Pr[U(x)]$, and $0$ otherwise. Commented Nov 14, 2020 at 17:08

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.
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}
• 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}$? Commented Nov 14, 2020 at 17:36
• 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)]$. Commented Nov 14, 2020 at 17:44
• 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)$. Commented Nov 14, 2020 at 18:05
• 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. Commented Nov 15, 2020 at 6:52