# Compute statistical distance between two distributions over tuples

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.

• Now that I think about it, this question is probably off-topic. Feb 20, 2020 at 12:10

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.