Suppose $X$ and $Y$ are correlated random variables in a finite set ${\mathcal A}$, and let $f, g$ be functions that map elements from ${\mathcal A}$ to ${\mathcal B}$ for some finite set ${\mathcal B}$. 


Assume the following:


1. $f(X)$ is independent of $Y$
2. $g(Y)$ is independent of $X$


Can we say that there exist independent variables $A, B, C$ and functions $h\_1, h\_2$ such that the joint distribution of f(X), g(Y), X, Y is same as $A$, $B$, $h\_1(A, C)$ and $h\_2(B, C)$?


The intuition behind the claim is that conditioned on $f(X)$ and $g(Y)$, the joint distribution of $X, Y$ should be such that $X$ depends only on $f(X)$, and $Y$ depends only on $g(Y)$. The marginal distribution of one of $X$ or $Y$ conditioned on $f(X)$ and $g(Y)$ of course satisfies this property by the given independence assumptions. The question is whether we can show such a statement for the joint distribution..


If not, then is there a counter-example? Of course, coming up with a counter-example might be hard since one needs to show that it is not true for *any* choice $A, B, C$, $h\_1$ and $h\_2$, but maybe there is some intuitive reasoning why this is not true..



Joint probability distribution as functions
No. Here is a counterexample. Let $\mathcal{A} = \{1,2,3,4\}$, $\mathcal{B} = \{1,2\}$, and $f(x) = g(x) = \lceil\frac{x}{2}\rceil$. Let the joint probability mass function of $X$ and $Y$ be given by the matrix
\[
P = \frac{1}{8}\begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0\end{bmatrix}.
\]
Note that the distribution of $(f(X),Y)$ is uniform over $\mathcal{B}\times\mathcal{A}$ and the distribution over $(X,g(Y))$ is uniform over $\mathcal{A}\times\mathcal{B}$, so the independence assumptions hold.


In searching for a factorization of the type requested, we can assume without loss of generality that $C$ takes values in a finite set (because $\mathcal{A}$ is finite). If a factorization of the desired type existed, then $X' := h\_1(A,C)$ and $Y' := h\_2(B,C)$ would be independent conditioned on $C$, since $A$ and $B$ would be independent.


Suppose there were some value $c$ taken by $C$ with positive probability such that, conditioned on $C=c$, each of $X'$ and $Y'$ took at least two values with positive probability. Let $i\neq j$ be two such values for $X'$ and $k\neq l$ two such values for $Y'$. Then conditioned on $C=c$ the pair $(X',Y')$ could take any of the four values $(i,k), (j,k), (i,l), (j,l)$ with positive probability. Hence the same statement would be true unconditionally. But there are no such values with $P\_{ik},P\_{jk},P\_{il},P\_{jl}$ all positive.


Therefore conditioned on $C$, we know for sure either the value of $X'$ or of $Y'$. From there we know for sure either the value of $A = f(X')$ or $B=g(Y')$. But $A,B,C$ are independent, so either $A$ or $B$ is deterministic, contradicting the assumption that each is uniform over $\mathcal{B}$.


(Edit / ad: For lots more on distributions like this in a game-theoretic context, see my paper “Structure of Extreme Correlated Equilibria: a Zero-Sum Example and its Implications.”)


