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

  1. 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:

markov network

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

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.