# Conditional Independence in Bayes Network

I have just started working through Michael Jordan's notes on Probabilistic Graphical Models and seem to be stuck on the exercise on page 5. I summarize the question here:

Suppose $$G = (V,E)$$ is a DAG with $$n$$ nodes. Corresponding to each node $$i \in V$$, let $$X_i$$ be a random variable. Denote the set of random variables that belong to the parent nodes of $$X_i$$ by $$X_{\pi_i}$$. To each note $$i$$, let $$f_i(x_i, x_{\pi_i})$$ be a function that behaves like a pdf on $$X_i$$ conditioned on $$X_{\pi_i}$$. Let $$p(x_1, \ldots , x_n) = \prod_{i=1}^n f_i(x_i, x_{\pi_i})$$.

It can be shown that $$p$$ is a joint distribution on $$X_1, \ldots, X_n$$. Show that for every $$i \in V, \> p(x_i \mid x_{\pi_i}) = f_i(x_i, x_{\pi_i})$$. My idea for a proof was to use induction.

We can assume without loss in generality that the nodes are ordered topologically. Then: \begin{align*} p(x_n \mid x_1, \ldots, x_{n-1}) &= \frac{p(x_1, \ldots, x_n)}{p(x_1, \ldots, x_{n-1})} \\ &= \frac{\prod_{i=1}^n f_i(x_i, x_{\pi_i})}{\prod_{i=1}^{n-1} f_i(x_i, x_{\pi_i})} \\ &= f_n(x_n, x_{\pi_n}) \end{align*}

The last (EDIT:second*) equality follows from $$x_n$$ not being a parent of any node. Now, I wish to show that $$p(x_n \mid x_1, \ldots, x_{n-1}) = p(x_n \mid x_{\pi_n})$$ and it is intuitive to me because no other node but the parents of $$x_n$$ have any sort of bearing on $$p(x_n \mid x_1, \ldots, x_{n-1}) = f_n(x_n, x_{\pi_n})$$. But how would I show this formally? The rest of the result follows quickly from induction since we can just remove $$x_n$$ from the graph.

• Unfortunately this approach won't work, because you haven't shown why $\tilde{p}(x_1, \dots, x_{n-1}) = \prod_{i=1}^{n-1} f_i(x_i, x_{\pi_i})$ is the same as $p(x_1, \dots, x_{n-1}) = \sum_{x_n} p(x_1, \dots, x_n)$. Both $p$ and $\tilde{p}$ are valid probability distributions, but it's not clear why the latter is necessarily the marginal of the former. – tddevlin Mar 7 '19 at 8:31

The notation is quite horrendous but I think this is what you're looking for. I recommend trying this out on a small example of say 4 nodes to get a more concrete feeling for what's going on. I briefly explain the following equations at the bottom. \begin{align} p(x_i | x_{\pi_i}) & = \frac{p(x_i, x_{\pi_i})}{p(x_{\pi_i})} \\ & = \frac{\sum_{ \{x_j \mid\ j \neq i, \ j \notin \pi_i \} } p(x_1, \dots, x_n)}{\sum_{ \{x_j \mid \ j \notin \pi_i \} } p(x_1, \dots, x_n)} \\ & = \frac{\sum_{ \{x_j \mid\ j \neq i, \ j \notin \pi_i \} } \prod_{k=1}^n f_k(x_k, x_{\pi_k}) }{\sum_{ \{x_j \mid \ j \notin \pi_i \} } \prod_{k=1}^n f_k(x_k, x_{\pi_k})} \\ & = \frac{f_i(x_i, x_{\pi_i}) \sum_{ \{x_j \mid\ j \neq i, \ j \notin \pi_i \} } \prod_{k\neq i} f_k(x_k, x_{\pi_k}) }{\sum_{ \{x_j \mid \ j \notin \pi_i \} } \prod_{k=1}^n f_k(x_k, x_{\pi_k})} \\ & = \frac{f_i(x_i, x_{\pi_i}) \phi(x_{\pi_i}) }{\phi(x_{\pi_i})} \\ & = f_i(x_i, x_{\pi_i}). \end{align}
4. Upper sum doesn't depend on $$x_i$$ or $$x_{\pi_i}$$ so we can factor out $$f_i$$.
5. Push the sums into the product one at a time and use the fact that each $$f_k(x_k, x_{\pi_k})$$ sums to one over $$x_k$$. In the end you're left with some function $$\phi(x_{\pi_i})$$. This happens in both the numerator and the denominator.
6. Cancel the $$\phi$$'s.