2-3-DTMC-dynamics.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\n",
    "\n",
    "import dtmc\n",
    "import mcviz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DTMC: Section 3 - Markov Chain Dynamics\n",
    "\n",
    "In this section, we will explore how to calculate $m$-step transition probabilities and state the Chapman-Kolmogorov Equations.  This defines the dynamics of a Markov chain.\n",
    "\n",
    "You should be comfortable with the concepts from Section 2:\n",
    "* state space $\\mathcal{S}$\n",
    "* transition probability matrix $\\mathbf{P}$\n",
    "* $m$-step transition probability $\\mathsf{P}\\left(X_{n+m} = j \\,|\\, X_n = i\\right)$\n",
    "* Markov property\n",
    "\n",
    "You should also be familiar with the definition of conditional probability:\n",
    "\n",
    "$$ \\mathsf{P}(A \\,|\\, B) = \\frac{\\mathsf{P}(A \\cap B)}{\\mathsf{P}(B)} $$\n",
    "\n",
    "and idea of “conditioning” on a partition $\\{E_i\\}$ of the sample space $\\Omega$:\n",
    "\n",
    "$$ \\mathsf{P}(A) = \\sum_i \\mathsf{P}(A \\,|\\, E_i) \\mathsf{P}(E_i) $$\n",
    "\n",
    "Consider our original rat in the maze example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "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& 1/2& 0& 1/2\\\\ 1/2& 0& 1/2& 0\\\\ 0& 1/2& 0& 1/2\\\\ 1/2& 0& 1/2& 0}$"
      ],
      "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=\"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\">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=\"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",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</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\">4</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;4 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;4</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",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M38.0778,-106.8327C47.1058,-115.8608 57.735,-126.4899 66.754,-135.5089\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"40.4783,-104.2834 30.9323,-99.6872 35.5285,-109.2332 40.4783,-104.2834\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"64.3347,-138.0394 73.8806,-142.6356 69.2844,-133.0896 64.3347,-138.0394\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M106.8327,-135.4321C115.8608,-126.404 126.4899,-115.7749 135.5089,-106.7559\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"104.2834,-133.0316 99.6872,-142.5776 109.2332,-137.9814 104.2834,-133.0316\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"138.0394,-109.1752 142.6356,-99.6292 133.0896,-104.2254 138.0394,-109.1752\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fbf603386d0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "P = 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",
    "S = [1, 2, 3, 4]\n",
    "\n",
    "dtmc.disp_dtmc(P, S, frac=True)\n",
    "display(mcviz.dot_mc(P, S, bidir=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Two-Step Transition Probabilities\n",
    "\n",
    "How would you calculate the *two*-step transition probability from state 1 to state 3?\n",
    "\n",
    "$$ \\mathsf{P}\\left(X_2 = 3 \\,|\\, X_0 = 1\\right) $$\n",
    "\n",
    "(In words, what is the probability that the rat starts in room 1 and ends up in room 3 after *two* moves?)\n",
    "\n",
    "**Look at all the possible paths.** There are two possible paths: \n",
    "* $X_0 = 1 \\to X_1 = 2 \\to X_2 = 3$\n",
    "  $$\\mathsf{P}(X_2 = 3, X_1 = 2 \\,|\\, X_0 = 1) = \\mathsf{P}(X_2 = 3 \\,|\\, X_0 = 1, X_1 = 2) \\mathsf{P}(X_1 = 2 \\,|\\, X_0 = 1) = 1/4$$\n",
    "  \n",
    "* $X_0 = 1 \\to X_1 = 4 \\to X_2 = 3$\n",
    "  $$\\mathsf{P}(X_2 = 3, X_1 = 2 \\,|\\, X_0 = 1) = \\mathsf{P}(X_2 = 3 \\,|\\, X_0 = 1, X_1 = 2) \\mathsf{P}(X_1 = 2 \\,|\\, X_0 = 1) = 1/4$$\n",
    "\n",
    "So the two-step transition probability is the sum of the probabilities of these two possible paths, or $1/2$.  (Of course, these paths are mutually exclusive -- the rat can be in *either* room 2 or room 4 at time 1.)\n",
    "\n",
    "$$ \\mathsf{P}\\left(X_2 = 3 \\,|\\, X_0 = 1\\right) = 1/2 $$\n",
    "\n",
    "More generally, to find the two-step transition probability from state $i$ to state $j$ for any $i, j \\in \\mathcal{S}$, we consider all paths through the intermediate state $k$:\n",
    "\n",
    "$$\\begin{aligned}\n",
    "     \\mathsf{P}(X_2 = j \\,|\\, X_0 = i) &= \\sum_{k \\in \\mathcal{S}} \\mathsf{P}(X_2 = j,\\ X_1 = k \\,|\\, X_0 = i) &&\\text{(Law of total probability)} \\\\\n",
    "     &= \\sum_{k \\in \\mathcal{S}} \\mathsf{P}(X_1 = k \\,|\\, X_0 = i) \\mathsf{P}(X_2 = j \\,|\\, X_0 = i, X_1 = k) && \\text{(Definition of conditional probability)} \\\\\n",
    "     &= \\sum_{k \\in \\mathcal{S}} \\mathsf{P}(X_1 = k \\,|\\, X_0 = i) \\mathsf{P}(X_2 = j \\,|\\, X_1 = k) && \\text{(Markov property)} \\\\\n",
    "     &= \\sum_{k \\in \\mathcal{S}} p_{ik} p_{kj} \\\\     \n",
    "  \\end{aligned}$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.1\n",
    "\n",
    "Fill out the table of **two-step** transition probabilities\n",
    "\n",
    "| **two-step** trans. prob. | to state 1  | to state 2   | to state 3   | to state 4   |\n",
    "|:--- |:---:|:---:|:---:|:---:|\n",
    "| from state 1 |  1/2 | 0 |  1/2  | 0 | \n",
    "| from state 2 | \n",
    "| from state 3 | \n",
    "| from state 4 | \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chapman-Kolmogorov Equations\n",
    "\n",
    "Let's introduce some more succinct notation for the two-step transition probabilities:\n",
    "\n",
    "$$ p_{ij}^{(2)} \\overset{\\mathsf{def}}{=} \\mathsf{P}\\left(X_2 = j \\,|\\, X_0 = i\\right) $$\n",
    "\n",
    "and write the two-step transition probabilities as a matrix $\\mathbf{P}^{(2)}$ where the $i$th row and $j$th column of the matrix is the two-step transition probability from state $i$ to state $j$:\n",
    "\n",
    "$$\\mathbf{P}^{(2)} = \\begin{pmatrix} \n",
    "    p_{1 1}^{(2)} & p_{1 2}^{(2)} & p_{1 3}^{(2)} & p_{1 4}^{(2)} \\\\\n",
    "    p_{2 1}^{(2)} & p_{2 2}^{(2)} & p_{2 3}^{(2)} & p_{2 4}^{(2)} \\\\\n",
    "    p_{3 1}^{(2)} & p_{3 2}^{(2)} & p_{3 3}^{(2)} & p_{3 4}^{(2)} \\\\\n",
    "    p_{4 1}^{(2)} & p_{4 2}^{(2)} & p_{4 3}^{(2)} & p_{4 4}^{(2)} \\\\\n",
    "  \\end{pmatrix} $$\n",
    "\n",
    "(This is entirely analogous to our notation for the one-step transition probabilities.)\n",
    "\n",
    "The formula we derived for the two-step transition probabilities\n",
    "\n",
    "$$ p_{ij}^{(2)} = \\sum_{k \\in \\mathcal{S}} p_{ik} p_{kj} \\qquad \\text{for any } i, j \\in \\mathcal{S}$$\n",
    "\n",
    "can be written neatly with matrix multiplication\n",
    "\n",
    "$$ \\mathbf{P}^{(2)} = \\mathbf{P} \\cdot \\mathbf{P} $$\n",
    "\n",
    "More generally, for any $m \\geq 1$, we will abbreviate the $m$-step transition probability from state $i$ to state $j$ as\n",
    "\n",
    "$$ p_{ij}^{(m)} \\overset{\\mathsf{def}}{=} \\mathsf{P}\\left(X_m = j \\,|\\, X_0 = i\\right) $$\n",
    "\n",
    "and let $\\mathbf{P}^{(m)}$ be the $m$-step transition probability *matrix*.  Then, for any $n, m \\geq 1$\n",
    "\n",
    "$$ p_{ij}^{(n+m)} = \\sum_{k \\in \\mathcal{S}} p_{ik}^{(n)} p_{kj}^{(m)} $$\n",
    "\n",
    "or in matrix notation\n",
    "\n",
    "$$\\mathbf{P}^{(n+m)} = \\mathbf{P}^{(n)} \\mathbf{P}^{(m)}$$\n",
    "\n",
    "These are known as the **Chapman-Kolmogorov equations** which describe the dynamics of a Markov chain.  (The ones presented here are for a discrete-time Markov chain.  We will see an equivalent for continuous-time Markov chains later in the course.)\n",
    "\n",
    "One practical implication of the Chapman-Kolmogorov equations is that we can easily calculate any $m$-step transition probability matrix from the one-step transition probability matrix $\\mathbf{P}$ by multiplying $\\mathbf{P}$ by itself $m$ times:\n",
    "\n",
    "$$ \\mathbf{P}^{(m)} = \\underbrace{\\mathbf{P} \\cdot \\mathbf{P} \\cdots \\mathbf{P}}_{m \\text{ times}} $$\n",
    "\n",
    "This tells us that the one-step transition probability matrix $\\mathbf{P}$ and state space $\\mathcal{S}$ **completely specify the dynamics of the discrete-time Markov chain**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def example(P, S, m):\n",
    "    dtmc.disp_dtmc(P, S, frac=True)\n",
    "    display(mcviz.dot_mc(P, S, bidir=True))\n",
    "\n",
    "    index = pd.Index(np.arange(1,m))\n",
    "    path = pd.Series(list(map(lambda n: np.linalg.matrix_power(P, n), index)), index)\n",
    "    widgets.interact(lambda y: display(path[y]), y=widgets.IntSlider(value=0, min=min(index), max=max(index), description='step'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "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& 1/2& 0& 1/2\\\\ 1/2& 0& 1/2& 0\\\\ 0& 1/2& 0& 1/2\\\\ 1/2& 0& 1/2& 0}$"
      ],
      "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=\"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\">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=\"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",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</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\">4</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;4 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;4</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",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M38.0778,-106.8327C47.1058,-115.8608 57.735,-126.4899 66.754,-135.5089\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"40.4783,-104.2834 30.9323,-99.6872 35.5285,-109.2332 40.4783,-104.2834\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"64.3347,-138.0394 73.8806,-142.6356 69.2844,-133.0896 64.3347,-138.0394\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M106.8327,-135.4321C115.8608,-126.404 126.4899,-115.7749 135.5089,-106.7559\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"104.2834,-133.0316 99.6872,-142.5776 109.2332,-137.9814 104.2834,-133.0316\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"138.0394,-109.1752 142.6356,-99.6292 133.0896,-104.2254 138.0394,-109.1752\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fbf60daa310>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "dc5c2a1fa49c4c09882ff88fa4f16aca",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=1, description='step', max=39, min=1), Output()), _dom_classes=('widget-…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "S = [1, 2, 3, 4]\n",
    "P = 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",
    "m = 40\n",
    "example(P, S, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "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{1/4& 1/4& 1/2\\\\ 1/2& 0& 1/2\\\\ 1/2& 1/2& 0}$"
      ],
      "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=\"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=\"M12.542,-35.2209C11.1542,-47.9476 10.8844,-65.5281 11.7326,-80.1421\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"8.2472,-80.4645 12.5478,-90.1473 15.2241,-79.896 8.2472,-80.4645\"/>\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=\"M30.1847,-31.3372C40.5125,-38.9024 55.6028,-47.9263 68.6829,-54.4988\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"67.2195,-57.6783 77.7552,-58.7954 70.2157,-51.3519 67.2195,-57.6783\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;1 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M23.458,-90.0944C24.8458,-77.3677 25.1156,-59.7872 24.2674,-45.1732\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"27.7528,-44.8507 23.4522,-35.168 20.7759,-45.4192 27.7528,-44.8507\"/>\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=\"M35.6427,-103.4316C47.3582,-98.2701 62.7183,-89.7135 74.9503,-81.672\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"76.9722,-84.5292 83.2075,-75.9634 72.9915,-78.7712 76.9722,-84.5292\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;1 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>3&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M83.1646,-49.3204C72.8368,-41.7552 57.7465,-32.7313 44.6664,-26.1589\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.1298,-22.9793 35.5941,-21.8622 43.1336,-29.3057 46.1298,-22.9793\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;2 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>3&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M77.7066,-66.5413C65.9911,-71.7028 50.631,-80.2594 38.399,-88.301\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"36.3771,-85.4437 30.1418,-94.0095 40.3578,-91.2017 36.3771,-85.4437\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fbf60dddbd0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "1cadd250e28849808071e4bfabf571f1",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=1, description='step', max=39, min=1), Output()), _dom_classes=('widget-…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "S = [1, 2, 3]\n",
    "P = np.array([[0.25, 0.25, 0.5], [0.5, 0, 0.5], [0.5, 0.5, 0]])\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, bidir=False))\n",
    "\n",
    "m = 40\n",
    "index = pd.Index(np.arange(1,m))\n",
    "path = pd.Series(list(map(lambda n: np.linalg.matrix_power(P, n), index)), index)\n",
    "widgets.interact(lambda y: display(path[y]), y=widgets.IntSlider(value=0, min=min(index), max=max(index), description='step'));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.2\n",
    "\n",
    "For each of the examples above, what do you notice about $\\mathbf{P}^{(m)}$ as you increase $m$?\n",
    "\n",
    "How can you intuitively explain the pattern for the first example (our original four-room maze) and why it does not appear in the second example (the three-room maze)?\n",
    "\n",
    "What happens to $\\mathbf{P}^{(m)}$ for large $m$ in the second example?\n",
    "\n",
    "Looking ahead, this is a preview of *periodic* versus *aperiodic* Markov chains and *convergence to the stationary distribution*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Working in Python (Optional)\n",
    "\n",
    "As you may have picked up in the above examples, you can specify the state space $\\mathcal{S}$ and (one-step) transition probability matrix $\\mathbf{P}$ as variables and use Python to draw the transition diagram and calculate the $m$-step transition probability matrix $\\mathbf{P}^{(m)}$.\n",
    "\n",
    "$\\mathcal{S}$ is specified as a [list](https://docs.python.org/3/tutorial/datastructures.html) and $\\mathbf{P}$ is specified as a [Numpy array](https://docs.scipy.org/doc/numpy/reference/generated/numpy.array.html) (constructed from a Python list of lists).\n",
    "\n",
    "To display a TeX-rendered state space $\\mathcal{S}$\n",
    "```python\n",
    "display(Math(r'\\mathcal{S} = \\{' + ','.join(map(str,S)) + '\\}'))\n",
    "```\n",
    "\n",
    "To display a TeX-rendered transition probability matrix $\\mathbf{P}$\n",
    "```python\n",
    "display(Math(r'\\mathbf{P} = ' + dtmc.pmatrix(P, frac=True)))\n",
    "```\n",
    "(Note: the `frac=True` keyword argument attempts to represent the transition probabilities as fractions with a maximum denominator of 100.  Omit the argument or set it to `False` for decimal representation.)\n",
    "\n",
    "To display the transition diagram\n",
    "```python\n",
    "display(mcviz.dot_mc(P, S, bidir=True))\n",
    "```\n",
    "(Note: the `bidir=True` keyword argument uses two-headed arrows if transitions are possible in both directions rather than two separate one-headed arrows.  This de-clutters the diagram a little bit, but it may make it harder to distinguish between unidirectional and bidirectional transitions.)\n",
    "\n",
    "Finally, to calculate $\\mathbf{P}^{(m)}$, use Numpy's linear algebra package's `matrix_power` function ([documentation](https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.matrix_power.html)).\n",
    "```python\n",
    "np.linalg.matrix_power(P, m)\n",
    "```"
   ]
  }
 ],
 "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
}