# Showing conditional independence in a graphical model

In a graphical model, we say that set $$A$$ and $$B$$ are conditionally independent given set $$C$$ if all routes from $$A$$ to $$B$$ are blocked. There are multiple ways for the route to be blocked at a node. One instance for the route to be blocked at a node is when neither the descendants or the node itself is in $$C$$.

Given the following:

let $$A = \{x_1\}, \ B = \{x_3\}$$ and $$x_2 \notin C$$. How then do we prove that

$$Pr(A,B|C) = Pr(A|C) Pr(B|C)$$

There is only one route (or "path") from $$A$$ to $$B$$, namely $$x_1\to x_2\to x_3$$. Is this path blocked at any node? Yes, it is blocked at node $$x_2$$ since "neither the node $$x_2$$ nor its descendants" (which it does not have) are in $$C$$. So all the paths are blocked, and we have conditional independence.

In this particular example we can also argue directly, though it is a bit of a "degenerate case". The Bayes net modeling assumption is "each variable is conditionally independent of its non-descendants, given its parents”. Applying it to $$x_1$$ and $$x_3$$ we have $$P(A,B)=P(A)P(B)$$.

We now ask $$P(A,B|C) =?= P(A|C) P(B|C)$$

Since $$x_2\notin C$$, it is actually completely irrelevant that we have a Bayes net relating $$x_2$$ to $$A$$ and $$B$$. Two independent random variables are independent after conditioning on any subset of them. In detail:

If $$C=\emptyset$$ we have the original $$P(A,B)=P(A)P(B)$$.

If $$C=A$$ assuming for simplicity that the variables are discrete and $$P(A=a)$$ is never zero, and using notation $$\delta(p,q)=\begin{cases}1 \text{ if } p=q\\ 0 \text{ else }\end{cases}$$, we have

\begin{align*}P((A,B)=(a,b)|A=x) =& \delta(a,x) \frac{P((A,B)=(x,b))}{P(A=x)}\\&=\delta(a,x) P(B=b)=P(A=a|A=x)P(B=b|A=x)\end{align*}

where we used $$P((A,B)=(x,b))=P(A=x)P(B=b)$$ and $$P(B=b)=P(B=b|A=x)$$ by independence. This is conventionally written $$P(A,B|A)=P(A|A)P(B|A)$$.

If $$C=B$$ the argument is symmetric (assuming $$P(B=b)$$ is never zero).

Finally if $$C=\{A, B\}$$ we have under suitable assumptions

\begin{align*} P((A,B)=(a,b)|(A,B)=(x,y)))&=\delta((a,b), (x,y))=\delta(a,x)\delta(b,y)\\&=P(A=a|A=x, B=y)P(B=b|A=x, B=y) \end{align*}

or $$P(A,B|A,B)=P(A|A,B)P(B|A,B)$$.

All of this can be done with continuous random variables and their densities instead.

• Yes, but how do we use the rules of conditional probability to illustrate that this is indeed the case? – Sean Lee Apr 14 at 13:19
• Are you interested in the general derivation of the D-separation rules or in a derivation of conditional independence for this particular case "from first principles"? – Max Apr 14 at 20:12
• I'd like to see a proof from first principles for this case – Sean Lee Apr 14 at 21:49
• I've added that. – Max Apr 15 at 9:07