4

Suppose $A$, $B$, and $C$ are random variables. If $A$ and $B$ are independent, and they are also conditionally independent given $C$, can we conclude that either $A$ and $C$ are independent or $B$ and $C$ are independent? Or is there a case where given the constraints, $C$ can still be dependent to both $A$ and $B$?

This question was inspired from Bayesian network configurations. I was trying to prove the former with no luck, and I wasn't able to find anything online that helped, so I figured that it might not even be true. Could someone please provide either a proof or a counterexample (or some other reasoning to why it's false)?

Springo
  • 43

3 Answers3

6

What if $C \in \{1, 2, 3, 4\}$ equally likely and

\begin{align} C=1 \implies A=0, B=0\\ C=2 \implies A=0, B=1\\ C=3 \implies A=1, B=0\\ C=4 \implies A=1, B=1 \end{align}

Michael
  • 23,905
  • The Arnaud example also works, coincidentally it also conditions on $C$ taking one of four values. – Michael Apr 24 '18 at 00:23
  • 1
    Funny that we came up with the same solution :) – Arnaud Mortier Apr 24 '18 at 00:23
  • 1
    Hey guys, I came up with the exact same solution as well – spaceisdarkgreen Apr 24 '18 at 00:25
  • @spaceisdarkgreen : Sorry, I didn't read yours, though it seems to have come in 2-3 minutes before mine. It looked like a paragraph discussion of what we need for an answer, rather than an answer. Reading it now it looks like my answer is exactly the same as yours, again with $C$ taking one of four values! – Michael Apr 24 '18 at 00:29
  • Makes sense, thanks all of you! – Springo Apr 24 '18 at 00:45
5

Here is a family of counterexamples:

Let $A$ and $B$ be independent, both almost surely non-zero, both taking positive as well as negative values with non-zero probability.

Let $C$ equal $1$ if $(A,B)$ lies in the first quadrant, $2$ if $(A,B)$ lies in the second quadrant, etc.

$A$ and $C$ are not independent, and neither are $B$ and $C$, but $A$ and $B$ are still independent conditional to $C$.

Arnaud Mortier
  • 27,276
  • My answer was likely the easiest to verify, though I actually like this one as it seems the most interesting. – Michael Apr 24 '18 at 00:48
4

We need the things $A$ teaches us about $C$ have no relevance to $B$ and vice versa. So let $C$ take four values uniformly, coded as the corners of the square. And then, conditional on $C,$ let $A$ and $B$ be constant $0$ or $1$ (thus conditionally dependent, with $A$'s value depending on whether $C$ is on the top or bottom of the square, and $B$'s depending on whether $C$ is on the left or right side of the square. Then $A$ and $B$ will be unconditionally independent as well.

spaceisdarkgreen
  • 58,508
  • I am a bit confused in your wording, and especially the sentence "And then, conditional on C, let A and B be independent." In fact I think you just mean that, given C, A and B are completely determined (and hence trivially independent). That was also the idea from my answer (which I actually gave 2-3 minutes after you, so you beat me to the punch). – Michael Apr 24 '18 at 00:31
  • Oh. Then I suppose my answer ends up being a special case of yours, with "depending overtly" defined more stringently. – Michael Apr 24 '18 at 00:39
  • @Michael I deleted cause I'm unsure... did I botch that? yours definitely works, I'm not sure my more general examples do – spaceisdarkgreen Apr 24 '18 at 00:40
  • Arnaud's examples work. The wording in your answer is perhaps too vague to tell, except if you define "depending overtly" as "completely dependent" (and with a specific 0/1 numeric scheme as in my answer, I suppose your answer could fail if the numbers are not chosen correctly). – Michael Apr 24 '18 at 00:41