Joint probability distribution as functions 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:


*

*$f(X)$ is independent of $Y$

*$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..
 A: 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.”)
A: $\mathcal B$ might be a singleton, or f and g constant in which case X and Y are both functions of C, which need not be the case, i.e.   if they have a joint density.
