2-5-DTMC-structure.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "    <div class=\"bk-root\">\n",
       "        <a href=\"https://bokeh.pydata.org\" target=\"_blank\" class=\"bk-logo bk-logo-small bk-logo-notebook\"></a>\n",
       "        <span id=\"1001\">Loading BokehJS ...</span>\n",
       "    </div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/javascript": [
       "\n",
       "(function(root) {\n",
       "  function now() {\n",
       "    return new Date();\n",
       "  }\n",
       "\n",
       "  var force = true;\n",
       "\n",
       "  if (typeof root._bokeh_onload_callbacks === \"undefined\" || force === true) {\n",
       "    root._bokeh_onload_callbacks = [];\n",
       "    root._bokeh_is_loading = undefined;\n",
       "  }\n",
       "\n",
       "  var JS_MIME_TYPE = 'application/javascript';\n",
       "  var HTML_MIME_TYPE = 'text/html';\n",
       "  var EXEC_MIME_TYPE = 'application/vnd.bokehjs_exec.v0+json';\n",
       "  var CLASS_NAME = 'output_bokeh rendered_html';\n",
       "\n",
       "  /**\n",
       "   * Render data to the DOM node\n",
       "   */\n",
       "  function render(props, node) {\n",
       "    var script = document.createElement(\"script\");\n",
       "    node.appendChild(script);\n",
       "  }\n",
       "\n",
       "  /**\n",
       "   * Handle when an output is cleared or removed\n",
       "   */\n",
       "  function handleClearOutput(event, handle) {\n",
       "    var cell = handle.cell;\n",
       "\n",
       "    var id = cell.output_area._bokeh_element_id;\n",
       "    var server_id = cell.output_area._bokeh_server_id;\n",
       "    // Clean up Bokeh references\n",
       "    if (id != null && id in Bokeh.index) {\n",
       "      Bokeh.index[id].model.document.clear();\n",
       "      delete Bokeh.index[id];\n",
       "    }\n",
       "\n",
       "    if (server_id !== undefined) {\n",
       "      // Clean up Bokeh references\n",
       "      var cmd = \"from bokeh.io.state import curstate; print(curstate().uuid_to_server['\" + server_id + \"'].get_sessions()[0].document.roots[0]._id)\";\n",
       "      cell.notebook.kernel.execute(cmd, {\n",
       "        iopub: {\n",
       "          output: function(msg) {\n",
       "            var id = msg.content.text.trim();\n",
       "            if (id in Bokeh.index) {\n",
       "              Bokeh.index[id].model.document.clear();\n",
       "              delete Bokeh.index[id];\n",
       "            }\n",
       "          }\n",
       "        }\n",
       "      });\n",
       "      // Destroy server and session\n",
       "      var cmd = \"import bokeh.io.notebook as ion; ion.destroy_server('\" + server_id + \"')\";\n",
       "      cell.notebook.kernel.execute(cmd);\n",
       "    }\n",
       "  }\n",
       "\n",
       "  /**\n",
       "   * Handle when a new output is added\n",
       "   */\n",
       "  function handleAddOutput(event, handle) {\n",
       "    var output_area = handle.output_area;\n",
       "    var output = handle.output;\n",
       "\n",
       "    // limit handleAddOutput to display_data with EXEC_MIME_TYPE content only\n",
       "    if ((output.output_type != \"display_data\") || (!output.data.hasOwnProperty(EXEC_MIME_TYPE))) {\n",
       "      return\n",
       "    }\n",
       "\n",
       "    var toinsert = output_area.element.find(\".\" + CLASS_NAME.split(' ')[0]);\n",
       "\n",
       "    if (output.metadata[EXEC_MIME_TYPE][\"id\"] !== undefined) {\n",
       "      toinsert[toinsert.length - 1].firstChild.textContent = output.data[JS_MIME_TYPE];\n",
       "      // store reference to embed id on output_area\n",
       "      output_area._bokeh_element_id = output.metadata[EXEC_MIME_TYPE][\"id\"];\n",
       "    }\n",
       "    if (output.metadata[EXEC_MIME_TYPE][\"server_id\"] !== undefined) {\n",
       "      var bk_div = document.createElement(\"div\");\n",
       "      bk_div.innerHTML = output.data[HTML_MIME_TYPE];\n",
       "      var script_attrs = bk_div.children[0].attributes;\n",
       "      for (var i = 0; i < script_attrs.length; i++) {\n",
       "        toinsert[toinsert.length - 1].firstChild.setAttribute(script_attrs[i].name, script_attrs[i].value);\n",
       "      }\n",
       "      // store reference to server id on output_area\n",
       "      output_area._bokeh_server_id = output.metadata[EXEC_MIME_TYPE][\"server_id\"];\n",
       "    }\n",
       "  }\n",
       "\n",
       "  function register_renderer(events, OutputArea) {\n",
       "\n",
       "    function append_mime(data, metadata, element) {\n",
       "      // create a DOM node to render to\n",
       "      var toinsert = this.create_output_subarea(\n",
       "        metadata,\n",
       "        CLASS_NAME,\n",
       "        EXEC_MIME_TYPE\n",
       "      );\n",
       "      this.keyboard_manager.register_events(toinsert);\n",
       "      // Render to node\n",
       "      var props = {data: data, metadata: metadata[EXEC_MIME_TYPE]};\n",
       "      render(props, toinsert[toinsert.length - 1]);\n",
       "      element.append(toinsert);\n",
       "      return toinsert\n",
       "    }\n",
       "\n",
       "    /* Handle when an output is cleared or removed */\n",
       "    events.on('clear_output.CodeCell', handleClearOutput);\n",
       "    events.on('delete.Cell', handleClearOutput);\n",
       "\n",
       "    /* Handle when a new output is added */\n",
       "    events.on('output_added.OutputArea', handleAddOutput);\n",
       "\n",
       "    /**\n",
       "     * Register the mime type and append_mime function with output_area\n",
       "     */\n",
       "    OutputArea.prototype.register_mime_type(EXEC_MIME_TYPE, append_mime, {\n",
       "      /* Is output safe? */\n",
       "      safe: true,\n",
       "      /* Index of renderer in `output_area.display_order` */\n",
       "      index: 0\n",
       "    });\n",
       "  }\n",
       "\n",
       "  // register the mime type if in Jupyter Notebook environment and previously unregistered\n",
       "  if (root.Jupyter !== undefined) {\n",
       "    var events = require('base/js/events');\n",
       "    var OutputArea = require('notebook/js/outputarea').OutputArea;\n",
       "\n",
       "    if (OutputArea.prototype.mime_types().indexOf(EXEC_MIME_TYPE) == -1) {\n",
       "      register_renderer(events, OutputArea);\n",
       "    }\n",
       "  }\n",
       "\n",
       "  \n",
       "  if (typeof (root._bokeh_timeout) === \"undefined\" || force === true) {\n",
       "    root._bokeh_timeout = Date.now() + 5000;\n",
       "    root._bokeh_failed_load = false;\n",
       "  }\n",
       "\n",
       "  var NB_LOAD_WARNING = {'data': {'text/html':\n",
       "     \"<div style='background-color: #fdd'>\\n\"+\n",
       "     \"<p>\\n\"+\n",
       "     \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n",
       "     \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n",
       "     \"</p>\\n\"+\n",
       "     \"<ul>\\n\"+\n",
       "     \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n",
       "     \"<li>use INLINE resources instead, as so:</li>\\n\"+\n",
       "     \"</ul>\\n\"+\n",
       "     \"<code>\\n\"+\n",
       "     \"from bokeh.resources import INLINE\\n\"+\n",
       "     \"output_notebook(resources=INLINE)\\n\"+\n",
       "     \"</code>\\n\"+\n",
       "     \"</div>\"}};\n",
       "\n",
       "  function display_loaded() {\n",
       "    var el = document.getElementById(\"1001\");\n",
       "    if (el != null) {\n",
       "      el.textContent = \"BokehJS is loading...\";\n",
       "    }\n",
       "    if (root.Bokeh !== undefined) {\n",
       "      if (el != null) {\n",
       "        el.textContent = \"BokehJS \" + root.Bokeh.version + \" successfully loaded.\";\n",
       "      }\n",
       "    } else if (Date.now() < root._bokeh_timeout) {\n",
       "      setTimeout(display_loaded, 100)\n",
       "    }\n",
       "  }\n",
       "\n",
       "\n",
       "  function run_callbacks() {\n",
       "    try {\n",
       "      root._bokeh_onload_callbacks.forEach(function(callback) {\n",
       "        if (callback != null)\n",
       "          callback();\n",
       "      });\n",
       "    } finally {\n",
       "      delete root._bokeh_onload_callbacks\n",
       "    }\n",
       "    console.debug(\"Bokeh: all callbacks have finished\");\n",
       "  }\n",
       "\n",
       "  function load_libs(css_urls, js_urls, callback) {\n",
       "    if (css_urls == null) css_urls = [];\n",
       "    if (js_urls == null) js_urls = [];\n",
       "\n",
       "    root._bokeh_onload_callbacks.push(callback);\n",
       "    if (root._bokeh_is_loading > 0) {\n",
       "      console.debug(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n",
       "      return null;\n",
       "    }\n",
       "    if (js_urls == null || js_urls.length === 0) {\n",
       "      run_callbacks();\n",
       "      return null;\n",
       "    }\n",
       "    console.debug(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n",
       "    root._bokeh_is_loading = css_urls.length + js_urls.length;\n",
       "\n",
       "    function on_load() {\n",
       "      root._bokeh_is_loading--;\n",
       "      if (root._bokeh_is_loading === 0) {\n",
       "        console.debug(\"Bokeh: all BokehJS libraries/stylesheets loaded\");\n",
       "        run_callbacks()\n",
       "      }\n",
       "    }\n",
       "\n",
       "    function on_error() {\n",
       "      console.error(\"failed to load \" + url);\n",
       "    }\n",
       "\n",
       "    for (var i = 0; i < css_urls.length; i++) {\n",
       "      var url = css_urls[i];\n",
       "      const element = document.createElement(\"link\");\n",
       "      element.onload = on_load;\n",
       "      element.onerror = on_error;\n",
       "      element.rel = \"stylesheet\";\n",
       "      element.type = \"text/css\";\n",
       "      element.href = url;\n",
       "      console.debug(\"Bokeh: injecting link tag for BokehJS stylesheet: \", url);\n",
       "      document.body.appendChild(element);\n",
       "    }\n",
       "\n",
       "    for (var i = 0; i < js_urls.length; i++) {\n",
       "      var url = js_urls[i];\n",
       "      var element = document.createElement('script');\n",
       "      element.onload = on_load;\n",
       "      element.onerror = on_error;\n",
       "      element.async = false;\n",
       "      element.src = url;\n",
       "      console.debug(\"Bokeh: injecting script tag for BokehJS library: \", url);\n",
       "      document.head.appendChild(element);\n",
       "    }\n",
       "  };var element = document.getElementById(\"1001\");\n",
       "  if (element == null) {\n",
       "    console.error(\"Bokeh: ERROR: autoload.js configured with elementid '1001' but no matching script tag was found. \")\n",
       "    return false;\n",
       "  }\n",
       "\n",
       "  function inject_raw_css(css) {\n",
       "    const element = document.createElement(\"style\");\n",
       "    element.appendChild(document.createTextNode(css));\n",
       "    document.body.appendChild(element);\n",
       "  }\n",
       "\n",
       "  var js_urls = [\"https://cdn.pydata.org/bokeh/release/bokeh-1.3.4.min.js\", \"https://cdn.pydata.org/bokeh/release/bokeh-widgets-1.3.4.min.js\", \"https://cdn.pydata.org/bokeh/release/bokeh-tables-1.3.4.min.js\", \"https://cdn.pydata.org/bokeh/release/bokeh-gl-1.3.4.min.js\"];\n",
       "  var css_urls = [];\n",
       "\n",
       "  var inline_js = [\n",
       "    function(Bokeh) {\n",
       "      Bokeh.set_log_level(\"info\");\n",
       "    },\n",
       "    \n",
       "    function(Bokeh) {\n",
       "      \n",
       "    },\n",
       "    function(Bokeh) {} // ensure no trailing comma for IE\n",
       "  ];\n",
       "\n",
       "  function run_inline_js() {\n",
       "    \n",
       "    if ((root.Bokeh !== undefined) || (force === true)) {\n",
       "      for (var i = 0; i < inline_js.length; i++) {\n",
       "        inline_js[i].call(root, root.Bokeh);\n",
       "      }if (force === true) {\n",
       "        display_loaded();\n",
       "      }} else if (Date.now() < root._bokeh_timeout) {\n",
       "      setTimeout(run_inline_js, 100);\n",
       "    } else if (!root._bokeh_failed_load) {\n",
       "      console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n",
       "      root._bokeh_failed_load = true;\n",
       "    } else if (force !== true) {\n",
       "      var cell = $(document.getElementById(\"1001\")).parents('.cell').data().cell;\n",
       "      cell.output_area.append_execute_result(NB_LOAD_WARNING)\n",
       "    }\n",
       "\n",
       "  }\n",
       "\n",
       "  if (root._bokeh_is_loading === 0) {\n",
       "    console.debug(\"Bokeh: BokehJS loaded, going straight to plotting\");\n",
       "    run_inline_js();\n",
       "  } else {\n",
       "    load_libs(css_urls, js_urls, function() {\n",
       "      console.debug(\"Bokeh: BokehJS plotting callback run at\", now());\n",
       "      run_inline_js();\n",
       "    });\n",
       "  }\n",
       "}(window));"
      ],
      "application/vnd.bokehjs_load.v0+json": "\n(function(root) {\n  function now() {\n    return new Date();\n  }\n\n  var force = true;\n\n  if (typeof root._bokeh_onload_callbacks === \"undefined\" || force === true) {\n    root._bokeh_onload_callbacks = [];\n    root._bokeh_is_loading = undefined;\n  }\n\n  \n\n  \n  if (typeof (root._bokeh_timeout) === \"undefined\" || force === true) {\n    root._bokeh_timeout = Date.now() + 5000;\n    root._bokeh_failed_load = false;\n  }\n\n  var NB_LOAD_WARNING = {'data': {'text/html':\n     \"<div style='background-color: #fdd'>\\n\"+\n     \"<p>\\n\"+\n     \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n     \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n     \"</p>\\n\"+\n     \"<ul>\\n\"+\n     \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n     \"<li>use INLINE resources instead, as so:</li>\\n\"+\n     \"</ul>\\n\"+\n     \"<code>\\n\"+\n     \"from bokeh.resources import INLINE\\n\"+\n     \"output_notebook(resources=INLINE)\\n\"+\n     \"</code>\\n\"+\n     \"</div>\"}};\n\n  function display_loaded() {\n    var el = document.getElementById(\"1001\");\n    if (el != null) {\n      el.textContent = \"BokehJS is loading...\";\n    }\n    if (root.Bokeh !== undefined) {\n      if (el != null) {\n        el.textContent = \"BokehJS \" + root.Bokeh.version + \" successfully loaded.\";\n      }\n    } else if (Date.now() < root._bokeh_timeout) {\n      setTimeout(display_loaded, 100)\n    }\n  }\n\n\n  function run_callbacks() {\n    try {\n      root._bokeh_onload_callbacks.forEach(function(callback) {\n        if (callback != null)\n          callback();\n      });\n    } finally {\n      delete root._bokeh_onload_callbacks\n    }\n    console.debug(\"Bokeh: all callbacks have finished\");\n  }\n\n  function load_libs(css_urls, js_urls, callback) {\n    if (css_urls == null) css_urls = [];\n    if (js_urls == null) js_urls = [];\n\n    root._bokeh_onload_callbacks.push(callback);\n    if (root._bokeh_is_loading > 0) {\n      console.debug(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n      return null;\n    }\n    if (js_urls == null || js_urls.length === 0) {\n      run_callbacks();\n      return null;\n    }\n    console.debug(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n    root._bokeh_is_loading = css_urls.length + js_urls.length;\n\n    function on_load() {\n      root._bokeh_is_loading--;\n      if (root._bokeh_is_loading === 0) {\n        console.debug(\"Bokeh: all BokehJS libraries/stylesheets loaded\");\n        run_callbacks()\n      }\n    }\n\n    function on_error() {\n      console.error(\"failed to load \" + url);\n    }\n\n    for (var i = 0; i < css_urls.length; i++) {\n      var url = css_urls[i];\n      const element = document.createElement(\"link\");\n      element.onload = on_load;\n      element.onerror = on_error;\n      element.rel = \"stylesheet\";\n      element.type = \"text/css\";\n      element.href = url;\n      console.debug(\"Bokeh: injecting link tag for BokehJS stylesheet: \", url);\n      document.body.appendChild(element);\n    }\n\n    for (var i = 0; i < js_urls.length; i++) {\n      var url = js_urls[i];\n      var element = document.createElement('script');\n      element.onload = on_load;\n      element.onerror = on_error;\n      element.async = false;\n      element.src = url;\n      console.debug(\"Bokeh: injecting script tag for BokehJS library: \", url);\n      document.head.appendChild(element);\n    }\n  };var element = document.getElementById(\"1001\");\n  if (element == null) {\n    console.error(\"Bokeh: ERROR: autoload.js configured with elementid '1001' but no matching script tag was found. \")\n    return false;\n  }\n\n  function inject_raw_css(css) {\n    const element = document.createElement(\"style\");\n    element.appendChild(document.createTextNode(css));\n    document.body.appendChild(element);\n  }\n\n  var js_urls = [\"https://cdn.pydata.org/bokeh/release/bokeh-1.3.4.min.js\", \"https://cdn.pydata.org/bokeh/release/bokeh-widgets-1.3.4.min.js\", \"https://cdn.pydata.org/bokeh/release/bokeh-tables-1.3.4.min.js\", \"https://cdn.pydata.org/bokeh/release/bokeh-gl-1.3.4.min.js\"];\n  var css_urls = [];\n\n  var inline_js = [\n    function(Bokeh) {\n      Bokeh.set_log_level(\"info\");\n    },\n    \n    function(Bokeh) {\n      \n    },\n    function(Bokeh) {} // ensure no trailing comma for IE\n  ];\n\n  function run_inline_js() {\n    \n    if ((root.Bokeh !== undefined) || (force === true)) {\n      for (var i = 0; i < inline_js.length; i++) {\n        inline_js[i].call(root, root.Bokeh);\n      }if (force === true) {\n        display_loaded();\n      }} else if (Date.now() < root._bokeh_timeout) {\n      setTimeout(run_inline_js, 100);\n    } else if (!root._bokeh_failed_load) {\n      console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n      root._bokeh_failed_load = true;\n    } else if (force !== true) {\n      var cell = $(document.getElementById(\"1001\")).parents('.cell').data().cell;\n      cell.output_area.append_execute_result(NB_LOAD_WARNING)\n    }\n\n  }\n\n  if (root._bokeh_is_loading === 0) {\n    console.debug(\"Bokeh: BokehJS loaded, going straight to plotting\");\n    run_inline_js();\n  } else {\n    load_libs(css_urls, js_urls, function() {\n      console.debug(\"Bokeh: BokehJS plotting callback run at\", now());\n      run_inline_js();\n    });\n  }\n}(window));"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "import ipywidgets as widgets\n",
    "from IPython.display import display, Math, Markdown\n",
    "\n",
    "import dtmc\n",
    "import mcviz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DTMC: Section 5 - Markov Chain Structure\n",
    "\n",
    "In this section, we will introduce some notation and terminology to describe the **structure** of a Markov chain.  In Section 3, we saw that dynamics of a discrete-time Markov chain can be deduced entirely from the one-step transition probability matrix $\\mathbf{P}$ (via the Chapman-Kolmogorov equations) and in Section 4, we made these calculations for a specific numerical example (modeling a ride-share driver's path through the Miami area).\n",
    "\n",
    "The content of this section will help us understand the dynamics of a Markov chain more analytically -- just by examining $\\mathbf{P}$ and without having to do any calculations.  Obviously, this leaves out some details of the dynamics, but it is useful as a high-level description.\n",
    "\n",
    "First, we will examine the relationship between states in the state space and describe a useful way of grouping states.  Then, we will characterize each individual state -- in particular whether the Markov chain will visit a state a finite number of times or infinitely often.\n",
    "\n",
    "While we are mathematically defining the concepts below, it is extremely important that you develop an intuitive sense of each concept.  We define these concepts because they are useful"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Accessibility and Communication\n",
    "\n",
    "**Definition:** State $j$ is **accessible from** state $i$ if $p^{(m)}_{ij} > 0$ for some $m \\geq 0$.\n",
    "\n",
    "**Notation:** $i \\rightarrow j$\n",
    "\n",
    "(*Intuition:* It is possible for the Markov chain to reach $j$ starting from $i$.  Not necessarily in one step.)\n",
    "\n",
    "**Definition:** State $i$ and state $j$ **communicate** if $i \\rightarrow j$ and $j \\rightarrow i$ (each is accessible from the other).\n",
    "\n",
    "**Notation:** $i \\leftrightarrow j$\n",
    "\n",
    "(*Intuition:* It is possible for the Markov chain to go back and forth between $i$ and $j$.  Not necessarily in one step.)\n",
    "\n",
    "**Definition:** the set of all states that communicate with each other make up a **communication class** (which is a subset of the state space $\\mathcal{S}$)\n",
    "\n",
    "**Definition:** If all the states of a Markov chain belong to a single communication class, then the Markov chain is **irreducible**.\n",
    "\n",
    "### Remarks\n",
    "\n",
    "Note that the definition of accessibility looks at $m$-step transition probabilities for any $m \\geq 0$:\n",
    "* It may be that $i \\to j$ even if the one-step transition probability $p_{ij} = 0$.  \n",
    "    In other words, multi-step transitions are fine for satisfying accessibility.    \n",
    "* Since we define $\\mathbf{P}^{(0)} = \\mathbf{1}$ (the identity matrix), every state is accessible from itself.\n",
    "* For a finite state-space Markov chain, if state $j$ is accessible from state $i$ then it must be accessible in $|\\mathcal{S}|$ or fewer steps: $p_{ij}^{(m)} > 0$ for some $m \\leq |\\mathcal{S}|$.  \n",
    "    ($|\\mathcal{S}|$ is [cardinality](https://en.wikipedia.org/wiki/Cardinality) of $\\mathcal{S}$: the number of states in the state-space).  \n",
    "\n",
    "    (This last statement is not obvious.  Why is it true?)\n",
    "    \n",
    "Communication is a *transitive* property: if $i \\leftrightarrow j$ and $j \\leftrightarrow k$ then $i \\leftrightarrow k$.  You can prove this easily with the Chapman-Kolmogorov Equations.\n",
    "\n",
    "Regarding communication classes:\n",
    "* Every state belongs to one and only one communication class.\n",
    "* A Markov chain may have one or more communication classes, but no more than $|\\mathcal{S}|$.\n",
    "* The state space $\\mathcal{S}$ can be [partitioned](https://en.wikipedia.org/wiki/Partition_of_a_set) into communication classes.\n",
    "* A communication class contains *all* the states that communicate with each other (not only some).  (A proper subset of a communication class is not a communication class.)\n",
    "* Once the Markov chain leaves a communication class, it can never return.  (Why?)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5.1\n",
    "\n",
    "For each of the following DTMCs, identify whether $i \\rightarrow j$ for every pair of states $i, j \\in \\mathcal{S}$.\n",
    "\n",
    "(There are $|\\mathcal{S}|^2$ pairs although $|\\mathcal{S}|$ are trivial since every state is accessible from itself.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathcal{S} = \\{1,2,3\\}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathbf{P} = \\pmatrix{0& 1& 0\\\\ 0& 0& 1\\\\ 1& 0& 0}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "S = [1,2,3]\n",
    "P = np.array([[0, 1, 0],\n",
    "              [0, 0, 1],\n",
    "              [1, 0, 0]\n",
    "             ])\n",
    "display(Math(r'\\mathcal{S} = \\{' + ','.join(map(str,S)) + '\\}'))\n",
    "display(Math(r'\\mathbf{P} = ' + dtmc.pmatrix(P, frac=True)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathcal{S} = \\{1,2,3\\}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathbf{P} = \\pmatrix{0& 1/2& 1/2\\\\ 1/4& 1/2& 1/4\\\\ 0& 0& 1}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "S = [1,2,3]\n",
    "P = np.array([[0, 0.5, 0.5],\n",
    "              [0.25, 0.5, 0.25],\n",
    "              [0, 0, 1]\n",
    "             ])\n",
    "display(Math(r'\\mathcal{S} = \\{' + ','.join(map(str,S)) + '\\}'))\n",
    "display(Math(r'\\mathbf{P} = ' + dtmc.pmatrix(P, frac=True)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(The DTMC below is randomly generated. Re-run the codeblock to get a new example.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathcal{S} = \\{1,2,3\\}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathbf{P} = \\pmatrix{5/13& 0& 8/13\\\\ 0& 0& 1\\\\ 0& 0& 1}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"116pt\" height=\"116pt\"\n",
       " viewBox=\"0.00 0.00 116.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-112 112,-112 112,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M32.0417,-101.7565C42.9126,-106.1532 54,-102.2344 54,-90 54,-81.5889 48.7595,-77.1081 41.9516,-76.5578\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"41.3132,-73.116 32.0417,-78.2435 42.4871,-80.0169 41.3132,-73.116\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"54\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M26.169,-73.6621C30.6337,-64.7326 36.2625,-53.475 41.2879,-43.4243\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"44.5217,-44.7828 45.8634,-34.2733 38.2607,-41.6523 44.5217,-44.7828\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"90\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M81.831,-73.6621C77.3663,-64.7326 71.7375,-53.475 66.7121,-43.4243\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"69.7393,-41.6523 62.1366,-34.2733 63.4783,-44.7828 69.7393,-41.6523\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;3 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M68.0417,-29.7565C78.9126,-34.1532 90,-30.2344 90,-18 90,-9.5889 84.7595,-5.1081 77.9516,-4.5578\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"77.3132,-1.116 68.0417,-6.2435 78.4871,-8.0169 77.3132,-1.116\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fd8804baad0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "S = [1,2,3]\n",
    "P = dtmc.rand_P(len(S), p=.4)\n",
    "display(Math(r'\\mathcal{S} = \\{' + ','.join(map(str,S)) + '\\}'))\n",
    "display(Math(r'\\mathbf{P} = ' + dtmc.pmatrix(P, frac=True)))\n",
    "display(mcviz.dot_mc(P, S, engine='dot', bidir=True, self_edge=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5.2\n",
    "\n",
    "Show that communication is a transitive property: if $i \\leftrightarrow j$ and $j \\leftrightarrow k$ then $i \\leftrightarrow k$.\n",
    "\n",
    "*Hint:* Pick one direction, say $i \\rightarrow j$ and $j \\rightarrow k$.  This means $p_{ij}^{(n)} > 0$ and $p_{jk}^{(m)} > 0$ for some $n, m \\geq 0$.  Use the Chapman-Kolmogorov equations to show that $i \\rightarrow k$.  The reverse direction is essentially the same argument."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Transience and Recurrence\n",
    "\n",
    "Define the return probability for state $i$, denoted $f_i$, to be the probability that the Markov chain, given that it starts in $i$, *ever* returns to state $i$ at some point in the future.\n",
    "\n",
    "$$ f_i = \\mathsf{P}\\left(\\left.\\bigcup_{m=1}^\\infty \\{X_n = i\\} \\,\\right|\\, X_0=i\\right) = \\mathsf{P}(\\text{ever returns to $i$}\\,|\\,\\text{starts in $i$}) $$\n",
    "\n",
    "**Definition:** State $i$ is **transient** if $f_i < 1$: the return probability is strictly less than 1.  Then the Markov chain will visit this state only a finite number of times (and eventually the Markov chain will leave this state and never return).\n",
    "\n",
    "**Definition:** State $i$ is **recurrent** if $f_i = 1$: the return probability is equal to 1.  Then the Markov chain will visit this state an infinite number of times.\n",
    "\n",
    "Transience and recurrence are **class properties**: all states in a communication class share the same property.  So if one state in a communication class is transient, then all states in that communication class are transient.  Or if one state in a communication class is recurrent, then all states in that communication class are recurrent.  Note that recurrence is defined for a state, but we may sometimes describe a communication class as transient (or recurrent), by which we mean all states in the communication class are transient (or recurrent).\n",
    "\n",
    "Recurrent states can be further classified as either **null recurrent** or **positive recurrent** based on the amount of time it takes for the Markov chain to return (since it returns with probability 1).  This is still a class property.  Define the return time (number of steps) to state $i$ as follows\n",
    "$$\\tau_{ii} = \\begin{cases}\n",
    "    \\infty &\\text{if $X_n \\neq i$ for all $n \\geq 1$} \\\\\n",
    "    \\min\\{n \\geq 1 : X_n = i\\,|\\, X_0 =i\\} & \\text{otherwise}.\n",
    "  \\end{cases}$$\n",
    "Note that $f_i = \\mathsf{P}(\\tau_{ii} < \\infty)$.\n",
    "\n",
    "**Definition:** State $i$ is **positive recurrent** if $\\mathsf{E}[\\tau_{ii}] < \\infty$.\n",
    "\n",
    "**Definition:** State $i$ is **null recurrent** if $\\mathsf{E}[\\tau_{ii}] = \\infty$.\n",
    "\n",
    "**Remark:** For a finite state-space Markov chain ($|\\mathcal{S}| < \\infty$), any recurrent state is positive recurrent and at least one state will be recurrent.  (It is impossible for a state to be null-recurrent and it is impossible for all states to be transient.)  Note that this is not true if the state space is infinite (which we will see with the random walk.\n",
    "\n",
    "**Definition:** A **DTMC is positive recurrent** if it is irreducible and all its states are positive recurrent.\n",
    "\n",
    "This means we are using the term “positive recurrent” in two different ways.  One way applies to an individual state in the DTMC and the other way applies to the entire DTMC.\n",
    "\n",
    "**Result:** If a DTMC has a finite state space ($|\\mathcal{S}| < \\infty$) and is irreducible, then it is positive recurrent.  (This follows from the remark above and the fact that positive recurrence is a class property.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5.3\n",
    "\n",
    "Suppose the return probability for state $i$ is $f_i < 1$, so state $i$ is transient.  Let $G_i$ be the number of times the Markov chain visits state $i$.  $G_i$ is a random variable -- what is its distribution? (Explain.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Absorbing State\n",
    "\n",
    "**Definition:** A state $i$ is **absorbing** if $p_{ii} = 1$.  That is, if the Markov chain ever reaches this state, it never leaves."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5.4\n",
    "\n",
    "Argue that if a state $i$ is absorbing then its communication class is $\\{i\\}$ (contains only itself) and that it is positive recurrent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Periodic and Aperiodic\n",
    "\n",
    "For the original rat-in-the-maze example and the ride-share driver example, what happened with $\\mathbf{P}^{(m)}$ for large $m$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "dc57e4816c1246b59e07ad501629172d",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=1, description='m', max=50, min=1), Output()), _dom_classes=('widget-int…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "P_rat = np.array([[0, 0.5, 0, 0.5],\n",
    "                  [0.5, 0, 0.5, 0],\n",
    "                  [0, 0.5, 0, 0.5],\n",
    "                  [0.5, 0, 0.5, 0]])\n",
    "\n",
    "P_driver = np.array([[0.3, 0.2, 0.4, 0.1],\n",
    "                     [0.4, 0.1, 0.4, 0.1],\n",
    "                     [0.7, 0.2, 0, 0.1],\n",
    "                     [0.5, 0.3, 0.1, 0.1]\n",
    "                    ])\n",
    "\n",
    "m_slider = widgets.IntSlider(value=1, min=1, max=50, description='m')\n",
    "\n",
    "def wrapper(m):\n",
    "    print('Rat in a Maze')\n",
    "    display(np.linalg.matrix_power(P_rat, m))\n",
    "    print('Ride-Share Driver')\n",
    "    display(np.linalg.matrix_power(P_driver, m))\n",
    "\n",
    "widgets.interact(wrapper, m=m_slider);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definition:** A state $j$ has period $d \\geq 2$ if $p_{jj}^{(m)} > 0$ for any $m$ that is an integer multiple of $d$ and $p_{jj}^{(m)} = 0$ otherwise.  That is, it is only possible for the Markov chain to return to state $j$ in a multiple of $d$ steps.  \n",
    "\n",
    "In the case of the rat in the maze, it was only possible to return to a room in an even number of steps, hence every state has a period of $d = 2$.\n",
    "\n",
    "Periodicity (and the period itself) is a class property, so we will say that an irreducible Markov chain is **periodic** if it has some period $d \\geq 2$ and otherwise is it is **aperiodic**.  (For a finite state space periodic Markov chain, $d \\leq |\\mathcal{S}|$.)\n",
    "\n",
    "If we look at $\\mathbf{P}^{(m)}$ for the rat in the maze (which is **periodic** with a period of $2$), the $m$-step transition probability matrix just switches back and forth between two forms:\n",
    "\n",
    "$$\\text{for odd $m$:}\\quad \\mathbf{P}^{(m)} = \\mathbf{P}^{(1)} =\n",
    "  \\begin{pmatrix}\n",
    "    0 & 1/2 & 0 & 1/2 \\\\\n",
    "    1/2 & 0 & 1/2 & 0 \\\\\n",
    "    0 & 1/2 & 0 & 1/2 \\\\\n",
    "    1/2 & 0 & 1/2 & 0\n",
    "  \\end{pmatrix}$$\n",
    "  \n",
    "  \n",
    "$$\\text{for even $m$:}\\quad \\mathbf{P}^{(m)} = \\mathbf{P}^{(2)} =\n",
    "  \\begin{pmatrix}\n",
    "    1/2 & 0 & 1/2 & 0 \\\\\n",
    "    0 & 1/2 & 0 & 1/2 \\\\\n",
    "    1/2 & 0 & 1/2 & 0 \\\\\n",
    "    0 & 1/2 & 0 & 1/2\n",
    "  \\end{pmatrix}$$\n",
    "\n",
    "By contrast, the DTMC representing the ride-share driver is **aperiodic** - there is no such switching behavior.  In fact, each transition probability *converges* to a limit:\n",
    "\n",
    "$$\\lim_{m \\to \\infty} \\mathbf{P}^{(m)} =\n",
    "  \\begin{pmatrix}\n",
    "    0.4448 & 0.1909 & 0.2643 & 0.1 \\\\\n",
    "    0.4448 & 0.1909 & 0.2643 & 0.1 \\\\\n",
    "    0.4448 & 0.1909 & 0.2643 & 0.1 \\\\\n",
    "    0.4448 & 0.1909 & 0.2643 & 0.1\n",
    "  \\end{pmatrix}$$\n",
    "  \n",
    "**This convergence only happens if the DTMC is aperiodic.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5.5\n",
    "\n",
    "For each of the following (rat-in-a-maze examples), determine whether the DTMC below is periodic or aperiodic.  If it is periodic, specify its period.\n",
    "\n",
    "(**Note:** The first two are the same mazes as in Exercise 2.2.  You can also use the randomly-generated mazes to practice.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"152pt\" height=\"44pt\"\n",
       " viewBox=\"0.00 0.00 152.00 44.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 40)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-40 148,-40 148,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"126\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M46.46,-18C62.2878,-18 81.9189,-18 97.718,-18\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.3208,-14.5001 36.3207,-18 46.3207,-21.5001 46.3208,-14.5001\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"97.9499,-21.5001 107.9498,-18 97.9498,-14.5001 97.9499,-21.5001\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fd85067efd0>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = [1,2]\n",
    "P = np.array([[0, 1], [1, 0]])\n",
    "mcviz.dot_mc(P, S, bidir=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"260pt\" height=\"44pt\"\n",
       " viewBox=\"0.00 0.00 260.00 44.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 40)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-40 256,-40 256,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"126\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M46.46,-18C62.2878,-18 81.9189,-18 97.718,-18\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.3208,-14.5001 36.3207,-18 46.3207,-21.5001 46.3208,-14.5001\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"97.9499,-21.5001 107.9498,-18 97.9498,-14.5001 97.9499,-21.5001\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"234\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M154.46,-18C170.2878,-18 189.9189,-18 205.718,-18\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"154.3208,-14.5001 144.3207,-18 154.3207,-21.5001 154.3208,-14.5001\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"205.9499,-21.5001 215.9498,-18 205.9498,-14.5001 205.9499,-21.5001\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fd8506906d0>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = [1,2,3]\n",
    "P = np.array([[0, 1, 0], [0.5, 0, 0.5], [0, 1, 0]])\n",
    "mcviz.dot_mc(P, S, bidir=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"121pt\" height=\"133pt\"\n",
       " viewBox=\"0.00 0.00 121.35 133.32\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 129.3153)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-129.3153 117.3493,-129.3153 117.3493,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-107.3153\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-103.6153\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M18,-46.2355C18,-56.6855 18,-68.5293 18,-78.9875\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"21.5001,-46.0742 18,-36.0743 14.5001,-46.0743 21.5001,-46.0742\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"14.4999,-79.2679 18,-89.2679 21.4999,-79.2678 14.4999,-79.2679\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"95.3493\" cy=\"-62.6576\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"95.3493\" y=\"-58.9576\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M42.4526,-32.1177C51.5026,-37.3427 61.7597,-43.2647 70.8167,-48.4937\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"44.0631,-29.0061 33.6528,-27.0371 40.563,-35.0683 44.0631,-29.0061\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"69.3095,-51.665 79.7198,-53.6339 72.8095,-45.6028 69.3095,-51.665\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M42.4526,-93.1975C51.5026,-87.9725 61.7597,-82.0506 70.8167,-76.8215\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"40.563,-90.247 33.6528,-98.2781 44.0631,-96.3092 40.563,-90.247\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"72.8095,-79.7125 79.7198,-71.6813 69.3095,-73.6503 72.8095,-79.7125\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fd8506907d0>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = [1,2,3]\n",
    "P = np.array([[0, 0.5, 0.5], [0.5, 0, 0.5], [0.5, 0.5, 0]])\n",
    "mcviz.dot_mc(P, S, bidir=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5.6\n",
    "\n",
    "Give an example of a periodic DTMC with period $d = 3$.  (Note that the simplest example will have $|\\mathcal{S}| = 3$.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5.7\n",
    "\n",
    "Suppose an irreducible DTMC has at least one state $i$ with $p_{ii} > 0$.  Then this DTMC must be **aperiodic**.  Why?\n",
    "\n",
    "**Note:** The converse is not true: even if $p_{ii} = 0$ for all $i \\in \\mathcal{S}$, the DTMC is not necessarily periodic."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Recap\n",
    "\n",
    "We've introduced a lot of new terminology and concepts in this Section.  If we've specified the dynamics of a Markov chain with $\\mathbf{P}$ and the Chapman-Kolmogorov equations, what is the point of all of this?  Again, we are looking for **structure**.\n",
    "\n",
    "Consider the following DTMC:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathcal{S} = \\{1,2,3,4,5,6,7,8\\}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathbf{P} = \\pmatrix{7/13& 2/13& 0& 0& 0& 4/13& 0& 0\\\\ 0& 0& 0& 0& 1/3& 1/3& 1/3& 0\\\\ 0& 0& 0& 5/12& 7/12& 0& 0& 0\\\\ 0& 0& 0& 0& 0& 0& 1/2& 1/2\\\\ 1/5& 4/5& 0& 0& 0& 0& 0& 0\\\\ 0& 0& 0& 0& 7/11& 0& 4/11& 0\\\\ 1& 0& 0& 0& 0& 0& 0& 0\\\\ 0& 0& 0& 0& 5/9& 0& 4/9& 0}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "S = list(range(1,9))\n",
    "P = np.array([[7/13,2/13,0,0,0,4/13,0,0],\n",
    "               [0,0,0,0,1/3,1/3,1/3,0],\n",
    "               [0,0,0,5/12,7/12,0,0,0],\n",
    "               [0,0,0,0,0,0,1/2,1/2],\n",
    "               [1/5,4/5,0,0,0,0,0,0],\n",
    "               [0,0,0,0,7/11,0,4/11,0],\n",
    "               [1,0,0,0,0,0,0,0],\n",
    "               [0,0,0,0,5/9,0,4/9,0]])\n",
    "display(Math(r'\\mathcal{S} = \\{' + ','.join(map(str,S)) + '\\}'))\n",
    "display(Math(r'\\mathbf{P} = ' + dtmc.pmatrix(P, frac=True)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While this fully specifies the Markov chain, it doesn't give us much insight into its behavior or dynamics (beyond what one-step transitions are possible).  Looking at the transition diagram is a little more helpful, but it can also appear to be a mess of nodes and edges unless we know what to look for."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"281pt\" height=\"260pt\"\n",
       " viewBox=\"0.00 0.00 280.97 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-256 276.9682,-256 276.9682,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"160.9682\" cy=\"-234\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"160.9682\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M175.01,-245.7565C185.8808,-250.1532 196.9682,-246.2344 196.9682,-234 196.9682,-225.5889 191.7277,-221.1081 184.9198,-220.5578\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"184.2814,-217.116 175.01,-222.2435 185.4553,-224.0169 184.2814,-217.116\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"183.9682\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"183.9682\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M166.5359,-216.5708C169.1915,-208.2575 172.4283,-198.1249 175.3887,-188.8577\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"178.7428,-189.8595 178.4518,-179.2687 172.0748,-187.7294 178.7428,-189.8595\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"137.9682\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"137.9682\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;6 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M158.1017,-216.0535C154.1764,-191.4774 147.0885,-147.1008 142.456,-118.0974\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"145.9043,-117.4955 140.8708,-108.1727 138.9919,-118.5996 145.9043,-117.4955\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"192.9682\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"192.9682\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;5 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>2&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M180.4575,-144.3428C179.4588,-119.5944 182.0154,-74.3665 185.8392,-45.2728\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"189.3058,-45.7553 187.3011,-35.3519 182.3806,-44.7348 189.3058,-45.7553\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;6 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M174.2128,-146.7307C168.1141,-137.1848 160.1307,-124.6891 153.2092,-113.8554\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"156.0429,-111.7899 147.7096,-105.2473 150.1441,-115.5587 156.0429,-111.7899\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"45.9682\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.9682\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;7 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>2&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M168.3517,-152.4811C152.7837,-142.5462 128.7014,-125.9366 110.9682,-108 91.1714,-87.976 72.801,-61.4959 60.6763,-42.4497\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"63.5133,-40.3849 55.247,-33.7577 57.5763,-44.0933 63.5133,-40.3849\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"254.9682\" cy=\"-234\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.9682\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"45.9682\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.9682\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M237.7741,-227.557C228.3949,-224.0745 216.5673,-219.7346 205.9682,-216 159.3106,-199.56 104.647,-181.3316 72.8022,-170.8149\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"73.897,-167.4906 63.3039,-167.6834 71.7051,-174.1386 73.897,-167.4906\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;5 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>3&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M254.3445,-215.8713C252.7716,-185.2369 247.2548,-121.7088 227.9682,-72 223.6808,-60.9498 216.9358,-49.7841 210.5065,-40.4965\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"213.226,-38.2842 204.5296,-32.2324 207.554,-42.3864 213.226,-38.2842\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;7 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>4&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M35.8911,-146.6731C29.6587,-136.2467 22.2433,-121.8736 18.9682,-108 15.2922,-92.428 15.2922,-87.572 18.9682,-72 21.399,-61.7032 26.1104,-51.1312 30.9261,-42.1018\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"34.0127,-43.7539 35.8911,-33.3269 27.9203,-40.3067 34.0127,-43.7539\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"45.9682\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.9682\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;8 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>4&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M45.9682,-143.8314C45.9682,-136.131 45.9682,-126.9743 45.9682,-118.4166\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"49.4683,-118.4132 45.9682,-108.4133 42.4683,-118.4133 49.4683,-118.4132\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;1 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>5&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M199.8522,-34.769C211.168,-64.9514 230.5852,-129.9401 210.9682,-180 205.3961,-194.2193 194.1268,-206.9328 183.6953,-216.4467\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"181.2917,-213.8974 175.9898,-223.0702 185.8548,-219.2058 181.2917,-213.8974\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;2 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>5&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M196.4879,-35.8831C197.458,-60.5741 194.9311,-105.3375 191.146,-134.3547\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"187.6271,-134.228 189.6383,-144.6302 194.553,-135.2443 187.6271,-134.228\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;5 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>6&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M149.0983,-75.4297C156.7023,-65.4754 166.9317,-52.0842 175.5998,-40.7368\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"178.5656,-42.62 181.8547,-32.5486 173.0029,-38.3707 178.5656,-42.62\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M123.5932,-78.75C108.74,-67.1258 85.3606,-48.8288 68.1381,-35.3503\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"70.2744,-32.5778 60.2423,-29.171 65.9602,-38.0904 70.2744,-32.5778\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;1 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>7&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M34.3479,-32.0937C26.6132,-42.4314 17.1343,-57.1932 12.9682,-72 -.0526,-118.2771 -9.9443,-141.5919 18.9682,-180 45.8774,-215.7468 99.4779,-227.83 132.579,-231.9144\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"132.2307,-235.3971 142.546,-232.9793 132.9744,-228.4367 132.2307,-235.3971\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;5 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>8&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M62.2614,-82.0196C87.7584,-69.5313 137.2918,-45.2701 167.5207,-30.4641\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"169.1609,-33.5581 176.602,-26.0161 166.0818,-27.2716 169.1609,-33.5581\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;7 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>8&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M45.9682,-71.8314C45.9682,-64.131 45.9682,-54.9743 45.9682,-46.4166\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"49.4683,-46.4132 45.9682,-36.4133 42.4683,-46.4133 49.4683,-46.4132\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fd8506999d0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "display(mcviz.dot_mc(P, S, engine='dot', bidir=False, self_edge=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What we are looking for is the structure of the Markov chain.  The definitions in this section give us a more organized way of thinking about the states and transitions:\n",
    "* Communication classes are $\\{1, 2, 5, 6, 7\\}$, $\\{3\\}$, $\\{4\\}$, and $\\{8\\}$.\n",
    "* States $1, 2, 5, 6, 7$ are recurrent, the rest are transient.\n",
    "\n",
    "If we draw the transition diagram with communication classes in mind, it is easier to see what the dynamics of the Markov chain will be.  If it starts in any of the transient communication classes, it will end up in the recurrent communication class (after at most three steps) and then circulate among the recurrent states from then on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"277pt\" height=\"292pt\"\n",
       " viewBox=\"0.00 0.00 277.00 292.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 288)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-288 273,-288 273,4 -4,4\"/>\n",
       "<g id=\"clust1\" class=\"cluster\">\n",
       "<title>cluster_0</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"148,-80 148,-132 200,-132 200,-80 148,-80\"/>\n",
       "</g>\n",
       "<g id=\"clust2\" class=\"cluster\">\n",
       "<title>cluster_1</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"209,-224 209,-276 261,-276 261,-224 209,-224\"/>\n",
       "</g>\n",
       "<g id=\"clust3\" class=\"cluster\">\n",
       "<title>cluster_2</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"186,-152 186,-204 238,-204 238,-152 186,-152\"/>\n",
       "</g>\n",
       "<g id=\"clust4\" class=\"cluster\">\n",
       "<title>cluster_3</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"8,-8 8,-276 140,-276 140,-8 8,-8\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"174\" cy=\"-106\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"174\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"48\" cy=\"-34\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"48\" y=\"-30.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;5 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>8&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M160.8745,-93.279C155.8352,-88.766 149.8785,-83.8554 144,-80 137.6621,-75.8434 100.0277,-58.1255 73.8084,-45.9331\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"74.9517,-42.6052 64.4075,-41.5705 72.0051,-48.9548 74.9517,-42.6052\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"114\" cy=\"-34\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114\" y=\"-30.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;7 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>8&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M162.4314,-92.1177C153.7989,-81.7587 141.8421,-67.4105 131.969,-55.5627\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"134.6238,-53.2813 125.5331,-47.8397 129.2462,-57.7626 134.6238,-53.2813\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"235\" cy=\"-250\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"235\" y=\"-246.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"212\" cy=\"-178\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"212\" y=\"-174.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M229.4323,-232.5708C226.7767,-224.2575 223.5399,-214.1249 220.5796,-204.8577\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"223.8934,-203.7294 217.5164,-195.2687 217.2254,-205.8595 223.8934,-203.7294\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;5 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>3&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M238.3565,-232.1585C239.7896,-223.6646 241.2931,-213.3438 242,-204 246.3482,-146.5234 249.5346,-115.3422 204,-80 161.7616,-47.2161 137.5197,-69.5107 87,-52 82.5192,-50.4469 77.8579,-48.5547 73.3824,-46.5876\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"74.5694,-43.2806 64.0234,-42.2646 71.634,-49.6354 74.5694,-43.2806\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;8 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>4&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M203.5666,-162.0209C198.7452,-152.8857 192.5929,-141.2286 187.1502,-130.9162\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"190.1728,-129.1447 182.4099,-121.9345 183.9821,-132.412 190.1728,-129.1447\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;7 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>4&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M215.4163,-160.0443C218.3938,-139.0038 220.0475,-103.9739 204,-80 189.7211,-58.6684 162.3734,-46.6953 141.555,-40.3508\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"142.229,-36.9055 131.6569,-37.5991 140.354,-43.6497 142.229,-36.9055\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"75\" cy=\"-250\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"75\" y=\"-246.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M89.0417,-261.7565C99.9126,-266.1532 111,-262.2344 111,-250 111,-241.5889 105.7595,-237.1081 98.9516,-236.5578\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"98.3132,-233.116 89.0417,-238.2435 99.4871,-240.0169 98.3132,-233.116\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"57\" cy=\"-178\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"57\" y=\"-174.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M70.5506,-232.2022C68.5234,-224.0936 66.0782,-214.3129 63.8262,-205.3049\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"67.2192,-204.4456 61.3983,-195.593 60.4282,-206.1434 67.2192,-204.4456\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"94\" cy=\"-106\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"94\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;6 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M78.8867,-232.1525C80.6353,-223.6573 82.6132,-213.3371 84,-204 87.4768,-180.5916 90.1167,-153.8563 91.8086,-134.2299\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"95.3081,-134.38 92.6503,-124.124 88.3323,-133.799 95.3081,-134.38\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;5 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>2&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M47.1992,-162.6904C45.0157,-153.7539 43.7657,-142.2539 43,-132 41.2134,-108.073 40.1817,-80.7958 41.1159,-61.1053\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"44.6151,-61.2423 41.8449,-51.016 37.6333,-60.7378 44.6151,-61.2423\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;6 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M65.3959,-161.6621C69.9846,-152.7326 75.7698,-141.475 80.9347,-131.4243\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"84.1796,-132.7673 85.6374,-122.2733 77.9536,-129.5678 84.1796,-132.7673\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;7 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>2&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M55.2911,-160.0314C54.126,-139.5951 54.6049,-105.7308 67,-80 72.463,-68.6595 81.9377,-58.5552 90.9555,-50.7256\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"93.427,-53.2272 98.9806,-44.2046 89.0125,-47.7947 93.427,-53.2272\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;1 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>5&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M41.1531,-50.6691C29.3665,-81.9926 8.483,-151.2352 30,-204 34.5864,-215.2468 43.3932,-225.2374 52.0087,-233.0102\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"49.83,-235.751 59.7404,-239.4975 54.3294,-230.3886 49.83,-235.751\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;2 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>5&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M54.848,-51.016C57.8255,-70.5783 58.8825,-103.6421 61,-132 61.4486,-138.0081 62.0635,-144.4441 62.4825,-150.5415\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"59.006,-151.151 62.9467,-160.9857 65.9991,-150.8401 59.006,-151.151\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;5 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>6&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M84.2446,-90.7307C78.1459,-81.1848 70.1625,-68.6891 63.241,-57.8554\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"66.0747,-55.7899 57.7414,-49.2473 60.1759,-59.5587 66.0747,-55.7899\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M98.8414,-88.5708C101.1093,-80.4065 103.8646,-70.4873 106.401,-61.3566\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"109.8296,-62.0902 109.1338,-51.5182 103.085,-60.2166 109.8296,-62.0902\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;1 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>7&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M117.9919,-51.8598C121.7814,-71.6229 126.1894,-104.3381 121,-132 114.7565,-165.2805 99.3784,-201.2219 88.1151,-224.5794\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"84.8641,-223.2583 83.5785,-233.7749 91.1417,-226.3554 84.8641,-223.2583\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fd8804cbb10>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "display(mcviz.more_cluster_mc(P, S, engine='dot', bidir=False, self_edge=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, we can easily see the effect of adding or removing some (one-step) transitions.  (Assuming we renormalize $\\mathbf{P}$ so that the rows sum to 1, including adjusting $p_{ii}$ as needed.)\n",
    "* Add a transition from state $1$ to state $3$ ($p_{13} > 0$): Markov chain becomes irreducible.\n",
    "* Add a transition from state $1$ to state $3$ ($p_{83} > 0$): $\\{3, 4, 8\\}$ becomes a communication class (these states are still transient).\n",
    "* Remove the transition from state $1$ to state $3$ ($p_{71} = 0$): $\\{7\\}$ becomes a communication class (absorbing) and $\\{1, 2, 5, 6\\}$ become transient.\n",
    "\n",
    "The codeblock below implements these changes and re-draws the transition diagram with the new communication classes.  (Uncomment/comment the appropriate lines by removing/adding `#` at the beginning of each line or use the Edit Mode keyboard shortcut.)  Note that Python arrays are indexed from `0` so `P[0,2]` represents $p_{13}$.  If you find this confusing, you can change some code above to `S = list(range(0,8))` to relabel the state space to $\\{0, 1, \\dots, 7\\}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"277pt\" height=\"292pt\"\n",
       " viewBox=\"0.00 0.00 277.00 292.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 288)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-288 273,-288 273,4 -4,4\"/>\n",
       "<g id=\"clust1\" class=\"cluster\">\n",
       "<title>cluster_0</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"148,-80 148,-132 200,-132 200,-80 148,-80\"/>\n",
       "</g>\n",
       "<g id=\"clust2\" class=\"cluster\">\n",
       "<title>cluster_1</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"209,-224 209,-276 261,-276 261,-224 209,-224\"/>\n",
       "</g>\n",
       "<g id=\"clust3\" class=\"cluster\">\n",
       "<title>cluster_2</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"186,-152 186,-204 238,-204 238,-152 186,-152\"/>\n",
       "</g>\n",
       "<g id=\"clust4\" class=\"cluster\">\n",
       "<title>cluster_3</title>\n",
       "<polygon fill=\"none\" stroke=\"#000000\" points=\"8,-8 8,-276 140,-276 140,-8 8,-8\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"174\" cy=\"-106\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"174\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"48\" cy=\"-34\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"48\" y=\"-30.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;5 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>8&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M160.8745,-93.279C155.8352,-88.766 149.8785,-83.8554 144,-80 137.6621,-75.8434 100.0277,-58.1255 73.8084,-45.9331\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"74.9517,-42.6052 64.4075,-41.5705 72.0051,-48.9548 74.9517,-42.6052\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"114\" cy=\"-34\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114\" y=\"-30.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;7 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>8&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M162.4314,-92.1177C153.7989,-81.7587 141.8421,-67.4105 131.969,-55.5627\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"134.6238,-53.2813 125.5331,-47.8397 129.2462,-57.7626 134.6238,-53.2813\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"235\" cy=\"-250\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"235\" y=\"-246.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"212\" cy=\"-178\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"212\" y=\"-174.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M229.4323,-232.5708C226.7767,-224.2575 223.5399,-214.1249 220.5796,-204.8577\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"223.8934,-203.7294 217.5164,-195.2687 217.2254,-205.8595 223.8934,-203.7294\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;5 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>3&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M238.3565,-232.1585C239.7896,-223.6646 241.2931,-213.3438 242,-204 246.3482,-146.5234 249.5346,-115.3422 204,-80 161.7616,-47.2161 137.5197,-69.5107 87,-52 82.5192,-50.4469 77.8579,-48.5547 73.3824,-46.5876\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"74.5694,-43.2806 64.0234,-42.2646 71.634,-49.6354 74.5694,-43.2806\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;8 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>4&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M203.5666,-162.0209C198.7452,-152.8857 192.5929,-141.2286 187.1502,-130.9162\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"190.1728,-129.1447 182.4099,-121.9345 183.9821,-132.412 190.1728,-129.1447\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;7 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>4&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M215.4163,-160.0443C218.3938,-139.0038 220.0475,-103.9739 204,-80 189.7211,-58.6684 162.3734,-46.6953 141.555,-40.3508\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"142.229,-36.9055 131.6569,-37.5991 140.354,-43.6497 142.229,-36.9055\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"75\" cy=\"-250\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"75\" y=\"-246.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M89.0417,-261.7565C99.9126,-266.1532 111,-262.2344 111,-250 111,-241.5889 105.7595,-237.1081 98.9516,-236.5578\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"98.3132,-233.116 89.0417,-238.2435 99.4871,-240.0169 98.3132,-233.116\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"57\" cy=\"-178\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"57\" y=\"-174.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M70.5506,-232.2022C68.5234,-224.0936 66.0782,-214.3129 63.8262,-205.3049\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"67.2192,-204.4456 61.3983,-195.593 60.4282,-206.1434 67.2192,-204.4456\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"94\" cy=\"-106\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"94\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;6 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M78.8867,-232.1525C80.6353,-223.6573 82.6132,-213.3371 84,-204 87.4768,-180.5916 90.1167,-153.8563 91.8086,-134.2299\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"95.3081,-134.38 92.6503,-124.124 88.3323,-133.799 95.3081,-134.38\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;5 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>2&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M47.1992,-162.6904C45.0157,-153.7539 43.7657,-142.2539 43,-132 41.2134,-108.073 40.1817,-80.7958 41.1159,-61.1053\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"44.6151,-61.2423 41.8449,-51.016 37.6333,-60.7378 44.6151,-61.2423\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;6 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M65.3959,-161.6621C69.9846,-152.7326 75.7698,-141.475 80.9347,-131.4243\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"84.1796,-132.7673 85.6374,-122.2733 77.9536,-129.5678 84.1796,-132.7673\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;7 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>2&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M55.2911,-160.0314C54.126,-139.5951 54.6049,-105.7308 67,-80 72.463,-68.6595 81.9377,-58.5552 90.9555,-50.7256\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"93.427,-53.2272 98.9806,-44.2046 89.0125,-47.7947 93.427,-53.2272\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;1 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>5&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M41.1531,-50.6691C29.3665,-81.9926 8.483,-151.2352 30,-204 34.5864,-215.2468 43.3932,-225.2374 52.0087,-233.0102\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"49.83,-235.751 59.7404,-239.4975 54.3294,-230.3886 49.83,-235.751\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;2 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>5&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M54.848,-51.016C57.8255,-70.5783 58.8825,-103.6421 61,-132 61.4486,-138.0081 62.0635,-144.4441 62.4825,-150.5415\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"59.006,-151.151 62.9467,-160.9857 65.9991,-150.8401 59.006,-151.151\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;5 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>6&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M84.2446,-90.7307C78.1459,-81.1848 70.1625,-68.6891 63.241,-57.8554\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"66.0747,-55.7899 57.7414,-49.2473 60.1759,-59.5587 66.0747,-55.7899\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M98.8414,-88.5708C101.1093,-80.4065 103.8646,-70.4873 106.401,-61.3566\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"109.8296,-62.0902 109.1338,-51.5182 103.085,-60.2166 109.8296,-62.0902\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;1 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>7&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M117.9919,-51.8598C121.7814,-71.6229 126.1894,-104.3381 121,-132 114.7565,-165.2805 99.3784,-201.2219 88.1151,-224.5794\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"84.8641,-223.2583 83.5785,-233.7749 91.1417,-226.3554 84.8641,-223.2583\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fd8602de050>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "P_chg = np.copy(P) # Make a copy of the transition probability matrix to change\n",
    "\n",
    "# P_chg[0,2] = 1/13 # Add transition from state 1 to state 3\n",
    "# P_chg[0,0] = 6/13 # Renormalize\n",
    "\n",
    "# P_chg[7,2] = 1/9 # Add transition from state 8 to state 3\n",
    "# P_chg[7,6] = 1/3 # Renormalize\n",
    "\n",
    "# P_chg[6,0] = 0 # Remove transition from state 7 to state 1\n",
    "# P_chg[6,6] = 1 # Renormalize\n",
    "\n",
    "display(mcviz.more_cluster_mc(P_chg, S, engine='dot', bidir=False, self_edge=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By now you've also noticed that to determine the communication classes, you need only to look at which one-step transitions are possible or not possible (that is, whether $p_{ij} > 0$ or $p_{ij} = 0$) -- a more exact value of the transition probabilities do not change the structure.  (This is also why we have not bothered labeling any of the arrows on the transition diagrams.)\n",
    "\n",
    "Recognizing the structure of a Markov chain is a skill that you should develop.  As with most skills, it requires practice and there are a variety of techniques you can use (inspecting $\\mathbf{P}$, drawing and examining the transition digram, numerical calculations).  Your skills will be stronger if you have a wider range of techniques you are comfortable with.  While I've provided some tools to help you (e.g., Python funcitons to draw the transition diagram, identify communication classes), be wary of becoming dependent on them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Practice Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5.8\n",
    "\n",
    "For each of the Markov chains below, identify the communication classes and determine whether each state is transient or recurrent.  Identify any absorbing states."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathcal{S} = \\{1,2,3,4\\}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathbf{P} = \\pmatrix{0.3& 0.2& 0.4& 0.1\\\\ 0.4& 0.1& 0.4& 0.1\\\\ 0.7& 0.2& 0.0& 0.1\\\\ 0.5& 0.3& 0.1& 0.1}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"182pt\" height=\"182pt\"\n",
       " viewBox=\"0.00 0.00 181.51 181.51\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 177.5099)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-177.5099 177.5099,-177.5099 177.5099,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"86.7549\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"86.7549\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"155.5099\" cy=\"-86.7549\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"155.5099\" y=\"-83.0549\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M106.8327,-38.0778C115.8608,-47.1058 126.4899,-57.735 135.5089,-66.754\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"109.2332,-35.5285 99.6872,-30.9323 104.2834,-40.4783 109.2332,-35.5285\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"133.0896,-69.2844 142.6356,-73.8806 138.0394,-64.3347 133.0896,-69.2844\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"86.7549\" cy=\"-155.5099\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"86.7549\" y=\"-151.8099\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M86.7549,-46.3411C86.7549,-69.9564 86.7549,-103.4331 86.7549,-127.0746\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"90.255,-46.2602 86.7549,-36.2602 83.255,-46.2603 90.255,-46.2602\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"83.255,-127.1741 86.7549,-137.1741 90.255,-127.1741 83.255,-127.1741\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-86.7549\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-83.0549\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;4 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M66.6772,-38.0778C57.6491,-47.1058 47.0199,-57.735 38.001,-66.754\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"69.2264,-40.4783 73.8227,-30.9323 64.2767,-35.5285 69.2264,-40.4783\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"35.4705,-64.3347 30.8743,-73.8806 40.4203,-69.2844 35.4705,-64.3347\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M135.4321,-106.8327C126.404,-115.8608 115.7749,-126.4899 106.7559,-135.5089\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"137.9814,-109.2332 142.5776,-99.6872 133.0316,-104.2834 137.9814,-109.2332\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"104.2254,-133.0896 99.6292,-142.6356 109.1752,-138.0394 104.2254,-133.0896\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;4 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M127.1688,-86.7549C103.5535,-86.7549 70.0768,-86.7549 46.4353,-86.7549\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"127.2497,-90.255 137.2496,-86.7549 127.2496,-83.255 127.2497,-90.255\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.3358,-83.255 36.3358,-86.7549 46.3357,-90.255 46.3358,-83.255\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M66.6772,-135.4321C57.6491,-126.404 47.0199,-115.7749 38.001,-106.7559\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"64.2767,-137.9814 73.8227,-142.5776 69.2264,-133.0316 64.2767,-137.9814\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"40.4203,-104.2254 30.8743,-99.6292 35.4705,-109.1752 40.4203,-104.2254\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fd8506a0b90>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "S = [1, 2, 3, 4]\n",
    "P = np.array([[0.3, 0.2, 0.4, 0.1],\n",
    "              [0.4, 0.1, 0.4, 0.1],\n",
    "              [0.7, 0.2, 0, 0.1],\n",
    "              [0.5, 0.3, 0.1, 0.1]\n",
    "             ])\n",
    "dtmc.disp_dtmc(P, S)\n",
    "display(mcviz.dot_mc(P, S, bidir=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathcal{S} = \\{1,2,3,4\\}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathbf{P} = \\pmatrix{0.3& 0.7& 0.0& 0.0\\\\ 0.8& 0.2& 0.0& 0.0\\\\ 0.0& 0.0& 0.5& 0.5\\\\ 0.0& 0.0& 0.5& 0.5}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"280pt\" height=\"104pt\"\n",
       " viewBox=\"0.00 0.00 280.00 104.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 100)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-100 276,-100 276,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M35.0373,-24.3792C44.8579,-25.6811 54,-23.5547 54,-18 54,-14.5283 50.4289,-12.3958 45.3529,-11.6025\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"45.031,-8.1029 35.0373,-11.6208 45.0435,-15.1029 45.031,-8.1029\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"126\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M46.46,-18C62.2878,-18 81.9189,-18 97.718,-18\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.3208,-14.5001 36.3207,-18 46.3207,-21.5001 46.3208,-14.5001\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"97.9499,-21.5001 107.9498,-18 97.9498,-14.5001 97.9499,-21.5001\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M143.0373,-24.3792C152.8579,-25.6811 162,-23.5547 162,-18 162,-14.5283 158.4289,-12.3958 153.3529,-11.6025\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"153.031,-8.1029 143.0373,-11.6208 153.0435,-15.1029 153.031,-8.1029\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"128\" cy=\"-78\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"128\" y=\"-74.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;3 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M145.0373,-84.3792C154.8579,-85.6811 164,-83.5547 164,-78 164,-74.5283 160.4289,-72.3958 155.3529,-71.6025\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"155.031,-68.1029 145.0373,-71.6208 155.0435,-75.1029 155.031,-68.1029\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"236\" cy=\"-78\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"236\" y=\"-74.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M156.46,-78C172.2878,-78 191.9189,-78 207.718,-78\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"156.3208,-74.5001 146.3207,-78 156.3207,-81.5001 156.3208,-74.5001\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"207.9499,-81.5001 217.9498,-78 207.9498,-74.5001 207.9499,-81.5001\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;4 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>4&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M253.0373,-84.3792C262.8579,-85.6811 272,-83.5547 272,-78 272,-74.5283 268.4289,-72.3958 263.3529,-71.6025\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"263.031,-68.1029 253.0373,-71.6208 263.0435,-75.1029 263.031,-68.1029\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fd8506b0810>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "S = [1, 2, 3, 4]\n",
    "P = np.array([[0.3, 0.7, 0, 0],\n",
    "              [0.8, 0.2, 0, 0],\n",
    "              [0, 0, 0.5, 0.5],\n",
    "              [0, 0, 0.5, 0.5]\n",
    "             ])\n",
    "dtmc.disp_dtmc(P, S)\n",
    "display(mcviz.dot_mc(P, S,bidir=True, self_edge=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathcal{S} = \\{1,2,3,4\\}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathbf{P} = \\pmatrix{0.3& 0.7& 0.0& 0.0\\\\ 0.8& 0.1& 0.1& 0.0\\\\ 0.0& 0.0& 0.5& 0.5\\\\ 0.0& 0.0& 0.5& 0.5}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"386pt\" height=\"44pt\"\n",
       " viewBox=\"0.00 0.00 386.00 44.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 40)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-40 382,-40 382,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M35.0373,-24.3792C44.8579,-25.6811 54,-23.5547 54,-18 54,-14.5283 50.4289,-12.3958 45.3529,-11.6025\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"45.031,-8.1029 35.0373,-11.6208 45.0435,-15.1029 45.031,-8.1029\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"126\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M46.46,-18C62.2878,-18 81.9189,-18 97.718,-18\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.3208,-14.5001 36.3207,-18 46.3207,-21.5001 46.3208,-14.5001\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"97.9499,-21.5001 107.9498,-18 97.9498,-14.5001 97.9499,-21.5001\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M143.0373,-24.3792C152.8579,-25.6811 162,-23.5547 162,-18 162,-14.5283 158.4289,-12.3958 153.3529,-11.6025\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"153.031,-8.1029 143.0373,-11.6208 153.0435,-15.1029 153.031,-8.1029\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"234\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M144.3207,-18C161.179,-18 186.4349,-18 205.853,-18\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"205.9499,-21.5001 215.9498,-18 205.9498,-14.5001 205.9499,-21.5001\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>3&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M251.0373,-24.3792C260.8579,-25.6811 270,-23.5547 270,-18 270,-14.5283 266.4289,-12.3958 261.3529,-11.6025\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"261.031,-8.1029 251.0373,-11.6208 261.0435,-15.1029 261.031,-8.1029\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"342\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"342\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M262.46,-18C278.2878,-18 297.9189,-18 313.718,-18\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"262.3208,-14.5001 252.3207,-18 262.3207,-21.5001 262.3208,-14.5001\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"313.9499,-21.5001 323.9498,-18 313.9498,-14.5001 313.9499,-21.5001\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;4 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>4&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M359.0373,-24.3792C368.8579,-25.6811 378,-23.5547 378,-18 378,-14.5283 374.4289,-12.3958 369.3529,-11.6025\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"369.031,-8.1029 359.0373,-11.6208 369.0435,-15.1029 369.031,-8.1029\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fd8506b0f90>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "S = [1, 2, 3, 4]\n",
    "P = np.array([[0.3, 0.7, 0, 0],\n",
    "              [0.8, 0.1, 0.1, 0],\n",
    "              [0, 0, 0.5, 0.5],\n",
    "              [0, 0, 0.5, 0.5]\n",
    "             ])\n",
    "dtmc.disp_dtmc(P, S)\n",
    "display(mcviz.dot_mc(P, S, bidir=True, self_edge=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathcal{S} = \\{1,2,3,4\\}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathbf{P} = \\pmatrix{1.0& 0.0& 0.0& 0.0\\\\ 0.4& 0.1& 0.4& 0.1\\\\ 0.7& 0.2& 0.0& 0.1\\\\ 0.5& 0.3& 0.1& 0.1}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"200pt\" height=\"182pt\"\n",
       " viewBox=\"0.00 0.00 199.51 181.51\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 177.5099)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-177.5099 195.5099,-177.5099 195.5099,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"86.7549\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"86.7549\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M103.7922,-24.3792C113.6128,-25.6811 122.7549,-23.5547 122.7549,-18 122.7549,-14.5283 119.1838,-12.3958 114.1079,-11.6025\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"113.786,-8.1029 103.7922,-11.6208 113.7985,-15.1029 113.786,-8.1029\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"155.5099\" cy=\"-86.7549\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"155.5099\" y=\"-83.0549\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>2&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M142.5776,-73.8227C132.4941,-63.7391 118.312,-49.5571 106.7662,-38.0113\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"109.1752,-35.4705 99.6292,-30.8743 104.2254,-40.4203 109.1752,-35.4705\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M172.5472,-93.1341C182.3678,-94.436 191.5099,-92.3096 191.5099,-86.7549 191.5099,-83.2833 187.9387,-81.1507 182.8628,-80.3574\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"182.5409,-76.8579 172.5472,-80.3757 182.5534,-83.8579 182.5409,-76.8579\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"86.7549\" cy=\"-155.5099\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"86.7549\" y=\"-151.8099\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M135.4321,-106.8327C126.404,-115.8608 115.7749,-126.4899 106.7559,-135.5089\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"137.9814,-109.2332 142.5776,-99.6872 133.0316,-104.2834 137.9814,-109.2332\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"104.2254,-133.0896 99.6292,-142.6356 109.1752,-138.0394 104.2254,-133.0896\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-86.7549\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-83.0549\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;4 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M127.1688,-86.7549C103.5535,-86.7549 70.0768,-86.7549 46.4353,-86.7549\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"127.2497,-90.255 137.2496,-86.7549 127.2496,-83.255 127.2497,-90.255\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.3358,-83.255 36.3358,-86.7549 46.3357,-90.255 46.3358,-83.255\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;1 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>3&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M86.7549,-137.2496C86.7549,-114.0311 86.7549,-73.6901 86.7549,-46.4296\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"90.255,-46.3357 86.7549,-36.3358 83.255,-46.3358 90.255,-46.3357\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M66.6772,-135.4321C57.6491,-126.404 47.0199,-115.7749 38.001,-106.7559\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"64.2767,-137.9814 73.8227,-142.5776 69.2264,-133.0316 64.2767,-137.9814\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"40.4203,-104.2254 30.8743,-99.6292 35.4705,-109.1752 40.4203,-104.2254\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;1 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>4&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M30.9323,-73.8227C41.0158,-63.7391 55.1978,-49.5571 66.7436,-38.0113\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"69.2844,-40.4203 73.8806,-30.8743 64.3347,-35.4705 69.2844,-40.4203\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;4 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>4&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M35.0373,-93.1341C44.8579,-94.436 54,-92.3096 54,-86.7549 54,-83.2833 50.4289,-81.1507 45.3529,-80.3574\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"45.031,-76.8579 35.0373,-80.3757 45.0435,-83.8579 45.031,-76.8579\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fd8506dd490>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "S = [1, 2, 3, 4]\n",
    "P = np.array([[1, 0, 0, 0],\n",
    "              [0.4, 0.1, 0.4, 0.1],\n",
    "              [0.7, 0.2, 0, 0.1],\n",
    "              [0.5, 0.3, 0.1, 0.1]\n",
    "             ])\n",
    "dtmc.disp_dtmc(P, S)\n",
    "display(mcviz.dot_mc(P, S, bidir=True, self_edge=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5.9\n",
    "\n",
    "For the Markov chain below, identify the communication classes and determine whether each state is transient or recurrent.  Identify any absorbing states.\n",
    "\n",
    "**Note:** The example below is randomly generated.  You can re-reun the code blocks to get different examples.  You can also change the size of the state space `dim` and the keyword argument `p`.  Values of `p` closer to 1 will tend to decrease the number of communication classes while values of `p` closer to 0 will tend to increase the number of communication classes.  (`p` represents the probability that any one-step transition probability is non-zero.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "dim = 5 # size of state space\n",
    "S = range(1,dim+1)\n",
    "P = dtmc.rand_P(dim, p=1.5/dim)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathcal{S} = \\{1,2,3,4,5\\}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathbf{P} = \\pmatrix{1/2& 1/2& 0& 0& 0\\\\ 9/17& 0& 0& 0& 8/17\\\\ 7/17& 7/17& 0& 0& 3/17\\\\ 0& 0& 1/10& 9/10& 0\\\\ 0& 1& 0& 0& 0}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "dtmc.disp_dtmc(P, S, frac=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** You can use the following functions to check the communication classes:\n",
    "* `dtmc.comm_class(P)` will return a list of sets representing the communication classes.  The only input argument is the transition probability matrix `P`.  This assumes a state space of $\\{0, 1, 2, \\dots, |\\mathcal{S}|-1\\}$.\n",
    "* `mcviz.more_cluster_mc(P, S, engine='dot')` will draw a transition diagram where the communication classes are clustered and contained in boxes.  You may include keyword arguments `bidir` and `self_edge` as before (with the `mcviz.dot_mc` function)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5.10\n",
    "\n",
    "For each of the following, come up with an example of a DTMC that has the structure described.  (You do not necessarily have to specify $\\mathbf{P}$ completely, but enough to draw a transition diagram.  However, you should be able to completely specify a valid $\\mathbf{P}$ if asked.)\n",
    "\n",
    "Let $\\{X_n, n \\geq 0\\}$ be a discrete-time Markov chain on state space $\\mathcal{S} = \\{1, 2, 3, 4\\}$.  For each of the following, come up with an example of a DTMC that has the structure described. **If it is impossible** to have such a DTMC, state as simply as possible why not.\n",
    "\n",
    "**Note:** Each part lists the communication classes and the states in each communication class are described as either recurrent or transient.  For example:\n",
    "<center> $\\{1, 2\\}$ are transient, $\\{3, 4\\}$ are recurrent. </center>\n",
    "means that $\\{1, 2\\}$ is a communication class and both states are transient, and $\\{3, 4\\}$ is a communication class and both states are transient.\n",
    "\n",
    "1. $\\{1, 2\\}$ are transient, $\\{3, 4\\}$ are recurrent.\n",
    "1. $\\{1, 2\\}$ are recurrent, $\\{3, 4\\}$ are recurrent.\n",
    "1. $\\{1, 2\\}$ are transient, $\\{3, 4\\}$ are transient.\n",
    "1. $\\{1, 2, 3, 4\\}$ are recurrent.\n",
    "1. $\\{1\\}$ is transient, $\\{3\\}$ is transient, $\\{2, 4\\}$ are recurrent.\n",
    "1. $\\{1\\}$ is recurrent, $\\{3\\}$ is recurrent, $\\{2, 4\\}$ are transient.\n",
    "1. $\\{1\\}$ is transient, $\\{2, 3, 4\\}$ are recurrent.\n",
    "1. $\\{1\\}$ is recurrent, $\\{2, 3, 4\\}$ are transient.\n",
    "1. The communication classes are $\\{1\\}$, $\\{2, 3\\}$, $\\{4\\}$ and either state 1 or 4 is absorbing, but not both.  In your example, which states are recurrent and which are transient?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5.11\n",
    "\n",
    "Come up with an example of a DTMC on the state space $\\mathcal{S}$ specified that has the structure described.\n",
    "\n",
    "(This is randomly generated, so you can re-run the codeblock to generate another exercise.  Change the variable `dim` to change $|\\mathcal{S}|$.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathcal{S} = \\{1,2,3,4\\}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/markdown": [
       "$\\{1\\}$ is recurrent, $\\{2\\}$ is transient, $\\{3\\}$ is transient, $\\{4\\}$ is recurrent."
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "dim = 4\n",
    "display(Math(r'\\mathcal{S} = \\{'+','.join(map(str, range(1,dim+1)))+'\\}'))\n",
    "display(Markdown(dtmc.rand_struct_exercise(dim)))"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}