1
$\begingroup$

Let $X$ denote one distribution. Let $f,g, \text{ and } h$ denote three functions. If we have the results: $g(X)$ is within a negligible statistical distance of $h(X)$. Is it possible to prove

$$(f(X),g(X)) \text{ is within negligible statistical distance of } (f(X),h(X))$$

I was struggling with this problem for a long time. Any hints are welcomed.

$\endgroup$
1
  • $\begingroup$ Now that I think about it, this question is probably off-topic. $\endgroup$
    – Maeher
    Feb 20, 2020 at 12:10

1 Answer 1

3
$\begingroup$

No, you cannot prove that, since it is not generally true. Consider the following counter example.

Let $X$ be a distribution over $\{0,1\}$ with $$\Pr_{b\gets X}[b=0] = \Pr_{b\gets X}[b=1]=\frac{1}{2}.$$ Let $f,g,h : \{0,1\} \to \{0,1\}$ be defined as $$f : b \mapsto b,\quad g : b \mapsto b, \quad \text{and} \quad h : b \mapsto b\oplus 1.$$

The statistical distance between the distributions $g(X)$ and $h(X)$ is zero and thereby negligible.

\begin{align}&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\Pr_{b'\gets X}[g(b')=b] - \Pr_{b'\gets X}[h(b')=b]\right|\\ =&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\Pr_{b'\gets X}[b'=b] - \Pr_{b'\gets X}[b'\oplus 1=b]\right|\\ =&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\frac{1}{2} - \frac{1}{2}\right| = 0 \end{align}

However, the support of the two distributions $$(f(X),g(X)) \in \{(0,0),(1,1)\}\quad \text{and} \quad (f(X),h(X)) \in \{(0,1),(1,0)\}$$ are completely disjoint and their statistical distance is thus $1$ which is non-negligible.

$\endgroup$
1
  • $\begingroup$ Thanks for your answer! I understand it now! $\endgroup$
    – M.Z.
    Feb 21, 2020 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.