1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How does the definition of $d_{TV}$ guarantee the first inequality in the last line? $\endgroup$ – BlackHat18 Nov 6 '20 at 13:50
  • $\begingroup$ My definition of total variation distance is the maximum, over all events $E$, of this quantity. $\endgroup$ – Yuval Filmus Nov 6 '20 at 15: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.