# Randomized functions cannot increase statistical distance

In these lecture notes instructor Chris Peikert states the following lemma without a proof

Let $f$ be a (randomized) function on the domain of $X$, $Y$. We have

$\triangle (f(X), f(Y)) \leq \triangle(X, Y )$

where triangle denotes statistical distance between two random variables.

First question: How can I prove this?

Second question:

Assume $X$ and $Y$ are independent uniformly distributed random variables. Define randomized algorithm $f$ like this:

$f(x) := \text{return 1 if$X = x$and 0 otherwise}$

However, $\triangle (X, Y)=0$, but $\triangle (f(X), f(Y))$ is not zero? What I am missing here?

• Definition of statistical distance that I am familiar is: $X$, $Y$ are random variables, $\triangle (X, Y) = \frac{1}{2} \sum_a |P(X = a) - P(Y = a)|$. If both $X$ and $Y$ are uniformly distributed (on the same set) then $P(X = a) = P(Y = a)$ – Student20 Jul 20 '16 at 23:39
• It looks like I misunderstood the definitions: $X$ and $Y$ which Peikert uses are distributions and not random variables. – Student20 Jul 20 '16 at 23:54

## 1 Answer

Second question:

$\Delta$ is defined on distributions so the distributions of $f(X)$ and $f(Y)$ are the same, since $X,Y$ are both uniform. The supremum definition makes this clearer.

First question:

Unless the map is one to one, hence a bijective, when equality holds, the probability that $f(X)=f(Y)$ can only increase compared to the probability that $X=Y$. Prove this for binary distributions and then subpartition and use induction to conclude the general case by using conditional probabilities.

• Regarding second question: $f(X)$ always returns 1 (because we defined it that way), but $f(Y)$ can return 0 sometimes. Why are the distributions of $f(X)$ and $f(Y)$ the same? Thanks. EDIT: maybe distributions are not random variables and my understanding is completely wrong? – Student20 Jul 20 '16 at 23:16