How to draw a Markov network graph for two or pair of variables

Question

For $i \in \{1, 2, 3\}$, let $X_i$ be a random variable for the event that a coin toss comes up heads (which occurs with probability $q$). Supposing that the $X_i$ are independent, define $X_4 = X_1 ⊕ X_2$ and $X_5 = X_2 ⊕ X_3$, where $⊕$ denotes addition in modulo two arithmetic (XOR logical operation).

1. How do I draw a directed graphical model (the graph and conditional probability tables) for these five random variables?
2. How do I draw an undirected graphical model (the graph and respective potentials) for these five variables?
3. Under what conditions on $q$ do we have $X_5 \perp \!\!\! \perp X_3$ and $X_4 \perp \!\!\! \perp X_1$? Are either of these marginal independence assertions implied by the graphs in (1) or (2)?

Answer 1

1. The directed graphical model is simple: $X_1 \to X_4 \leftarrow X_2 \to X_5 \leftarrow X_3$. The CPTs you have already described in your question:

\begin{align} P(X_1=1)=P(X_2=1)=P(X_3=1)=q \end{align} \begin{align} P(X_4=1|X_1=1\;\&\;X_2=1)&=P(X_4=1|X_1=0\;\&\;X_2=0)\\ &=0\\ P(X_4=1|X_1=1\;\&\;X_2=0)&=P(X_4=1|X_1=0\;\&\;X_2=1)\\ &=1\\ P(X_5=1|X_2=1\;\&\;X_3=1)&=P(X_5=1|X_2=0\;\&\;X_3=0)\\ &=0\\ P(X_5=1|X_2=1\;\&\;X_3=0)&=P(X_5=1|X_2=0\;\&\;X_3=1)\\ &=1 \end{align}

2. When converting this directed network to an undirected Markov network, you must "moralize" the graph, i.e. connect the parents of a common child node, because conditioning on the child node induces a dependency between the parents. So you need to connect $X_1$ to $X_2$ and $X_2$ to $X_3$, like so:

I will leave the question about clique potentials to another user as I don't have much experience with undirected Markov networks.

3. When $X_1 \perp \!\!\! \perp X_4$, we have that $P(X_4=1)=P(X_4=1|X_1=1)$ and $P(X_4=1)=P(X_4=1|X_1=0)$. So we calculate those probabilities and solve for $q$:

\begin{align} P(X_4=1) &= P(X_1=1 \; \& \; X_2=0) + P(X_1=0 \; \& \; X_2=1)\\ &= 2q(1-q) \end{align}

\begin{align} P(X_4=1|X_1=0) &= P(X_2=1)\\ &= q \end{align}

\begin{align} P(X_4=1|X_1=1) &= P(X_2=0)\\ &= 1-q \end{align}

Giving us $q=\frac{1}{2}$, 1 or 0. These values of $q$ produce the independence $X_1 \perp \!\!\! \perp X_4$ (and by symmetry, also $X_3 \perp \!\!\! \perp X_5$). These marginal independences are not implied by either of the graphs – this is a case of the distribution being "unfaithful" to the directed graph.