Chapter 17 - Undirected Graphs and Conditional Independence.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 17. Undirected Graphs and Conditional Independence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$k$ binary variables $Y_1, \\dots, Y_k$ correspond to a multinomial with $N = 2^k$ categories.  Even for moderately large $k$, $2^k$ will be huge.  It can be shown in this case that the MLE is a poor estimator, because the data are **sparse**.\n",
    "\n",
    "Graphical models often require fewer parameters and may lead to estimators with smaller risk.  There are two main types of graphical models:  undirected and directed.  Here we introduce undirected graphs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.1 Conditional Independence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $X$, $Y$, $Z$ be discrete random variables.  We say that $X$ and $Y$ are **conditionally independent given $Z$**, written  $X \\text{⫫} Y \\;|\\; Z$, if\n",
    "\n",
    "$$ \\mathbb{P}(X = x, Y = y | Z = z) = \\mathbb{P}(X = x | Z = z) \\mathbb{P}(Y = y | Z = z)$$\n",
    "\n",
    "for all $x$, $y$, $z$.  If $X$, $Y$, $Z$ are continuous random variables, we say that $X$ and $Y$ are conditionally independent given $Z$ if\n",
    "\n",
    "$$ f_{X, Y | Z}(x, y | z) = f_{X | Z}(x | z) f_{Y | Z}(y | z) $$\n",
    "\n",
    "for all $x$, $y$, $z$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Intuitively, this means that once you know $Z$, $Y$ provides no extra information about $X$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Theorem 17.2**.  The following implications hold:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "X \\text{ ⫫ } Y \\;|\\; Z & \\Longrightarrow Y \\text{ ⫫ } X \\;|\\; Z \\\\\n",
    "X \\text{ ⫫ } Y \\;|\\; Z \\; \\text{and} \\; U = h(X) & \\Longrightarrow U \\text{ ⫫ } Y \\;|\\; Z \\\\\n",
    "X \\text{ ⫫ } Y \\;|\\; Z \\; \\text{and} \\; U = h(X) & \\Longrightarrow X \\text{ ⫫ } Y \\;|\\; (Z, U)  \\\\\n",
    "X \\text{ ⫫ } Y \\;|\\; Z \\; \\text{and} \\; X \\text{ ⫫ } W \\;|\\; (Y, Z) & \\Longrightarrow X \\text{ ⫫ } (W, Y) \\;|\\; Z \\\\\n",
    "X \\text{ ⫫ } Y \\;|\\; Z \\; \\text{and} \\; X \\text{ ⫫ } Z \\;|\\; Y \\; & \\Longrightarrow Y \\text{ ⫫ } (Y, Z)\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "The last property requires the assumption that all events have positive probability; the first four do not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.2 Undirected Graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An **undirected graph** $\\mathcal{G} = (V, E)$ has a finite set $V$ of **vertices** (or **nodes**) and a set $E$ of **edges** (or **arcs**) consisting of pairs of vertices.  The vertices correspond to random variables $X, Y, Z, \\dots$ and the edges are written as unordered pairs.  For example, $(X, Y) \\in E$ means that $X$ and $Y$ are joined by an edge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"134pt\" height=\"116pt\"\r\n",
       " viewBox=\"0.00 0.00 134.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-112 130,-112 130,4 -4,4\"/>\r\n",
       "<!-- Y -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>Y</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Y</text>\r\n",
       "</g>\r\n",
       "<!-- X -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X</text>\r\n",
       "</g>\r\n",
       "<!-- Y&#45;&#45;X -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>Y&#45;&#45;X</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-72.7646C48.8345,-61.456 41.1103,-46.4367 35.3043,-35.1473\"/>\r\n",
       "</g>\r\n",
       "<!-- Z -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>Z</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Z</text>\r\n",
       "</g>\r\n",
       "<!-- Y&#45;&#45;Z -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>Y&#45;&#45;Z</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-72.7646C77.1655,-61.456 84.8897,-46.4367 90.6957,-35.1473\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c496d8>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('Y', 'X')\n",
    "g.edge('Y', 'Z')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*A graph with vertices $V = \\{X, Y, Z\\}$.  The edge set is $E = \\{(X, Y), (Y, Z)\\}$.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Two vertices are **adjacent**, written $X \\sim Y$, if there is an edge between them.  A sequence $X_0, \\dots, X_n$ is called a **path** if $X_{i-1} \\sim X_i$ for each $i$.  A graph is **complete** if there is an edge between every pair of vertices.  A subset $U \\subset V$ of vertices together with their edges is called a **subgraph**.\n",
    "\n",
    "If $A$, $B$ and $C$ are three distinct subsets in $V$, we say that **$C$ separates $A$ and $B$** if every path from a variable in $A$ to a variable in $B$ intersects a variable in $C$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"134pt\" height=\"188pt\"\r\n",
       " viewBox=\"0.00 0.00 134.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 130,-184 130,4 -4,4\"/>\r\n",
       "<!-- W -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>W</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">W</text>\r\n",
       "</g>\r\n",
       "<!-- X -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"82\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"82\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X</text>\r\n",
       "</g>\r\n",
       "<!-- W&#45;&#45;X -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>W&#45;&#45;X</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M60.6356,-144.411C65.099,-133.252 70.9586,-118.604 75.412,-107.47\"/>\r\n",
       "</g>\r\n",
       "<!-- Y -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>Y</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Y</text>\r\n",
       "</g>\r\n",
       "<!-- W&#45;&#45;Y -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>W&#45;&#45;Y</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M50.7432,-143.871C45.5536,-116.578 35.4652,-63.5205 30.2684,-36.1893\"/>\r\n",
       "</g>\r\n",
       "<!-- X&#45;&#45;Y -->\r\n",
       "<g id=\"edge4\" class=\"edge\"><title>X&#45;&#45;Y</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M70.0658,-73.811C60.8405,-62.0697 48.1304,-45.8932 38.9109,-34.1593\"/>\r\n",
       "</g>\r\n",
       "<!-- Z -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>Z</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Z</text>\r\n",
       "</g>\r\n",
       "<!-- X&#45;&#45;Z -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>X&#45;&#45;Z</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M86.1152,-72.055C88.7487,-61.2111 92.1556,-47.183 94.8046,-36.2753\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c7e240>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('W', 'X')\n",
    "g.edge('W', 'Y')\n",
    "g.edge('X', 'Z')\n",
    "g.edge('X', 'Y')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*$\\{Y, W\\}$ and $\\{Z\\}$ are separated by $\\{X\\}$.  Also, $W$ and $Z$ are separated by $\\{X, Y\\}$.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.3 Probability and Graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $V$ be a set of random variables with distribution $\\mathbb{P}$.  Construct a graph with one vertex for each random variable in $V$.  Suppose we omit the edge between a pair of variables if they are independent given the rest of the variables:\n",
    "\n",
    "$$ \\text{no edge between } X \\text{ and } Y \\Leftrightarrow X \\text{⫫} Y \\;|\\; \\text{rest} $$\n",
    "\n",
    "where \"rest\" refers to all the other variables besides $X$ and $Y$.  This type of graph is called a **pairwise Markov graph**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The graph encodes a set of pairwise conditional independence relations.  These relations imply other conditional independence relations.  Fortunately we can read these other conditional independence relations from the graph as well, as is explained in the next theorem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Theorem 17.3**.  Let $\\mathcal{G} = (V, E)$ be a pairwise Markov graph for a distribution $\\mathbb{P}$.  Let $A$, $B$, and $C$ be distinct subsets of $V$ such that $C$ separates $A$ and $B$.  Then $A \\text{ ⫫ } B \\;|\\; C$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remark:  if $A$ and $B$ are not connected, we can regard them as separated by the empty set.  Then it follows from the theorem that $A \\text{ ⫫ } B$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The independence property in Theorem 17.3 is called the **global Markov property**.  We thus see that the pairwise and global Markov properties are equivalent.\n",
    "\n",
    "More precisely:  given a graph $\\mathcal{G}$, \n",
    "\n",
    "- Let $M_\\text{pair}(\\mathcal{G})$ be the set of distributions that satisfy the pairwise Markov property; thus $\\mathbb{P} \\in M_\\text{pair}(\\mathcal{G})$ if, under $\\mathbb{P}$, $X \\text{⫫} Y \\;|\\; \\text{rest}$ if and only if there is no edge between $X$ and $Y$.\n",
    "- Let $M_\\text{global}(\\mathcal{G})$ be the set of distributions that satisfy the global Markov property; thus $\\mathbb{P} \\in M_\\text{global}(\\mathcal{G})$ if, under $\\mathbb{P}$,  $A \\text{⫫} B \\;|\\; C$ if and only if $C$ separates $A$ and $B$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Theorem 17.5**. Let $\\mathcal{G}$ be a graph.  Then $M_\\text{pair}(\\mathcal{G}) = M_\\text{global}(\\mathcal{G})$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"89pt\" height=\"188pt\"\r\n",
       " viewBox=\"0.00 0.00 89.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 85,-184 85,4 -4,4\"/>\r\n",
       "<!-- X -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X</text>\r\n",
       "</g>\r\n",
       "<!-- Y -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>Y</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Y</text>\r\n",
       "</g>\r\n",
       "<!-- X&#45;&#45;Y -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X&#45;&#45;Y</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M47.6014,-144.411C43.3597,-133.414 37.8106,-119.027 33.5403,-107.956\"/>\r\n",
       "</g>\r\n",
       "<!-- Z -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>Z</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Z</text>\r\n",
       "</g>\r\n",
       "<!-- Y&#45;&#45;Z -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>Y&#45;&#45;Z</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.3986,-72.411C37.6403,-61.4141 43.1894,-47.0274 47.4597,-35.9562\"/>\r\n",
       "</g>\r\n",
       "<!-- Z&#45;&#45;X -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>Z&#45;&#45;X</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.6538,-36.0925C59.6758,-46.4315 61.9808,-59.9098 63,-72 64.3441,-87.9434 64.3441,-92.0566 63,-108 61.9808,-120.09 59.6758,-133.569 57.6538,-143.908\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c7e710>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X', 'Y')\n",
    "g.edge('Y', 'Z')\n",
    "g.edge('Z', 'X')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*No implied independence relations*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"89pt\" height=\"260pt\"\r\n",
       " viewBox=\"0.00 0.00 89.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 85,-256 85,4 -4,4\"/>\r\n",
       "<!-- X -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-230.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X</text>\r\n",
       "</g>\r\n",
       "<!-- Y -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>Y</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Y</text>\r\n",
       "</g>\r\n",
       "<!-- X&#45;&#45;Y -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X&#45;&#45;Y</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M47.6014,-216.411C43.3597,-205.414 37.8106,-191.027 33.5403,-179.956\"/>\r\n",
       "</g>\r\n",
       "<!-- Z -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>Z</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Z</text>\r\n",
       "</g>\r\n",
       "<!-- Y&#45;&#45;Z -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>Y&#45;&#45;Z</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-143.697C27,-132.846 27,-118.917 27,-108.104\"/>\r\n",
       "</g>\r\n",
       "<!-- W -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>W</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">W</text>\r\n",
       "</g>\r\n",
       "<!-- Z&#45;&#45;W -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>Z&#45;&#45;W</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.3986,-72.411C37.6403,-61.4141 43.1894,-47.0274 47.4597,-35.9562\"/>\r\n",
       "</g>\r\n",
       "<!-- W&#45;&#45;X -->\r\n",
       "<g id=\"edge4\" class=\"edge\"><title>W&#45;&#45;X</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.6538,-36.0925C59.6758,-46.4315 61.9808,-59.9098 63,-72 67.0322,-119.83 67.0322,-132.17 63,-180 61.9808,-192.09 59.6758,-205.569 57.6538,-215.908\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c7e978>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X', 'Y')\n",
    "g.edge('Y', 'Z')\n",
    "g.edge('Z', 'W')\n",
    "g.edge('W', 'X')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*$X \\text{ ⫫ } Z \\;|\\; \\{Y, W\\}$ and $Y \\text{ ⫫ } W \\;|\\; \\{X, Z\\}$*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"62pt\" height=\"260pt\"\r\n",
       " viewBox=\"0.00 0.00 62.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 58,-256 58,4 -4,4\"/>\r\n",
       "<!-- X -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-230.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X</text>\r\n",
       "</g>\r\n",
       "<!-- Y -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>Y</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Y</text>\r\n",
       "</g>\r\n",
       "<!-- X&#45;&#45;Y -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X&#45;&#45;Y</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-215.697C27,-204.846 27,-190.917 27,-180.104\"/>\r\n",
       "</g>\r\n",
       "<!-- Z -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>Z</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Z</text>\r\n",
       "</g>\r\n",
       "<!-- Y&#45;&#45;Z -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>Y&#45;&#45;Z</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-143.697C27,-132.846 27,-118.917 27,-108.104\"/>\r\n",
       "</g>\r\n",
       "<!-- W -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>W</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">W</text>\r\n",
       "</g>\r\n",
       "<!-- Z&#45;&#45;W -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>Z&#45;&#45;W</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-71.6966C27,-60.8463 27,-46.9167 27,-36.1043\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c7ec50>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X', 'Y')\n",
    "g.edge('Y', 'Z')\n",
    "g.edge('Z', 'W')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*$X \\text{ ⫫ } Z \\;|\\; Y$ and $Y \\text{ ⫫ } W \\;|\\; Z$*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"134pt\" height=\"116pt\"\r\n",
       " viewBox=\"0.00 0.00 134.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-112 130,-112 130,4 -4,4\"/>\r\n",
       "<!-- Y -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>Y</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Y</text>\r\n",
       "</g>\r\n",
       "<!-- Z -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>Z</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Z</text>\r\n",
       "</g>\r\n",
       "<!-- Y&#45;&#45;Z -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>Y&#45;&#45;Z</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-71.6966C27,-60.8463 27,-46.9167 27,-36.1043\"/>\r\n",
       "</g>\r\n",
       "<!-- X -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X</text>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c89208>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('Y', 'Z')\n",
    "g.node('X')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*$X \\text{ ⫫ } Y$, $X \\text{ ⫫ } Z$ and $X \\text{ ⫫ } (Y, Z)$*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"89pt\" height=\"260pt\"\r\n",
       " viewBox=\"0.00 0.00 89.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 85,-256 85,4 -4,4\"/>\r\n",
       "<!-- Y -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>Y</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Y</text>\r\n",
       "</g>\r\n",
       "<!-- W -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>W</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">W</text>\r\n",
       "</g>\r\n",
       "<!-- Y&#45;&#45;W -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>Y&#45;&#45;W</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M47.6014,-144.411C43.3597,-133.414 37.8106,-119.027 33.5403,-107.956\"/>\r\n",
       "</g>\r\n",
       "<!-- Z -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>Z</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Z</text>\r\n",
       "</g>\r\n",
       "<!-- W&#45;&#45;Z -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>W&#45;&#45;Z</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.3986,-72.411C37.6403,-61.4141 43.1894,-47.0274 47.4597,-35.9562\"/>\r\n",
       "</g>\r\n",
       "<!-- Z&#45;&#45;Y -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>Z&#45;&#45;Y</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.6538,-36.0925C59.6758,-46.4315 61.9808,-59.9098 63,-72 64.3441,-87.9434 64.3441,-92.0566 63,-108 61.9808,-120.09 59.6758,-133.569 57.6538,-143.908\"/>\r\n",
       "</g>\r\n",
       "<!-- X -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>X</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-230.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X</text>\r\n",
       "</g>\r\n",
       "<!-- X&#45;&#45;Y -->\r\n",
       "<g id=\"edge4\" class=\"edge\"><title>X&#45;&#45;Y</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M54,-215.697C54,-204.846 54,-190.917 54,-180.104\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c89a20>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('Y', 'W')\n",
    "g.edge('W', 'Z')\n",
    "g.edge('Z', 'Y')\n",
    "g.edge('X', 'Y')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*$X \\text{ ⫫ } W | (Y, Z)$ and $X \\text{ ⫫ } Z | Y$*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.4  Fitting Graphs to Data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a dataset, how do we find a graphical model that fits the data?  Some authors have devoted whole books to this subject.  We will only treat the discrete case and we will consider a method based on **log-linear models** which are the subject of the next chapter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.6 Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 17.6.1**.  Consider random variables $(X_1, X_2, X_3)$.  In each of the following cases, draw a graph that has the given independence relations.\n",
    "\n",
    "**(i)** $X_1 \\text{ ⫫ } X_3 | X_2$\n",
    "\n",
    "**(ii)** $X_1 \\text{ ⫫ } X_2 | X_3$ and $X_1 \\text{ ⫫ } X_3 | X_2$\n",
    "\n",
    "**(iii)** $X_1 \\text{ ⫫ } X_2 | X_3$ and $X_1 \\text{ ⫫ } X_3 | X_2$ and $X_2 \\text{ ⫫ } X_3 | X_1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(i)** $X_1 \\text{ ⫫ } X_3 | X_2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"62pt\" height=\"188pt\"\r\n",
       " viewBox=\"0.00 0.00 62.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 58,-184 58,4 -4,4\"/>\r\n",
       "<!-- X1 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X1</text>\r\n",
       "</g>\r\n",
       "<!-- X2 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X2</text>\r\n",
       "</g>\r\n",
       "<!-- X1&#45;&#45;X2 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X1&#45;&#45;X2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-143.697C27,-132.846 27,-118.917 27,-108.104\"/>\r\n",
       "</g>\r\n",
       "<!-- X3 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X3</text>\r\n",
       "</g>\r\n",
       "<!-- X2&#45;&#45;X3 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>X2&#45;&#45;X3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-71.6966C27,-60.8463 27,-46.9167 27,-36.1043\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c89cf8>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X1', 'X2')\n",
    "g.edge('X2', 'X3')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(ii)** $X_1 \\text{ ⫫ } X_2 | X_3$ and $X_1 \\text{ ⫫ } X_3 | X_2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"134pt\" height=\"116pt\"\r\n",
       " viewBox=\"0.00 0.00 134.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-112 130,-112 130,4 -4,4\"/>\r\n",
       "<!-- X1 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X1</text>\r\n",
       "</g>\r\n",
       "<!-- X2 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X2</text>\r\n",
       "</g>\r\n",
       "<!-- X3 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X3</text>\r\n",
       "</g>\r\n",
       "<!-- X2&#45;&#45;X3 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X2&#45;&#45;X3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M99,-71.6966C99,-60.8463 99,-46.9167 99,-36.1043\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c89be0>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.node('X1')\n",
    "g.edge('X2', 'X3')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(iii)** $X_1 \\text{ ⫫ } X_2 | X_3$ and $X_1 \\text{ ⫫ } X_3 | X_2$ and $X_2 \\text{ ⫫ } X_3 | X_1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"206pt\" height=\"44pt\"\r\n",
       " viewBox=\"0.00 0.00 206.00 44.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 40)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-40 202,-40 202,4 -4,4\"/>\r\n",
       "<!-- X1 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X1</text>\r\n",
       "</g>\r\n",
       "<!-- X2 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X2</text>\r\n",
       "</g>\r\n",
       "<!-- X3 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X3</text>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c8f320>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.node('X1')\n",
    "g.node('X2')\n",
    "g.node('X3')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 17.6.2**.  Consider random variables $(X_1, X_2, X_3, X_4)$.  In each of the following cases, draw a graph that has the given independence relations.\n",
    "\n",
    "**(a)** $X_1 \\text{ ⫫ } X_3 |  X_2, X_4 $ and $X_1 \\text{ ⫫ } X_4 |  X_2, X_3 $ and $X_2 \\text{ ⫫ } X_4 |  X_1, X_3 $\n",
    "\n",
    "**(b)** $X_1 \\text{ ⫫ } X_2 |  X_3, X_4 $ and $X_1 \\text{ ⫫ } X_3 |  X_2, X_4 $ and $X_2 \\text{ ⫫ } X_3 |  X_1, X_4 $\n",
    "\n",
    "**(c)** $X_1 \\text{ ⫫ } X_3 |  X_2, X_4 $ and $X_2 \\text{ ⫫ } X_4 |  X_1, X_3 $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(a)** $X_1 \\text{ ⫫ } X_3 |  X_2, X_4 $ and $X_1 \\text{ ⫫ } X_4 |  X_2, X_3 $ and $X_2 \\text{ ⫫ } X_4 |  X_1, X_3 $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"62pt\" height=\"260pt\"\r\n",
       " viewBox=\"0.00 0.00 62.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 58,-256 58,4 -4,4\"/>\r\n",
       "<!-- X1 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-230.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X1</text>\r\n",
       "</g>\r\n",
       "<!-- X2 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X2</text>\r\n",
       "</g>\r\n",
       "<!-- X1&#45;&#45;X2 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X1&#45;&#45;X2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-215.697C27,-204.846 27,-190.917 27,-180.104\"/>\r\n",
       "</g>\r\n",
       "<!-- X3 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X3</text>\r\n",
       "</g>\r\n",
       "<!-- X2&#45;&#45;X3 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>X2&#45;&#45;X3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-143.697C27,-132.846 27,-118.917 27,-108.104\"/>\r\n",
       "</g>\r\n",
       "<!-- X4 -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>X4</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X4</text>\r\n",
       "</g>\r\n",
       "<!-- X3&#45;&#45;X4 -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>X3&#45;&#45;X4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-71.6966C27,-60.8463 27,-46.9167 27,-36.1043\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c8f7f0>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X1', 'X2')\n",
    "g.edge('X2', 'X3')\n",
    "g.edge('X3', 'X4')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(b)** $X_1 \\text{ ⫫ } X_2 |  X_3, X_4 $ and $X_1 \\text{ ⫫ } X_3 |  X_2, X_4 $ and $X_2 \\text{ ⫫ } X_3 |  X_1, X_4 $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"206pt\" height=\"116pt\"\r\n",
       " viewBox=\"0.00 0.00 206.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-112 202,-112 202,4 -4,4\"/>\r\n",
       "<!-- X1 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X1</text>\r\n",
       "</g>\r\n",
       "<!-- X4 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X4</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X4</text>\r\n",
       "</g>\r\n",
       "<!-- X1&#45;&#45;X4 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X1&#45;&#45;X4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M41.5703,-74.8345C53.9798,-62.7697 71.7306,-45.5119 84.2043,-33.3847\"/>\r\n",
       "</g>\r\n",
       "<!-- X2 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X2</text>\r\n",
       "</g>\r\n",
       "<!-- X2&#45;&#45;X4 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>X2&#45;&#45;X4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M99,-71.6966C99,-60.8463 99,-46.9167 99,-36.1043\"/>\r\n",
       "</g>\r\n",
       "<!-- X3 -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>X3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X3</text>\r\n",
       "</g>\r\n",
       "<!-- X3&#45;&#45;X4 -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>X3&#45;&#45;X4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M156.43,-74.8345C144.02,-62.7697 126.269,-45.5119 113.796,-33.3847\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c8fac8>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X1', 'X4')\n",
    "g.edge('X2', 'X4')\n",
    "g.edge('X3', 'X4')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(c)** $X_1 \\text{ ⫫ } X_3 |  X_2, X_4 $ and $X_2 \\text{ ⫫ } X_4 |  X_1, X_3 $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"89pt\" height=\"260pt\"\r\n",
       " viewBox=\"0.00 0.00 89.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 85,-256 85,4 -4,4\"/>\r\n",
       "<!-- X1 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-230.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X1</text>\r\n",
       "</g>\r\n",
       "<!-- X2 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X2</text>\r\n",
       "</g>\r\n",
       "<!-- X1&#45;&#45;X2 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X1&#45;&#45;X2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M47.6014,-216.411C43.3597,-205.414 37.8106,-191.027 33.5403,-179.956\"/>\r\n",
       "</g>\r\n",
       "<!-- X4 -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>X4</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X4</text>\r\n",
       "</g>\r\n",
       "<!-- X1&#45;&#45;X4 -->\r\n",
       "<g id=\"edge4\" class=\"edge\"><title>X1&#45;&#45;X4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.6538,-215.908C59.6758,-205.569 61.9808,-192.09 63,-180 67.0322,-132.17 67.0322,-119.83 63,-72 61.9808,-59.9098 59.6758,-46.4315 57.6538,-36.0925\"/>\r\n",
       "</g>\r\n",
       "<!-- X3 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X3</text>\r\n",
       "</g>\r\n",
       "<!-- X2&#45;&#45;X3 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>X2&#45;&#45;X3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-143.697C27,-132.846 27,-118.917 27,-108.104\"/>\r\n",
       "</g>\r\n",
       "<!-- X3&#45;&#45;X4 -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>X3&#45;&#45;X4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.3986,-72.411C37.6403,-61.4141 43.1894,-47.0274 47.4597,-35.9562\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c8ff98>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X1', 'X2')\n",
    "g.edge('X2', 'X3')\n",
    "g.edge('X3', 'X4')\n",
    "g.edge('X1', 'X4')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 17.6.3**.  A conditional independence between a pair of variables is **minimal** if it is not possible to use the Separation Theorem to eliminate any variable from the conditioning set, i.e. from the right side of the bar (Whittaker 1990).  Write down the minimal conditioning independences from the given figures."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(a)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"134pt\" height=\"188pt\"\r\n",
       " viewBox=\"0.00 0.00 134.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 130,-184 130,4 -4,4\"/>\r\n",
       "<!-- X1 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X1</text>\r\n",
       "</g>\r\n",
       "<!-- X2 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X2</text>\r\n",
       "</g>\r\n",
       "<!-- X1&#45;&#45;X2 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X1&#45;&#45;X2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M63,-143.697C63,-132.846 63,-118.917 63,-108.104\"/>\r\n",
       "</g>\r\n",
       "<!-- X3 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X3</text>\r\n",
       "</g>\r\n",
       "<!-- X2&#45;&#45;X3 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>X2&#45;&#45;X3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M54.6504,-72.7646C48.8345,-61.456 41.1103,-46.4367 35.3043,-35.1473\"/>\r\n",
       "</g>\r\n",
       "<!-- X4 -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>X4</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X4</text>\r\n",
       "</g>\r\n",
       "<!-- X2&#45;&#45;X4 -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>X2&#45;&#45;X4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.3496,-72.7646C77.1655,-61.456 84.8897,-46.4367 90.6957,-35.1473\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c8fba8>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X1', 'X2')\n",
    "g.edge('X2', 'X3')\n",
    "g.edge('X2', 'X4')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(b)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"62pt\" height=\"260pt\"\r\n",
       " viewBox=\"0.00 0.00 62.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 58,-256 58,4 -4,4\"/>\r\n",
       "<!-- X1 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-230.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X1</text>\r\n",
       "</g>\r\n",
       "<!-- X2 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X2</text>\r\n",
       "</g>\r\n",
       "<!-- X1&#45;&#45;X2 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X1&#45;&#45;X2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-215.697C27,-204.846 27,-190.917 27,-180.104\"/>\r\n",
       "</g>\r\n",
       "<!-- X3 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X3</text>\r\n",
       "</g>\r\n",
       "<!-- X2&#45;&#45;X3 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>X2&#45;&#45;X3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-143.697C27,-132.846 27,-118.917 27,-108.104\"/>\r\n",
       "</g>\r\n",
       "<!-- X4 -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>X4</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X4</text>\r\n",
       "</g>\r\n",
       "<!-- X3&#45;&#45;X4 -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>X3&#45;&#45;X4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-71.6966C27,-60.8463 27,-46.9167 27,-36.1043\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c9a390>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X1', 'X2')\n",
    "g.edge('X2', 'X3')\n",
    "g.edge('X3', 'X4')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(c)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"89pt\" height=\"260pt\"\r\n",
       " viewBox=\"0.00 0.00 89.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 85,-256 85,4 -4,4\"/>\r\n",
       "<!-- X1 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-230.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X1</text>\r\n",
       "</g>\r\n",
       "<!-- X2 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X2</text>\r\n",
       "</g>\r\n",
       "<!-- X1&#45;&#45;X2 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X1&#45;&#45;X2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M47.6014,-216.411C43.3597,-205.414 37.8106,-191.027 33.5403,-179.956\"/>\r\n",
       "</g>\r\n",
       "<!-- X3 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X3</text>\r\n",
       "</g>\r\n",
       "<!-- X2&#45;&#45;X3 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>X2&#45;&#45;X3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M27,-143.697C27,-132.846 27,-118.917 27,-108.104\"/>\r\n",
       "</g>\r\n",
       "<!-- X4 -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>X4</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X4</text>\r\n",
       "</g>\r\n",
       "<!-- X3&#45;&#45;X4 -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>X3&#45;&#45;X4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.3986,-72.411C37.6403,-61.4141 43.1894,-47.0274 47.4597,-35.9562\"/>\r\n",
       "</g>\r\n",
       "<!-- X4&#45;&#45;X1 -->\r\n",
       "<g id=\"edge4\" class=\"edge\"><title>X4&#45;&#45;X1</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.6538,-36.0925C59.6758,-46.4315 61.9808,-59.9098 63,-72 67.0322,-119.83 67.0322,-132.17 63,-180 61.9808,-192.09 59.6758,-205.569 57.6538,-215.908\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c9a898>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X1', 'X2')\n",
    "g.edge('X2', 'X3')\n",
    "g.edge('X3', 'X4')\n",
    "g.edge('X4', 'X1')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(d)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"147pt\" height=\"332pt\"\r\n",
       " viewBox=\"0.00 0.00 146.88 332.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 328)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-328 142.88,-328 142.88,4 -4,4\"/>\r\n",
       "<!-- X1 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"64\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"64\" y=\"-302.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X1</text>\r\n",
       "</g>\r\n",
       "<!-- X2 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"94\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"94\" y=\"-230.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X2</text>\r\n",
       "</g>\r\n",
       "<!-- X1&#45;&#45;X2 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X1&#45;&#45;X2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.1096,-288.411C75.8918,-277.252 82.1699,-262.604 86.9415,-251.47\"/>\r\n",
       "</g>\r\n",
       "<!-- X3 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X3</text>\r\n",
       "</g>\r\n",
       "<!-- X2&#45;&#45;X3 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>X2&#45;&#45;X3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M80.1176,-218.496C68.6187,-206.482 52.3586,-189.494 40.8647,-177.485\"/>\r\n",
       "</g>\r\n",
       "<!-- X4 -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>X4</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X4</text>\r\n",
       "</g>\r\n",
       "<!-- X2&#45;&#45;X4 -->\r\n",
       "<g id=\"edge4\" class=\"edge\"><title>X2&#45;&#45;X4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M95.236,-215.697C96.011,-204.846 97.0059,-190.917 97.7783,-180.104\"/>\r\n",
       "</g>\r\n",
       "<!-- X3&#45;&#45;X1 -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>X3&#45;&#45;X1</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M31.384,-179.825C38.5013,-207.14 52.4893,-260.824 59.6103,-288.153\"/>\r\n",
       "</g>\r\n",
       "<!-- X5 -->\r\n",
       "<g id=\"node5\" class=\"node\"><title>X5</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"94\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"94\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X5</text>\r\n",
       "</g>\r\n",
       "<!-- X3&#45;&#45;X5 -->\r\n",
       "<g id=\"edge7\" class=\"edge\"><title>X3&#45;&#45;X5</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M40.8824,-146.496C52.3813,-134.482 68.6414,-117.494 80.1353,-105.485\"/>\r\n",
       "</g>\r\n",
       "<!-- X4&#45;&#45;X5 -->\r\n",
       "<g id=\"edge5\" class=\"edge\"><title>X4&#45;&#45;X5</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M97.764,-143.697C96.989,-132.846 95.9941,-118.917 95.2217,-108.104\"/>\r\n",
       "</g>\r\n",
       "<!-- X5&#45;&#45;X2 -->\r\n",
       "<g id=\"edge6\" class=\"edge\"><title>X5&#45;&#45;X2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M109.209,-105.15C118.633,-115.006 129.885,-129.028 135,-144 140.173,-159.141 140.173,-164.859 135,-180 129.885,-194.972 118.633,-208.994 109.209,-218.85\"/>\r\n",
       "</g>\r\n",
       "<!-- X6 -->\r\n",
       "<g id=\"node6\" class=\"node\"><title>X6</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"64\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"64\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X6</text>\r\n",
       "</g>\r\n",
       "<!-- X5&#45;&#45;X6 -->\r\n",
       "<g id=\"edge8\" class=\"edge\"><title>X5&#45;&#45;X6</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M86.8904,-72.411C82.1082,-61.2524 75.8301,-46.6036 71.0585,-35.4699\"/>\r\n",
       "</g>\r\n",
       "<!-- X6&#45;&#45;X3 -->\r\n",
       "<g id=\"edge9\" class=\"edge\"><title>X6&#45;&#45;X3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M59.616,-35.825C52.4987,-63.14 38.5107,-116.824 31.3897,-144.153\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2d0c9a0f0>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X1', 'X2')\n",
    "g.edge('X2', 'X3')\n",
    "g.edge('X3', 'X1')\n",
    "\n",
    "g.edge('X2', 'X4')\n",
    "g.edge('X4', 'X5')\n",
    "g.edge('X5', 'X2')\n",
    "\n",
    "g.edge('X3', 'X5')\n",
    "g.edge('X5', 'X6')\n",
    "g.edge('X6', 'X3')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(a)**\n",
    "\n",
    "- $X_1 \\text{ ⫫ } X_3 |  X_2 $ \n",
    "- $X_1 \\text{ ⫫ } X_4 |  X_2 $ \n",
    "- $X_3 \\text{ ⫫ } X_4 |  X_2 $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(b)**\n",
    "\n",
    "- $X_1 \\text{ ⫫ } X_3 |  X_2 $ \n",
    "- $X_2 \\text{ ⫫ } X_4 |  X_2 $ \n",
    "- $X_1 \\text{ ⫫ } X_4 |  X_2 $ (or $X_1 \\text{ ⫫ } X_4 |  X_3 $)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(c)**\n",
    "\n",
    "- $X_1 \\text{ ⫫ } X_3 |  X_2, X_4 $ \n",
    "- $X_2 \\text{ ⫫ } X_4 |  X_1, X_3 $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(d)**\n",
    "\n",
    "- $X_1 \\text{ ⫫ } X_4 |  X_2, X_3 $ ( or  $X_1 \\text{ ⫫ } X_4 |  X_2, X_5 $ )\n",
    "- $X_1 \\text{ ⫫ } X_5 |  X_2, X_3 $\n",
    "- $X_1 \\text{ ⫫ } X_6 |  X_2, X_3 $ ( or  $X_1 \\text{ ⫫ } X_6 |  X_2, X_5 $ )\n",
    "- $X_2 \\text{ ⫫ } X_6 |  X_3, X_5 $\n",
    "- $X_3 \\text{ ⫫ } X_4 |  X_2, X_5 $\n",
    "- $X_4 \\text{ ⫫ } X_6 |  X_2, X_5 $ ( or  $X_4 \\text{ ⫫ } X_6 |  X_3, X_5 $ )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 17.6.4**. Here are the breast cancer data on diagnosic center ($X_1$), nuclear grade ($X_2$) and survival ($X_3$):\n",
    "\n",
    "$$\n",
    "\\begin{array}{cccccc} \n",
    "    & X_2 & \\text{malignant} & \\text{malignant} & \\text{benign} & \\text{benign}   \\\\\n",
    "    & X_3 & \\text{died}      & \\text{survived}  & \\text{died}   & \\text{survived} \\\\\n",
    "\\hline\n",
    "X_1 & \\text{Boston}    & 35 & 59 & 47 & 112 \\\\\n",
    "    & \\text{Glamorgan} & 42 & 77 & 26 & 76 \\\\\n",
    "\\hline\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "**(a)** Treat this as a multinomial and find the maximum likelihood estimator.\n",
    "\n",
    "**(b)** If someone has a tumour classified as benign at the Glamorgan clinic, what is the estimated probability that they will die?  Find the standard error for this estimate.\n",
    "\n",
    "**(c)** Test the following hypothesis:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "X_1 \\text{ ⫫ } X_2 |  X_3 \\quad &\\text{versus} \\quad \\text{not} (X_1 \\text{ ⫫ } X_2 |  X_3 ) \\\\\n",
    "X_1 \\text{ ⫫ } X_3 |  X_2 \\quad &\\text{versus} \\quad \\text{not} (X_1 \\text{ ⫫ } X_3 |  X_2 ) \\\\\n",
    "X_2 \\text{ ⫫ } X_3 |  X_1 \\quad &\\text{versus} \\quad \\text{not} (X_2 \\text{ ⫫ } X_3 |  X_1 ) \\\\\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Based on the results of your tests, draw and interpret the resulting graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(a)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "X = np.array([[[35, 59], [47, 112]], [[42, 77], [26, 76]]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[[0.07383966, 0.12447257],\n",
       "        [0.09915612, 0.23628692]],\n",
       "\n",
       "       [[0.08860759, 0.16244726],\n",
       "        [0.05485232, 0.16033755]]])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_hat = X / X.sum()\n",
    "\n",
    "p_hat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(b)**  The question asks for $\\mathbb{P}( X_3 = \\text{died} | X_1 = \\text{Glamorgan}, X_2 = \\text{benign})$.  The MLE estimate is:\n",
    "\n",
    "$$\\hat{p} = \\frac{26}{26 + 76} \\approx 0.2594$$\n",
    "\n",
    "The distribution is a binomial distribution on only $X_3$, conditioned on the other variables.\n",
    "\n",
    "The variance is\n",
    "\n",
    "$$\\mathbb{V}(\\hat{p}) = \\frac{1}{n}\\hat{p} (1 - \\hat{p}) = \\frac{1}{26 + 76} \\frac{26}{26 + 76} \\frac{76}{26 + 76}  \\approx 0.001862$$\n",
    "\n",
    "so the standard deviation of this estimate is approximately $0.0431$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(c)**\n",
    "\n",
    "We will test conditional independence $A \\text{ ⫫ } B \\;|\\;  C$ over discrete variables $A$, $B$ and $C$ by testing independence between $A$ and $B$ for each value of $C = c$ and then selecting the largest / worst p-value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.stats import chi2_contingency\n",
    "\n",
    "def get_p_value(table):\n",
    "    # Implement Pearson's chi squared independence test\n",
    "    chi2, p, dof, expected = chi2_contingency(table)\n",
    "    return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X_1 ⫫ X_2 | X_3:  0.030\n",
      "X_1 ⫫ X_3 | X_2:  0.882\n",
      "X_2 ⫫ X_3 | X_1:  0.262\n"
     ]
    }
   ],
   "source": [
    "p_12 = max([get_p_value(X[:, :, k]) for k in range(X.shape[2])])\n",
    "p_13 = max([get_p_value(X[:, k, :]) for k in range(X.shape[1])])\n",
    "p_23 = max([get_p_value(X[k, :, :]) for k in range(X.shape[1])])\n",
    "\n",
    "print(\"X_1 ⫫ X_2 | X_3:  %.3f\" % p_12)\n",
    "print(\"X_1 ⫫ X_3 | X_2:  %.3f\" % p_13)\n",
    "print(\"X_2 ⫫ X_3 | X_1:  %.3f\" % p_23)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At a confidence level of 5%, we can certify the first hypothesis, but not the other two.\n",
    "\n",
    "The resulting graph would be:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"190pt\" height=\"188pt\"\r\n",
       " viewBox=\"0.00 0.00 189.98 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 185.984,-184 185.984,4 -4,4\"/>\r\n",
       "<!-- X1 (diagnostic center) -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>X1 (diagnostic center)</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90.9919\" cy=\"-162\" rx=\"90.9839\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90.9919\" y=\"-158.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X1 (diagnostic center)</text>\r\n",
       "</g>\r\n",
       "<!-- X3 (survival) -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>X3 (survival)</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90.9919\" cy=\"-90\" rx=\"57.6901\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90.9919\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X3 (survival)</text>\r\n",
       "</g>\r\n",
       "<!-- X1 (diagnostic center)&#45;&#45;X3 (survival) -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>X1 (diagnostic center)&#45;&#45;X3 (survival)</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M90.9919,-143.697C90.9919,-132.846 90.9919,-118.917 90.9919,-108.104\"/>\r\n",
       "</g>\r\n",
       "<!-- X2 (nuclear grade) -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>X2 (nuclear grade)</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90.9919\" cy=\"-18\" rx=\"77.9862\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90.9919\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X2 (nuclear grade)</text>\r\n",
       "</g>\r\n",
       "<!-- X3 (survival)&#45;&#45;X2 (nuclear grade) -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>X3 (survival)&#45;&#45;X2 (nuclear grade)</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M90.9919,-71.6966C90.9919,-60.8463 90.9919,-46.9167 90.9919,-36.1043\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x1e2e8dc9da0>"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "g.edge('X1 (diagnostic center)', 'X3 (survival)')\n",
    "g.edge('X3 (survival)', 'X2 (nuclear grade)')\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These results can be interpreted to mean that the nuclear grade is independent of the diagnostic center given the survival -- that is, no diagnostic center is more optimistic or pessimistic in its classification of tumors given their severity."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}