# Indistinguishability of exponentially close distributions

Let $$D_{1}$$ and $$D_{2}$$ be two probability distributions over $$n$$-bit strings such that the total variation distance between them is $$\mathcal{O}\left(1/{2^{n}}\right)$$. Given as input a polynomial number of samples from any one of the distributions, the task is to output $$1$$ if the samples come from the first distribution and $$0$$ if they come from the second one. I am trying to show that no polynomial-time algorithm (even with bounded error) can do this task.

Intuitively, it should be very clear that two distributions that are exponentially close are indistinguishable. But how do I formalize the intuition?

Here is the key. Let $$A \otimes B$$ be the distribution corresponding to a sample from $$A$$ and an independent sample from $$B$$, and denote total variation distance by $$d_{TV}$$. Then
$$d_{TV}(A_1 \otimes A_2, B_1 \otimes B_2) \leq d_{TV}(A_1,B_1) + d_{TV}(A_2,B_2)$$
We can see this using the $$L_1$$ formula for $$d_{TV}$$: \begin{align} d_{TV}(A_1\otimes A_2,B_1\otimes B_2) &= \frac{1}{2} \sum_{x_1,x_2} |\Pr[A_1=x_1]\Pr[A_2=x_2] - \Pr[B_1=x_1]\Pr[B_2=x_2]| \\ &\leq \frac{1}{2} \sum_{x_1,x_2} |\Pr[A_1=x_1]\Pr[A_2=x_2] - \Pr[B_1=x_1]\Pr[A_2=x_2]| \\ &+ \frac{1}{2} \sum_{x_1,x_2} |\Pr[B_1=x_1]\Pr[A_2=x_2] - \Pr[B_1=x_1]\Pr[B_2=x_2]| \\ &= \frac{1}{2} \sum_{x_2} \Pr[A_2=x_2] \sum_{x_1} |\Pr[A_1=x_1] - \Pr[B_1=x_1]| \\ &+ \frac{1}{2} \sum_{x_1} \Pr[B_1=x_1] \sum_{x_2} |\Pr[A_2=x_2] - \Pr[B_2=x_2]| \\ &= \sum_{x_2} \Pr[A_2=x_2] d_{TV}(A_1,B_1) + \sum_{x_1} \Pr[B_1=x_1] d_{TV}(A_2,B_2) \\ &= d_{TV}(A_1,B_1) + d_{TV}(A_2,B_2). \end{align}
Now let $$D^{\otimes n}$$ denote $$n$$ independent samples from $$D$$. The above inequality shows that $$d_{TV}(D_1^{\otimes m}, D_2^{\otimes m}) \leq m d_{TV}(D_1,D_2).$$ Let $$E$$ be the event that your algorithm outputs "$$D_1$$". The definition of $$d_{TV}$$ guarantees that $$|\Pr_{D_1^{\otimes m}}[E] - \Pr_{D_2^{\otimes m}}[E]| \leq d_{TV}(D_1^{\otimes m}, D_2^{\otimes m}) \leq m d_{TV}(D_1,D_2).$$ Here $$\Pr_D$$ denotes that the samples in the algorithm are generated from the distribution $$D$$.
We deduce that an algorithm with advantage $$\delta$$ must use at least $$\delta/d_{TV}(D_1,D_2)$$ samples.
• How does the definition of $d_{TV}$ guarantee the first inequality in the last line? Nov 6, 2020 at 13:50
• My definition of total variation distance is the maximum, over all events $E$, of this quantity. Nov 6, 2020 at 15:52