Decomposing a discrete random variable

Question

Note: this question is a duplicate of another question asked by my classmate with much more contexts. Attempt to suggest edits is rejected due to drastic change, so I reask the question.

---

I hate to admit it, but I'm asking for help on a homework problem assigned in our Information Theory class. I'm really scratching my head but unable to prove it:

For two discrete random variables $X, Y \sim p(x,y)$, we can find another random variable $Z$ independent of $X$, such that there exists a function $f$ satisfying $Y = f(X,Z)$.

The problem also comes with a hint that calls for a constructive proof.

Now that I have (maybe in a wrong way) constructed a random variable $Y'$ that has the same distribution as $Y$, but I simply can't prove that $Y = Y'$ due to their identical distribution.

This question I found may be related to the problem but it goes unanswered. Any help is appreciated!

Answer 1

I'll post my professor's answer here. The problem is called Functional Representataion Lemma and you may search for its proof on the internet. The conclusion of the lemma is actually stronger, though.

Answer 2

Given $X = x$ and $Y = y$, let $Z$ be uniform on the interval $\left[\mathbb P(Y < y \mid X=x), \mathbb P(Y \le y \mid X = x)\right]$. Then $Y = \min \{y: \mathbb P(Y \le y \mid X) \ge Z\}$. That is, when $X = x$ and $Z = z \in (0,1)$, $Y = \min \{y: \mathbb P(Y \le y \mid X = x) \ge z \}$.

Answer 3

Let $Z$ be uniform on $[0,1]$. Given $X=x$, use inverse transform sampling to generate $Y$, using $Z$ as the uniform variable and using $q(y)= p(x,y)/\left(\sum_y p(x,y)\right)$ as the distribution.