How to draw a Markov network graph for two or pair of variables 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).


*

*How do I draw a directed graphical model (the graph and conditional
probability tables) for these five random variables?

*How do I draw an undirected graphical model (the graph and respective potentials) for these five variables?

*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)?

 A: *

*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}


*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.


*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.
