Suppose a pair of random variables $(X,Y)\in\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$ is given. I am interested in a deterministic mapping $f:\mathcal{Y}\to \{0, 1\}^k,$ for some integer $k>0$ such that $$f(Y)\perp X, \qquad \text{i.e.}, \quad f(Y)\text{ is independent of } X,$$ and $$H(f(Y))>0.$$ The second condition is just to rule out the degenerate functions $f$.

For example if $X\sim\mathsf{Bernoulli}(p)$ and $P_{Y|X}$ is an erasure channel* with erasure probability $\delta>0$, then $f:\{0,\text{e},1\}\to \{0,1\}$ where $\text{e}$ is the erasure, defined as
$$f(1)=f(0)=1,\qquad f(\text{e})=0,$$ satisfies the above condition.

What is a necessary and sufficient condition on $P_{XY}$ for the existence of such deterministic map?

*By erasure channel, I mean the following conditional distribution: $$P_{Y|X}(y|x)=(1-\delta)1_{\{y=x\}},$$ and $$P_{Y|X}(\text{e}|x)=\delta, ~~~~\text{for}~~~~x=0,1.$$

  • 1
    $\begingroup$ I suspect you already know this, but there's no guarantee such a mapping exists: e.g., if $(X,Y)$ is uniformly distributed on $\{(0,0),(0,1),(1,0)\}$, then no deterministic function $f$ exists with the desired properties (the only possibilities are the identity function $f(y)=y$ or the constant functions $f(y)=0$ or $f(y)=1$; none actually works). $\endgroup$ – D.W. Nov 24 '15 at 18:04
  • 1
    $\begingroup$ Thanks for your comment. I know that such $f$ is not guaranteed to exist. That is why I am looking for a necessary and sufficient condition on $P_{XY}$ which guarantees that such a mapping exists. $\endgroup$ – math-Student Nov 24 '15 at 18:12
  • 1
    $\begingroup$ What are your thoughts? Is this an exercise? $\endgroup$ – Yuval Filmus Nov 24 '15 at 19:46

If such a mapping $f$ exists at all, there always exists such a mapping with $k = 1$: you can always collapse a larger function in such a way that doesn't make the mapping constant. In other words, a mapping $f$ exists if there is some non-trivial event $E$ depending only on $Y$ which is independent of $X$. The converse is also true.

  • $\begingroup$ Thanks for your answer. I dont understand what you mean by "there is a non-trivial event $E$ depending only on $Y$ and independent of $X$". Can you please elaborate a bit? $\endgroup$ – math-Student Nov 25 '15 at 16:16
  • $\begingroup$ There is some event $E$ such that $\Pr[X=x \land E] = \Pr[X=x]\Pr[E]$. Furthermore, you can tell whether $E$ happened given only $Y$. (That is, $E$ is measurable with respect to $Y$.) Furthermore, $0 < \Pr[E] < 1$. $\endgroup$ – Yuval Filmus Nov 25 '15 at 16:19
  • $\begingroup$ Yuvel thanks again for your elaboration. To be honest with you, this is not what I was hoping for. I could show that in this case the second singular value of the matrix with element $\frac{P_{XY}(x,y)}{\sqrt{P_X(x)P_Y(y)}}$ is zero in this case. However, the converse is not true. In other words, a necessary condition for the existence of such mapping $f$ is that the smallest singular value of the above matrix is equal to zero. However, I dont think the converse is true. $\endgroup$ – math-Student Nov 25 '15 at 23:51

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.