<p>I have been working on privacy and come across a neat problem.</p>

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

<p>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$.</p>

<p>I am looking for a sufficient and necessary condition of this.</p>

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

<p>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).</p>

CC BY-SA 3.0
2015-02-11T02:20:33.170Z
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
CC BY-SA 3.0
2015-02-11T14:20:23.670Z
@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
CC BY-SA 3.0
2015-02-11T14:22:11.160Z
@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
CC BY-SA 3.0
2015-02-11T15:57:00.423Z
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
CC BY-SA 3.0
2015-02-11T16:47:16.437Z
@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 http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7028602
SAmath
CC BY-SA 3.0
2015-02-12T15:04:11.763Z
(a) You are probably aware of the large literature on "secrecy capacity" which is closely related to this question. (b) Given your motivation, you might be aiming for the wrong target by maximizing the Shannon entropy of f(Y). If the motivation is crypto/security, then it seems you really want to extract a secret key, which should be near-uniform on some set. In that case, the key quantity you want is the (smoothed) *conditional min-entropy* of Y given X. See Renner and Wolf, ASIACRYPT 2005 for a definition.
Adam Smith
CC BY-SA 3.0
2015-02-12T16:31:22.303Z
@AdamSmith, thanks for your comment. Can you please let me know why do you think this target is wrong? All those results on crypto/secrecy from both information and computer science communities, are approximate the independence or asymptotic independence. However, here I am looking for a single-shot exact independence. Like classical results on channel coding versus zero-error finite-length channel coding. I like to know your opinion on this
SAmath
<cr.crypto-security><pr.probability><it.information-theory><st.statistics>
One kind of dependence relation between a pair of random variables
SAmath
# One kind of dependence relation between a pair of random variables

(Asked by: username_0 on 2015-02-10)

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).

**Tags:** cr.crypto-security, pr.probability, it.information-theory, st.statistics
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  
> **username_0**: @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.  
> **username_2**: 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.  
> **username_0**: @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 http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7028602  
> **username_1**: (a) You are probably aware of the large literature on "secrecy capacity" which is closely related to this question. (b) Given your motivation, you might be aiming for the wrong target by maximizing the Shannon entropy of f(Y). If the motivation is crypto/security, then it seems you really want to extract a secret key, which should be near-uniform on some set. In that case, the key quantity you want is the (smoothed) *conditional min-entropy* of Y given X. See Renner and Wolf, ASIACRYPT 2005 for a definition.  
> **username_0**: @AdamSmith, thanks for your comment. Can you please let me know why do you think this target is wrong? All those results on crypto/secrecy from both information and computer science communities, are approximate the independence or asymptotic independence. However, here I am looking for a single-shot exact independence. Like classical results on channel coding versus zero-error finite-length channel coding. I like to know your opinion on this  

---

## 0 answers

