# Determining unconditional independence in Markov Networks

I would like to know whether $$E \perp\kern-5pt\perp A$$ in the following Markov Network and would like to know if my reasoning is correct:

So, since this is a Pairwise Markov Network, it factorizes into potentials. We have that $$P(A,B,C,D,E) = \phi (A,B) \phi (A,C) \phi(B,D)\phi (C,D)\phi(D,E)\frac{1}{Z}$$

where $$Z$$ is a normalization constant.

And so we have that the marginal for $$E$$ and $$A$$ is $$P(E,A) \propto \sum_{B,C,D}\phi (A,B) \phi (A,C) \phi(B,D)\phi (C,D)\phi(D,E)$$

Since $$\sum_{x_1} \phi(x_1,x_2) \phi(x_1,x_3) = \phi(x_2,x_3)$$

We have that $$\sum_{B,C,D}\phi (A,B) \phi (A,C) \phi(B,D)\phi (C,D)\phi(D,E) = \sum_{C,A} \phi(A,B)\phi(A,C)\phi(B,E,C) = \phi(B,E,C,A)$$. Since $$E$$ and $$A$$ are inside one potential, this makes them dependent.

Would this be a correct way to determine unconditional independence in Markov Networks? Is there a faster, non-formula way to solve this?

$$\newcommand{\pperp}{\perp\kern-5pt\perp} \newcommand{\npperp}{\not\perp\kern-8pt\perp}$$ I am not sure whether I understand your argument. In general, to show that $$A\npperp E$$, I don't think it is sufficient to show that $$p(A, E) = \phi(A, E)$$ for some potential $$\phi$$, but one has to show that this $$\phi(A,E)$$ cannot be factored as $$\phi_A(A)\phi_B(B)$$.

So my approach would be as follows:
To be extra precise, I think what you want to show is the following: The condition, that a probability density function (pdf) has as I-map your Markov Network (MN), is not sufficient to deduce $$A\pperp E$$. I.e., we have to show that there exists a pdf that has the MN as I-map and that has $$A\npperp E$$.

Thus, let's presume that all variables are binary. Then, such a pdf could be: \begin{align} A &\sim U(\{0, 1\})\quad\mbox{(uniform binary random variable)}\\ B &= A\\ C &= A\\ D &= I(B+C-2)\\ E &= D, \end{align} where $$I()$$ is the function that is zero everywhere except at zero where it is equal to one. Then: \begin{align} p(E=0|A=0) &= 1 \\ p(E=0|A=1) &= 0, \end{align} which means $$A\npperp E$$.
(If it vexes you a bit that some conditional probabilities are undefined in this MN, just jitter the Markov transition matrices only a tiny bit, so that all probabilities become positive. This would not change the dependence of $$A$$ and $$E$$.)

Your question: "Is there a faster, non-formula way to solve this?":
Yes, there is the easier, graph-based, way. For MNs, if you can presume that the graph is a P-map for the pdf, then $$A \pperp E$$ if and only if there is no path in the MN connecting $$A$$ and $$E$$.

• Thanks a lot for this answer. I was wondering whether there is a simpler way to deduce this, without "rigorously" proving it? For example we can see from a BN whether some variables are d-separated, without constructing variables the way you did in your approach here
– user
Aug 4, 2022 at 13:28
• Sorry, I overlooked the last sentence of your post. I have extended my answer. Aug 4, 2022 at 15:27
• Thanks. So in simple words, if there is a path from $A$ to $E$, then they are not unconditionally independent?
– user
Aug 4, 2022 at 16:21
• Yes, that is correct. Aug 4, 2022 at 16:26