$X \not\!\perp\!\!\!\perp Y$ and $X \perp Y \mid Z$ implies $X \not\!\perp\!\!\!\perp Z$

Question

I've been trying to prove this statement by opening up things on the left hand side using the chain rule but am really getting nowhere. Any tips/hints would be very helpful and appreciated!

Answer 1

Here is an elementary argument, using an obvious notation. Notice how it mirrors @d.k.o's measure-theoretic proof. $$ p(x,y)=\sum_z p(x,y\mid z)p(z) \stackrel{(1)}= \sum_z p(x\mid z)p(y\mid z)p(z)\stackrel{(2)}=p(x)\sum_zp(y\mid z)p(z)=p(x)p(y) $$ In (1) we use the conditional independence of $X$ and $Y$ given $Z$; in (2) we assume independence of $X$ and $Z$, from which we conclude that $X$ and $Y$ must be independent.

Answer 2

Suppose that $X$ is independent of $Z$. Then if $X$ is independent of $Y$ conditionally on $Z$ implies that $$ \mathsf{E}[f(X)g(Y)]=\mathsf{E}[\mathsf{E}[f(X)g(Y)\mid Z]]=\mathsf{E}[\mathsf{E}[f(X)\mid Z]\mathsf{E}[g(Y)\mid Z]]=\mathsf{E}[f(X)]\mathsf{E}[g(Y)] $$ for any measurable functions $f$ and $g$ for which the relevant expectations exists (i.e. the unconditional independence of $X$ and $Y$).