# What exactly would be a perfect map in this situation? Is a perfect map a distribution which has the same independence assumptions?

I am currently studying Bayesian Reasoning and Machine Learning by David Barber, the 4th chapter exercise 4.7 (p 80). The exercise is the following:

Consider the following belief network:

1. Write down a Markov Network of $$p(x_1,x_2,x_3)$$
2. Is your Markov Network a perfect map of $$p(x_1,x_2,x_3)$$?

I have done 1. It was simple - just sum over $$h_1$$ and $$h_1$$ and then $$x_1,x_2,x_3$$ are coupled and my solution is the same as in the solution manual. I didn't know how to do (2) so I looked at the solution manual and didn't quite understand their answer:

This is not a perfect map since in $$p(x_1,x_2,x_3)$$ we have $$x_1 \perp\kern-5pt\perp x_3 | \emptyset$$, which is violated by the Markov Network representation.

I don't fully understand 2 things:

1. What exactly would be a perfect map in this situation? (an example of a perfect map would be great) Is a perfect map a distribution which has the same independence assumptions?

2. Isn't the independence $$x_1 \perp\kern-5pt\perp x_2 | \emptyset$$ also violated?

The definition of a perfect map is given on page 77:

A graph G which is both an I-map and a D-map for P is called a perfect map.

So, a graph $$G$$ is a perfect map of a probability distribution $$P$$ if

1. every separation (see Definitions 4.5 and 4.6 on page 68) in the graph $$G$$ is also a conditional independence relation in $$P$$, and
2. every conditional independence relation in $$P$$ is a separation in the graph $$G$$.

The decisive point here is, that perfect maps do not always exist. There are distributions $$P$$ that don't admit a perfect map. And this marginalization of the graph of exercise 4.7 is an example. And here is why:

You have already figured out that there must be an edge between all three nodes $$x_1, x_2$$ and $$x_3$$. This is because if we condition on $$x_3$$, then $$x_1$$ and $$x_2$$ are still dependent, and it is clear that an undirected graph that is supposed to describe this must have an edge between $$x_1$$ and $$x_2$$. Similar arguments show the necessity of the edges between $$x_2$$ and $$x_3$$ and between $$x_3$$ and $$x_1$$ (for this last case, note that $$x_2$$ is a collider). I.e., the fully connected graph is the only candidate we have left. But unfortunately, since $$x_2$$ is a collider, we have $$x_1 \perp\kern-5pt\perp x_3 | \emptyset$$. But in our fully connected graph, $$x_1$$ and $$x_3$$ are not separated, thus there is no perfect map.

The independence $$x_1 \perp\kern-5pt\perp x_2 | \emptyset$$ does not hold. The nodes $$x_1, x_2$$ are dependent because of the path $$x_1\leftarrow h_1 \to x_2$$.