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


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.”)


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

  • $\begingroup$ Hmm, I think $C$ could be represented as a pair $(X',Y')$ with the same joint distribution as $(X,Y)$, with $h_1(A,X',Y') = X'$ and similarly for $h_2$. $\endgroup$ – usul Mar 27 '14 at 16:02
  • $\begingroup$ Yes, in particular $C$ can carry any information about the joint distribution of $X$, $Y$ as long as $C$ is independent of $f(X)$, $g(Y)$. So, setting $f(X)$ and/or $g(Y)$ to a constant can only help.. $\endgroup$ – user47772 Mar 27 '14 at 16:33

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.