Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Motivation

Let $f(\cdot)$ be a (possibly randomized) function, such that for any random variable $X$ (taking values from a finite set $D$), $X$ and $f(X)$ are statistically independent. Let $U, U_1, U_2, \ldots$ be uniform and independent random variables over $D$.

Example: $f(X)=X \oplus U$. That is, $f$ picks a random value from $D$ and XORs it with a sample from its input (assuming XOR is well defined).

FACT: It can be easily proven that $(U_1, f(U_1))$ and $(U_2, f(U_3))$ are identically distributed.

Main Problem

In the main problem, we don't assume that $X$ and $f(X)$ are statistically independent. Instead, we assume that for any $X$, the mutual information between $X$ and $f(X)$ is very small. Formally:

Let $f(\cdot)$ be a (possibly randomized) function, such that for any random variable $X$ (taking values from a finite set $D$), we have $$I(X; f(X)) < \epsilon \enspace,$$ where $\epsilon$ is a (small) positive real value.

Can we prove a fact similar to above? That is, find some $\delta$ as a function of $\epsilon$, such that for all $(\alpha,\beta) \in D^2$:

$$\big| \Pr [(U_1, f(U_1)) = (\alpha,\beta)] - \Pr [(U_2, f(U_3)) = (\alpha,\beta)] \big| < \delta$$

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.