# One kind of dependence relation between a pair of random variables

I have been working on privacy and come across a neat problem.

Suppose two random variables $X$ and $Y$, over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$, are given with joint distribution $P_{XY}$.

We want to make sure that there exists a non-degenerate function acting on $\mathcal{Y}$, say, $f(Y)$, such that $f(Y)$ is independent of $X$.

I am looking for a sufficient and necessary condition of this.

It is clear that a necessary condition for this is that $P_{XY}$ be rank deficient.

I am, in particular, hoping to see if there is any connection to the set of singular values of the conditional expectation operator (like the connection between maximal correlation and the second largest singular value of conditional expectation operator).

• What does nondegenerate mean in this context? Do you need the distribution of f(Y) to be close to uniform? Does f(Y) have to be exactly independent of X, or is it sufficient for it to be close to independent of X? – Adam Smith Feb 11 '15 at 2:20
• @AdamSmith, All you said are nice and meaningful generalization of this problem. But what I want at first is to find the extreme case, where I have exact independence between $f(Y)$ and $X$. My original problem was to find among all $f$ having this property, and maximizes $H(f(Y))$, where $H$ is the entropy. – SAmath Feb 11 '15 at 14:20
• @AdamSmith, note that if $f$ returns a constant number, then it is always independent with $X$, so I need to assume that $f$ is still a random variable, i.e., it takes at least two values with non-zero probability. This is what I mean by non-degenerate. – SAmath Feb 11 '15 at 14:22
• I really like this question "what can we say about the $f(Y)$ that maximizes entropy subject to being independent of $X$? Then your question is the special case where there is a nontrivial answer, i.e. the maximizer's entropy is not zero. – usul Feb 11 '15 at 15:57
• @usul, I have been working on and off on this question, but it turns out to be hard to get a solid result on such functions $f$. If you are interested you can have a look at the following paper ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7028602 – SAmath Feb 11 '15 at 16:47