2
$\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?

Improve this question
$\endgroup$
3
  • $\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$ Commented Jul 20, 2016 at 23:39
  • $\begingroup$ It looks like I misunderstood the definitions: $X$ and $Y$ which Peikert uses are distributions and not random variables. $\endgroup$ Commented Jul 20, 2016 at 23:54
  • $\begingroup$ Similar question/answers here $\endgroup$ Commented Dec 27, 2023 at 20:53

2 Answers 2

Reset to default
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$
1
  • $\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$ Commented Jul 20, 2016 at 23:16
1
$\begingroup$

I think the problem is due to that, the randomized process you define is dependent of $X$. I think the following slightly modified version of your statement is correct:

Consider any two random variables $X$ and $Y$ distributed over some finite universal set $U$. Consider a randomized process $f(t, z)$, which is a (deterministic) function $$ f: U\times R\to U, $$ where $R$ is the set of all random seeds.

Let $Z$ be a random variable distributed over $R$ that is independent of $X$ and $Y$.

Then $$\Delta(f(X, Z); f(Y, Z))\leq \Delta(X; Y).$$

Note that letting the range of $f$ to be $U$ is without loss of generality. In fact, we can also let $R=U$ w.l.o.g..

Here is my proof:

For all $u\in U$ , let set $S_u\subseteq U\times R$ be $$ S_u\overset{\text{def}}{=}\{(t, z)\in U\times R: f(t, z) = u\}. $$ Let set $S_{u|z}$ be $$ S_{u|z} \overset{\text{def}}{=}\{t\in U:f(t, z)=u\}. $$ Note that for different $u_1\neq u_2$ , $S_{u_1|z}$ and $S_{u_2|z}$ are disjoint. Hence the disjoint union of all $S_{u|z}$ is a subset of $U$ , i.e. $$ \bigcup_{u\in U} S_{u|z}\subseteq U. $$ What we want to prove is $$ \begin{align}2\Delta(f(X, Z); f(Y, Z))&=\sum_{u\in U}\left|\Pr[f(X, Z)=u]-\Pr[f(Y, Z)=u]\right|\\ &=\sum_{u\in U} \left|\Pr[(X, Z)\in S_u]-\Pr[(Y, Z)\in S_u]\right|\\ &=\sum_{u\in U}\left|\sum_{z\in R}\Pr[Z=z]\cdot \left(\Pr[X\in S_{u|z}]-\Pr[Y\in S_{u|z}]\right)\right|\\ &\leq\sum_{u\in U}\sum_{z\in R}\Pr[Z=z]\cdot \left|\Pr[X\in S_{u|z}]-\Pr[Y\in S_{u|z}]\right|\\ &=\sum_{z\in R}\Pr[Z=z]\cdot\left(\sum_{u\in U} \left|\Pr[X\in S_{u|z}]-\Pr[Y\in S_{u|z}]\right|\right)\\ &\leq\sum_{z\in R}\Pr[Z=z]\cdot\left(\sum_{t\in U} \left|\Pr[X=t]-\Pr[Y=t]\right| \right)&(*)\\ &=2\Delta(X; Y). \end{align} $$

In step $(*)$, we take the union of all (disjoint) $S_{u|z}$, which is contained in $U$.

This finishes our proof.

Hope this helps!

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.