1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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)$ $\endgroup$ – Student20 Jul 20 '16 at 23:39
  • $\begingroup$ It looks like I misunderstood the definitions: $X$ and $Y$ which Peikert uses are distributions and not random variables. $\endgroup$ – Student20 Jul 20 '16 at 23:54
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Student20 Jul 20 '16 at 23:16

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.