# One-shot Private Randomness Extractor

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

• 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).
– D.W.
Nov 24 '15 at 18:04
• 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. Nov 24 '15 at 18:12
• What are your thoughts? Is this an exercise? 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.
• 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? Nov 25 '15 at 16:16
• 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$. Nov 25 '15 at 16:19
• 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. Nov 25 '15 at 23:51