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:

enter image description here

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.

  • $\begingroup$ Yes, but how do we use the rules of conditional probability to illustrate that this is indeed the case? $\endgroup$ – Sean Lee Apr 14 at 13:19
  • $\begingroup$ 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"? $\endgroup$ – Max Apr 14 at 20:12
  • $\begingroup$ I'd like to see a proof from first principles for this case $\endgroup$ – Sean Lee Apr 14 at 21:49
  • $\begingroup$ I've added that. $\endgroup$ – Max Apr 15 at 9:07

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.