2-6-DTMC-stationary.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": "code",
   "execution_count": 2,
   "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=\"1002\">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(\"1002\");\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(\"1002\");\n",
       "  if (element == null) {\n",
       "    console.error(\"Bokeh: ERROR: autoload.js configured with elementid '1002' 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(\"1002\")).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(\"1002\");\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(\"1002\");\n  if (element == null) {\n    console.error(\"Bokeh: ERROR: autoload.js configured with elementid '1002' 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(\"1002\")).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 bokeh.plotting as bplt\n",
    "from bokeh.models import Range1d, LabelSet, ColumnDataSource\n",
    "from bokeh.models.glyphs import VBar\n",
    "from bokeh.io import output_notebook, push_notebook\n",
    "output_notebook()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DTMC: Section 6 - The Stationary Distribution\n",
    "\n",
    "In Section 5 we learned how to organize a Markov chain into communication classes and classify each state as recurrent or transient.  For a communication class whose states are transient, the Markov chain will move among the states in the class for some finite (but random) period of time before leaving and never returning.  For a communication class whose states are recurrent, the Markov chain will continue to move among the states in that class forever (and never leave the communication class)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Long-Run Proportion of Time Spent in a State\n",
    "\n",
    "Consider the ride-share driver example from Section 4.  What proportion of his passengers' destinations are in Coral Gables?  Clearly this is subject to random fluctuations, but we might expect that, over the long-run this will stabilize to some value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mathematically, we write this as:\n",
    "\n",
    "$$ \\text{long-run proportion of passengers going to Coral Gables} = \\lim_{n \\to \\infty} \\frac{1}{n} \\sum_{k=1}^n \\mathbf{1}\\{X_k = 1\\} $$\n",
    "\n",
    "where $\\mathbf{1}\\{\\cdot\\}$ is the indicator random variable.  Given a probability space $(\\Omega, \\mathcal{F}, \\mathsf{P})$ and event $A \\in \\mathcal{F}$, the random variable $\\mathbf{1}\\{A\\} : \\Omega \\to [0, 1]$ is defined to be\n",
    "$$\\mathbf{1}\\{A\\}(\\omega) \\overset{\\mathsf{def}}{=} \\begin{cases}\n",
    "    1 & \\text{if } \\omega \\in A \\\\\n",
    "    0 & \\text{otherwise}\n",
    "  \\end{cases}$$\n",
    "  \n",
    "You can think of $\\sum_{k=1}^n \\mathbf{1}\\{X_k = 1\\}$ as a simple counter: it adds $1$ when the Markov chain visits state $1$ (the $k$th passenger goes to Coral Gables) and ignores the other states (adds $0$ otherwise).  Dividing the sum by $n$ (total time steps) normalizes this to the proportion of visits.  Taking the limit as $n \\to \\infty$ considers the long-run.  \n",
    "\n",
    "For a general DTMC on state space $\\mathcal{S}$ and any state $j \\in \\mathcal{S}$:\n",
    "\n",
    "$$ \\text{long-run proportion of time spent in state $j$} = \\underbrace{\\lim_{n \\to \\infty}}_{\\text{long-run}} \\overbrace{\\frac{1}{n}}^{\\text{proportion}} \\underbrace{\\sum_{k=1}^n \\mathbf{1}\\{X_k = j\\}}_{\\text{time spent in state $j$}} $$\n",
    "\n",
    "**Remark:** Remember that we are in discrete time, so the ”time spent in” a state means the number of visits to that state.  When we encounter this same idea in continuous-time Markov chains, we will take into account the duration of each visit.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "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",
    "names = ['Coral Gables', 'Kendall', 'Downtown', 'Miami Beach']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "d_0 = [1, 0, 0, 0]\n",
    "steps = 1000\n",
    "sample_path = pd.DataFrame(dtmc.sim_path(P, d_0, steps=steps, S=S), \n",
    "                           index=pd.Index(range(0,steps+1), name='step'),\n",
    "                           columns=['path'])\n",
    "slider = widgets.IntSlider(value=1, min=1, max=steps, description='step')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "137c4f9757f54b68beb386af681137fb",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=500, description='step', max=1000, min=1), Output()), _dom_classes=('wid…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def sliding_table(path, current = 0, num_rows = 10, loc = 0):\n",
    "    style_past = 'color: gray'\n",
    "    style_present = 'background-color: rgba(255, 0, 0, 0.6)'\n",
    "    style_future = ''\n",
    "    start = max(0, current-loc)\n",
    "    end = start + num_rows\n",
    "    if start == current-loc:\n",
    "        highlight = loc\n",
    "    else:\n",
    "        highlight = current\n",
    "    df = path[start:end]\n",
    "    def highlight_row(s):\n",
    "        strs = ['']*len(df)\n",
    "        strs[0:highlight] = [style_past]*highlight\n",
    "        strs[highlight] = style_present\n",
    "        strs[highlight+1:] = [style_future]*(len(df)-highlight-1)\n",
    "        return strs\n",
    "    \n",
    "    display(df.style.apply(highlight_row))\n",
    "\n",
    "def path_state_counts(path, S):\n",
    "    indic = pd.get_dummies(path[1:]).reindex(S, axis='columns', fill_value=0)\n",
    "    count = indic.cumsum()\n",
    "    prop = count/np.transpose(np.broadcast_to(path.index.values[1:], (len(S), len(path.index)-1)))\n",
    "    indic = indic.rename(columns=dict(zip(indic.columns, [f'is in state {j}' for j in S])))\n",
    "    count = count.rename(columns=dict(zip(count.columns, [f'time in state {j}' for j in S])))\n",
    "    prop = prop.rename(columns=dict(zip(prop.columns, [f'proportion in state {j}' for j in S])))\n",
    "    return indic, count, prop\n",
    "\n",
    "indic, count, prop = path_state_counts(sample_path['path'], S)\n",
    "j = [2]\n",
    "loc = [S.index(state) for state in j]\n",
    "state_path = pd.DataFrame(sample_path['path'][1:]).join(indic.iloc[:,loc]).join(count.iloc[:,loc]).join(prop.iloc[:,loc])\n",
    "widgets.interact(lambda step: sliding_table(state_path, step-1), step=(1, len(sample_path.index)-1));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Connecting the table for the generated sample path above to the mathematical notation introduced, each column is:\n",
    "* $n$: step\n",
    "* $X_n$: path\n",
    "* $\\mathbf{1}\\{X_n = j\\}$: is in state $j$\n",
    "* $\\displaystyle\\sum_{k=0}^n \\mathbf{1}\\{X_k = j\\}$: time in state $j$\n",
    "* $\\displaystyle\\frac{1}{n}\\sum_{k=0}^n \\mathbf{1}\\{X_k = j\\}$: proportion in state $j$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "  <div class=\"bk-root\" id=\"d974eaa7-d961-47e7-8cef-26b56addb184\" data-root-id=\"1003\"></div>\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/javascript": [
       "(function(root) {\n",
       "  function embed_document(root) {\n",
       "    \n",
       "  var docs_json = {\"b4b4cb01-e93c-4304-a841-a1a6361a94a6\":{\"roots\":{\"references\":[{\"attributes\":{\"below\":[{\"id\":\"1014\",\"type\":\"CategoricalAxis\"}],\"center\":[{\"id\":\"1017\",\"type\":\"Grid\"},{\"id\":\"1022\",\"type\":\"Grid\"},{\"id\":\"1029\",\"type\":\"LabelSet\"}],\"left\":[{\"id\":\"1018\",\"type\":\"LinearAxis\"}],\"renderers\":[{\"id\":\"1026\",\"type\":\"GlyphRenderer\"}],\"title\":{\"id\":\"1004\",\"type\":\"Title\"},\"toolbar\":{\"id\":\"1023\",\"type\":\"Toolbar\"},\"x_range\":{\"id\":\"1006\",\"type\":\"FactorRange\"},\"x_scale\":{\"id\":\"1010\",\"type\":\"CategoricalScale\"},\"y_range\":{\"id\":\"1028\",\"type\":\"Range1d\"},\"y_scale\":{\"id\":\"1012\",\"type\":\"LinearScale\"}},\"id\":\"1003\",\"subtype\":\"Figure\",\"type\":\"Plot\"},{\"attributes\":{\"align\":\"center\",\"text\":\"Proportion of Time Spent in Each State\",\"text_font_size\":{\"value\":\"25px\"}},\"id\":\"1004\",\"type\":\"Title\"},{\"attributes\":{},\"id\":\"1019\",\"type\":\"BasicTicker\"},{\"attributes\":{\"dimension\":1,\"ticker\":{\"id\":\"1019\",\"type\":\"BasicTicker\"}},\"id\":\"1022\",\"type\":\"Grid\"},{\"attributes\":{},\"id\":\"1015\",\"type\":\"CategoricalTicker\"},{\"attributes\":{\"active_drag\":\"auto\",\"active_inspect\":\"auto\",\"active_multi\":null,\"active_scroll\":\"auto\",\"active_tap\":\"auto\"},\"id\":\"1023\",\"type\":\"Toolbar\"},{\"attributes\":{},\"id\":\"1010\",\"type\":\"CategoricalScale\"},{\"attributes\":{},\"id\":\"1034\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"level\":\"glyph\",\"source\":{\"id\":\"1024\",\"type\":\"ColumnDataSource\"},\"text\":{\"field\":\"labels\"},\"text_align\":\"center\",\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"top\"}},\"id\":\"1029\",\"type\":\"LabelSet\"},{\"attributes\":{\"fill_color\":{\"value\":\"blue\"},\"top\":{\"field\":\"top\"},\"width\":{\"value\":0.5},\"x\":{\"field\":\"x\"}},\"id\":\"1025\",\"type\":\"VBar\"},{\"attributes\":{\"callback\":null,\"factors\":[\"Coral Gables\",\"Kendall\",\"Downtown\",\"Miami Beach\"]},\"id\":\"1006\",\"type\":\"FactorRange\"},{\"attributes\":{\"ticker\":{\"id\":\"1015\",\"type\":\"CategoricalTicker\"}},\"id\":\"1017\",\"type\":\"Grid\"},{\"attributes\":{},\"id\":\"1032\",\"type\":\"CategoricalTickFormatter\"},{\"attributes\":{\"formatter\":{\"id\":\"1034\",\"type\":\"BasicTickFormatter\"},\"ticker\":{\"id\":\"1019\",\"type\":\"BasicTicker\"}},\"id\":\"1018\",\"type\":\"LinearAxis\"},{\"attributes\":{\"source\":{\"id\":\"1024\",\"type\":\"ColumnDataSource\"}},\"id\":\"1027\",\"type\":\"CDSView\"},{\"attributes\":{\"callback\":null},\"id\":\"1028\",\"type\":\"Range1d\"},{\"attributes\":{},\"id\":\"1012\",\"type\":\"LinearScale\"},{\"attributes\":{\"callback\":null,\"data\":{\"labels\":[\"0.4370\",\"0.1920\",\"0.2630\",\"0.1080\"],\"top\":{\"__ndarray__\":\"K4cW2c732z/6fmq8dJPIP6JFtvP91NA/2c73U+Oluz8=\",\"dtype\":\"float64\",\"shape\":[4]},\"x\":[\"Coral Gables\",\"Kendall\",\"Downtown\",\"Miami Beach\"]},\"selected\":{\"id\":\"1036\",\"type\":\"Selection\"},\"selection_policy\":{\"id\":\"1037\",\"type\":\"UnionRenderers\"}},\"id\":\"1024\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"formatter\":{\"id\":\"1032\",\"type\":\"CategoricalTickFormatter\"},\"major_label_text_font_size\":{\"value\":\"20px\"},\"ticker\":{\"id\":\"1015\",\"type\":\"CategoricalTicker\"}},\"id\":\"1014\",\"type\":\"CategoricalAxis\"},{\"attributes\":{\"data_source\":{\"id\":\"1024\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"1025\",\"type\":\"VBar\"},\"hover_glyph\":null,\"muted_glyph\":null,\"view\":{\"id\":\"1027\",\"type\":\"CDSView\"}},\"id\":\"1026\",\"type\":\"GlyphRenderer\"},{\"attributes\":{},\"id\":\"1037\",\"type\":\"UnionRenderers\"},{\"attributes\":{},\"id\":\"1036\",\"type\":\"Selection\"}],\"root_ids\":[\"1003\"]},\"title\":\"Bokeh Application\",\"version\":\"1.3.4\"}};\n",
       "  var render_items = [{\"docid\":\"b4b4cb01-e93c-4304-a841-a1a6361a94a6\",\"notebook_comms_target\":\"1038\",\"roots\":{\"1003\":\"d974eaa7-d961-47e7-8cef-26b56addb184\"}}];\n",
       "  root.Bokeh.embed.embed_items_notebook(docs_json, render_items);\n",
       "\n",
       "  }\n",
       "  if (root.Bokeh !== undefined) {\n",
       "    embed_document(root);\n",
       "  } else {\n",
       "    var attempts = 0;\n",
       "    var timer = setInterval(function(root) {\n",
       "      if (root.Bokeh !== undefined) {\n",
       "        embed_document(root);\n",
       "        clearInterval(timer);\n",
       "      }\n",
       "      attempts++;\n",
       "      if (attempts > 100) {\n",
       "        console.log(\"Bokeh: ERROR: Unable to run BokehJS code because BokehJS library is missing\");\n",
       "        clearInterval(timer);\n",
       "      }\n",
       "    }, 10, root)\n",
       "  }\n",
       "})(window);"
      ],
      "application/vnd.bokehjs_exec.v0+json": ""
     },
     "metadata": {
      "application/vnd.bokehjs_exec.v0+json": {
       "id": "1003"
      }
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "ba4a49254e6f4a0d9bb03f0f361604fd",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=1, description='step', max=1000, min=1), Output()), _dom_classes=('widge…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def freq_plot(freq, xlabels, normalize=True):\n",
    "    p = bplt.figure(title='Proportion of Time Spent in Each State', x_range=xlabels, tools=[])\n",
    "    p.title.align = 'center'\n",
    "    p.title.text_font_size = '25px'\n",
    "    p.xaxis.major_label_text_font_size = '20px'\n",
    "    source = ColumnDataSource(data=dict(x=xlabels, top=freq.iloc[-1].values))\n",
    "    source.data['labels'] = [f'{v:0.4f}' if normalize else f'{v}' for v in source.data['top']]\n",
    "    glyph = VBar(x=\"x\", top=\"top\", bottom=0, width=0.5, fill_color='blue')\n",
    "    p.add_glyph(source, glyph)\n",
    "    if normalize:\n",
    "        p.y_range = Range1d(0, 1)\n",
    "    else:\n",
    "        p.y_range = Range1d(0, len(sample_path.index))\n",
    "    labels = LabelSet(x=\"x\", y=\"top\", text=\"labels\",\n",
    "                      level=\"glyph\", text_align=\"center\",\n",
    "                      source=source, \n",
    "                      render_mode='canvas')\n",
    "    p.add_layout(labels)\n",
    "    handle = bplt.show(p, notebook_handle=True)\n",
    "    \n",
    "    return source, handle\n",
    "\n",
    "normalize = True # Set to True for proportion of time, False for number of visits\n",
    "freq = prop if normalize else count\n",
    "source, handle = freq_plot(freq, names, normalize=normalize)\n",
    "\n",
    "def wrapper(step, freq, source, handle):\n",
    "    source.data['top'] = freq.iloc[step-1].values\n",
    "    source.data['labels'] = [f'{v:0.4f}' if normalize else f'{v}' for v in source.data['top']]\n",
    "    push_notebook(handle=handle)\n",
    "        \n",
    "    sliding_table(pd.DataFrame(sample_path['path'][1:]).join(freq), current=step-1, loc=5)\n",
    "\n",
    "widgets.interact(lambda step: wrapper(step, freq, source, handle), step=slider);    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The codeblock above produces an interactive bar plot: the relative frequency of visits to each state (neighborhood) in the first $n$ steps of the sample path $(X_0, X_1, \\dots, X_n)$ (so the height of the bars will sum to 1).  Use the slider to increase/decrease $m$.  You should notice that as $n$ increases, the frequencies tend to stabilize.  You can change the number of steps (`steps`) and the initial distribution (`d_0`) in the prior codeblock."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 6.1\n",
    "\n",
    "Pick a large $n$ (number of steps) and look at the long-run proportions of time spent in each state for this sample path.  Compare this to the distributions you calculated in Exercises 4.2, 4.3, and 4.4.  What do you notice?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Stationary Distribution — Interpretations\n",
    "\n",
    "### Proportion of Time\n",
    "\n",
    "We will define $\\pi_j$ to be the long-run proportion of time spent in state $j$:\n",
    "\n",
    "$$ \\pi_j = \\lim_{n \\to \\infty} \\frac{1}{n} \\sum_{k=1}^n \\mathbf{1}\\{X_k = j\\} $$\n",
    "\n",
    "with the caveat that $\\pi_j$ is only defined when:\n",
    "* the limit exists\n",
    "* the limit does not depend on the initial state $X_0$.  (That is, it is the same for any initial state $X_0 = i$, $i \\in \\mathcal{S}$.)\n",
    "\n",
    "In particular, we want to avoid the ambiguity described in Example 6.x below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Distribution\n",
    "\n",
    "We will usually represent $\\pi$ as a (row) vector with $\\pi_j$ as the $j$th element of the vector.\n",
    "\n",
    "When the limit exists and does not depend on the initial state $X_0$, $\\pi$ is called the stationary distribution and satisfies:\n",
    "\n",
    "$$ \\pi = \\pi \\mathbf{P} $$\n",
    "\n",
    "In this class, we will only discuss stationary distributions in the context of positive recurrent Markov chains. (The optional Exercise 6.x below considers a stationary distribution for a finite state-space Markov chain that is not irreducible, and hence not positive recurrent.  It may be useful to test the limits of your understanding, but you should feel free to skip it.)\n",
    "\n",
    "**Theorem:** An *irreducible* Markov chain is positive recurrent if and only if there exists a unique solution to:\n",
    "$$ \\pi = \\pi \\mathbf{P} $$\n",
    "with $\\pi \\geq 0$ and $\\sum_j \\pi_j = 1$.\n",
    "\n",
    "Note that this assumes the Markov chain is irreducible and is an “if and only if” result, so it works in both directions:\n",
    "* If a Markov chain is positive recurrent, then the stationary distribution exists and is unique.\n",
    "* If a unique stationary distribution exists, then the Markov chain is positive recurrent.\n",
    "\n",
    "The first direction will be most useful for this part of the course when we only consider finite state spaces.  The second direction will be useful once we move to infinite state spaces.  (For finite state spaces, we already know that an irreducible Markov chain is positive recurrent.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Limiting or Steady-State Probabilities\n",
    "\n",
    "We saw in Section 4 (The Ride-Share Driver) that $\\lim_{m \\to \\infty} p_{ij}^{(m)} = \\pi_j$.  In matrix form, this was\n",
    "$$\\lim_{m \\to \\infty} \\mathbf{P}^{(m)} = \n",
    "  \\begin{pmatrix}\n",
    "    \\leftarrow & \\pi & \\rightarrow \\\\\n",
    "    \\leftarrow & \\pi & \\rightarrow \\\\\n",
    "    & \\vdots & \\\\\n",
    "    \\leftarrow & \\pi & \\rightarrow \\\\\n",
    "  \\end{pmatrix}$$\n",
    "This is true **only if the Markov chain is aperiodic**.  So, for a Markov chain that is positive recurrent and aperiodic, $\\pi$ can also be interpreted as the limiting distribution — the distribution representing where the Markov chain will be far into the future.\n",
    "\n",
    "Alternatively, we sometimes say that the Markov chain is in “steady-state”, if its initial distribution $\\mathbf{d}_0 = \\pi$, since $\\mathbf{d}_n = \\pi$ for all $n \\geq 0$.  For an aperiodic Markov chain, we can interpret this as the Markov chain  been running for a long time (it started at $n = -\\infty$) and, so by time $0$, has reached steady-state.\n",
    "  \n",
    "Why does this not apply to a periodic Markov chain?  Consider the original rat-in-a-maze example, where the Markov chain was *periodic* (with period 2).  $\\mathbf{P}^{(m)} = \\mathbf{P}$ for all $m$ odd and $\\mathbf{P}^{(m)} = \\mathbf{P}^{(2)}$ for all $m$ even (since $\\mathbf{P}^{(m)}$ never converges, the limit $\\lim_{m \\to \\infty} \\mathbf{P}^{(m)}$ does not exist)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example: Long-Run Depends on Initial State\n",
    "\n",
    "This example shows when the limit exists (for the long-run proportion of time spent in a state), but depends on the initial state $X_0$.  $\\mathcal{S} = \\{1,2,3,4\\}$ \n",
    "$$\\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}$$\n",
    "There are two communication classes: $\\{1, 2\\}$ and $\\{3, 4\\}$, both with recurrent states.  Depending on which set of states the Markov chain starts in, it will stay in those states forever (never visiting the other communication class).  In this case, the long-run proportion of time spent in a state depends on the starting position of the Markov chain $X_0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "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",
    "             ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathbf{d}_0 = \\pmatrix{0.5& 0& 0.5& 0}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle X_0 = 1$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "  <div class=\"bk-root\" id=\"cbea9b8b-0eb2-460a-b44b-af8a831def32\" data-root-id=\"1170\"></div>\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/javascript": [
       "(function(root) {\n",
       "  function embed_document(root) {\n",
       "    \n",
       "  var docs_json = {\"076212fb-4bf6-4ff1-a84f-1c83639dbc13\":{\"roots\":{\"references\":[{\"attributes\":{\"below\":[{\"id\":\"1181\",\"type\":\"CategoricalAxis\"}],\"center\":[{\"id\":\"1184\",\"type\":\"Grid\"},{\"id\":\"1189\",\"type\":\"Grid\"},{\"id\":\"1196\",\"type\":\"LabelSet\"}],\"left\":[{\"id\":\"1185\",\"type\":\"LinearAxis\"}],\"renderers\":[{\"id\":\"1193\",\"type\":\"GlyphRenderer\"}],\"title\":{\"id\":\"1171\",\"type\":\"Title\"},\"toolbar\":{\"id\":\"1190\",\"type\":\"Toolbar\"},\"x_range\":{\"id\":\"1173\",\"type\":\"FactorRange\"},\"x_scale\":{\"id\":\"1177\",\"type\":\"CategoricalScale\"},\"y_range\":{\"id\":\"1195\",\"type\":\"Range1d\"},\"y_scale\":{\"id\":\"1179\",\"type\":\"LinearScale\"}},\"id\":\"1170\",\"subtype\":\"Figure\",\"type\":\"Plot\"},{\"attributes\":{\"source\":{\"id\":\"1191\",\"type\":\"ColumnDataSource\"}},\"id\":\"1194\",\"type\":\"CDSView\"},{\"attributes\":{\"align\":\"center\",\"text\":\"Proportion of Time Spent in Each State\",\"text_font_size\":{\"value\":\"25px\"}},\"id\":\"1171\",\"type\":\"Title\"},{\"attributes\":{\"callback\":null,\"data\":{\"labels\":[\"0.5000\",\"0.5000\",\"0.0000\",\"0.0000\"],\"top\":{\"__ndarray__\":\"AAAAAAAA4D8AAAAAAADgPwAAAAAAAAAAAAAAAAAAAAA=\",\"dtype\":\"float64\",\"shape\":[4]},\"x\":[\"1\",\"2\",\"3\",\"4\"]},\"selected\":{\"id\":\"1217\",\"type\":\"Selection\"},\"selection_policy\":{\"id\":\"1218\",\"type\":\"UnionRenderers\"}},\"id\":\"1191\",\"type\":\"ColumnDataSource\"},{\"attributes\":{},\"id\":\"1213\",\"type\":\"CategoricalTickFormatter\"},{\"attributes\":{},\"id\":\"1217\",\"type\":\"Selection\"},{\"attributes\":{},\"id\":\"1177\",\"type\":\"CategoricalScale\"},{\"attributes\":{\"formatter\":{\"id\":\"1213\",\"type\":\"CategoricalTickFormatter\"},\"major_label_text_font_size\":{\"value\":\"20px\"},\"ticker\":{\"id\":\"1182\",\"type\":\"CategoricalTicker\"}},\"id\":\"1181\",\"type\":\"CategoricalAxis\"},{\"attributes\":{},\"id\":\"1215\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"fill_color\":{\"value\":\"blue\"},\"top\":{\"field\":\"top\"},\"width\":{\"value\":0.5},\"x\":{\"field\":\"x\"}},\"id\":\"1192\",\"type\":\"VBar\"},{\"attributes\":{},\"id\":\"1218\",\"type\":\"UnionRenderers\"},{\"attributes\":{\"ticker\":{\"id\":\"1182\",\"type\":\"CategoricalTicker\"}},\"id\":\"1184\",\"type\":\"Grid\"},{\"attributes\":{\"level\":\"glyph\",\"source\":{\"id\":\"1191\",\"type\":\"ColumnDataSource\"},\"text\":{\"field\":\"labels\"},\"text_align\":\"center\",\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"top\"}},\"id\":\"1196\",\"type\":\"LabelSet\"},{\"attributes\":{},\"id\":\"1182\",\"type\":\"CategoricalTicker\"},{\"attributes\":{},\"id\":\"1179\",\"type\":\"LinearScale\"},{\"attributes\":{\"dimension\":1,\"ticker\":{\"id\":\"1186\",\"type\":\"BasicTicker\"}},\"id\":\"1189\",\"type\":\"Grid\"},{\"attributes\":{\"formatter\":{\"id\":\"1215\",\"type\":\"BasicTickFormatter\"},\"ticker\":{\"id\":\"1186\",\"type\":\"BasicTicker\"}},\"id\":\"1185\",\"type\":\"LinearAxis\"},{\"attributes\":{\"callback\":null},\"id\":\"1195\",\"type\":\"Range1d\"},{\"attributes\":{\"callback\":null,\"factors\":[\"1\",\"2\",\"3\",\"4\"]},\"id\":\"1173\",\"type\":\"FactorRange\"},{\"attributes\":{\"data_source\":{\"id\":\"1191\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"1192\",\"type\":\"VBar\"},\"hover_glyph\":null,\"muted_glyph\":null,\"view\":{\"id\":\"1194\",\"type\":\"CDSView\"}},\"id\":\"1193\",\"type\":\"GlyphRenderer\"},{\"attributes\":{},\"id\":\"1186\",\"type\":\"BasicTicker\"},{\"attributes\":{\"active_drag\":\"auto\",\"active_inspect\":\"auto\",\"active_multi\":null,\"active_scroll\":\"auto\",\"active_tap\":\"auto\"},\"id\":\"1190\",\"type\":\"Toolbar\"}],\"root_ids\":[\"1170\"]},\"title\":\"Bokeh Application\",\"version\":\"1.3.4\"}};\n",
       "  var render_items = [{\"docid\":\"076212fb-4bf6-4ff1-a84f-1c83639dbc13\",\"notebook_comms_target\":\"1219\",\"roots\":{\"1170\":\"cbea9b8b-0eb2-460a-b44b-af8a831def32\"}}];\n",
       "  root.Bokeh.embed.embed_items_notebook(docs_json, render_items);\n",
       "\n",
       "  }\n",
       "  if (root.Bokeh !== undefined) {\n",
       "    embed_document(root);\n",
       "  } else {\n",
       "    var attempts = 0;\n",
       "    var timer = setInterval(function(root) {\n",
       "      if (root.Bokeh !== undefined) {\n",
       "        embed_document(root);\n",
       "        clearInterval(timer);\n",
       "      }\n",
       "      attempts++;\n",
       "      if (attempts > 100) {\n",
       "        console.log(\"Bokeh: ERROR: Unable to run BokehJS code because BokehJS library is missing\");\n",
       "        clearInterval(timer);\n",
       "      }\n",
       "    }, 10, root)\n",
       "  }\n",
       "})(window);"
      ],
      "application/vnd.bokehjs_exec.v0+json": ""
     },
     "metadata": {
      "application/vnd.bokehjs_exec.v0+json": {
       "id": "1170"
      }
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "a937f0a2a483486980f02ebd0a761eb0",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=1, description='step'), Output()), _dom_classes=('widget-interact',))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "d_0 = [0.5, 0, 0.5, 0]\n",
    "steps = 100\n",
    "example_sample_path = pd.DataFrame(dtmc.sim_path(P, d_0, steps=steps, S=S), \n",
    "                           index=pd.Index(range(0,steps+1), name='step'),\n",
    "                           columns=['path'])\n",
    "slider = widgets.IntSlider(value=1, min=0, max=steps, description='step')\n",
    "\n",
    "display(Math(r'\\mathbf{d}_0 = ' + dtmc.pmatrix([d_0])))\n",
    "X_0 = example_sample_path[\"path\"][0]\n",
    "display(Math(f'X_0 = {X_0}'))\n",
    "\n",
    "example_indic, example_count, example_prop = path_state_counts(example_sample_path['path'], S)\n",
    "\n",
    "normalize = True\n",
    "example_freq = example_prop if normalize else example_count\n",
    "example_source, example_handle = freq_plot(example_freq, list(map(str, S)), normalize=normalize)\n",
    "\n",
    "widgets.interact(lambda step: wrapper(step, example_freq, example_source, example_handle), step=slider);    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The stationary distrbution $\\pi$ for a positive recurrent Markov chain has a number of interpretations and uses:\n",
    "* $\\pi$ is the unique solution to  \n",
    "    $$ \\pi = \\pi \\mathbf{P} \\qquad \\sum_{j \\in \\mathcal{S}} \\pi_j = 1. $$\n",
    "    \n",
    "* $\\pi_j$ is the long-run proportion of time spent in time $j$\n",
    "    $$ \\pi_j = \\lim_{n \\to \\infty} \\frac{1}{n} \\sum_{k=1}^n \\mathbf{1}\\{X_k = j\\}. $$\n",
    "    \n",
    "* $\\pi_j$ is $1/$expected return time to state $j$ (remember that $\\mathsf{E}[\\tau_{jj}] < \\infty$ since state $j$ is positive recurrent)\n",
    "    $$ \\pi_j = \\frac{1}{\\mathsf{E}[\\tau_{jj}]}.$$\n",
    "    (See “Transience and Recurrence” of Section 5: Markov Chain Structure to review the concept of the return time $\\tau_{jj}$.)  \n",
    "    \n",
    "* $\\pi_j$ is the long-run average probability  \n",
    "    $$ \\pi_j = \\lim_{n \\to \\infty} \\frac{1}{n} \\sum_{k=0}^n p_{ij}^{(k)}. $$\n",
    "    \n",
    "* **If the chain is aperiodic then** $\\pi_j$ is also the long-run limit probability\n",
    "    $$ \\pi_j = \\lim_{n \\to \\infty} p_{ij}^{(n)}. $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Finding the Stationary Distribution $\\pi$\n",
    "\n",
    "### Solve for $\\pi$\n",
    "\n",
    "The most straightforward way to find the stationary distribution is to (algebraically) solve the system of equations:\n",
    "\n",
    "$$ \\pi = \\pi \\mathbf{P} \\qquad \\sum_{j \\in \\mathcal{S}} \\pi_j = 1. $$\n",
    "\n",
    "Since $\\pi$ is a vector and $\\mathbf{P}$ is a matrix, $\\pi = \\mathbf{P}$ is equivalent to\n",
    "$$\\pi_j = \\sum_{i \\in \\mathcal{S}} \\pi_j p_{ij} = \\pi_1 p_{1j} + \\pi_2 p_{2j} + \\pi_3 p_{3j} + \\dots$$\n",
    "for each $j \\in \\mathcal{S}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example: Rat in a Maze\n",
    "\n",
    "For $\\mathcal{S} = \\{1, 2, 3, 4\\}$ and \n",
    "$$\\mathbf{P} = \\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",
    "Solve the system of equations $\\pi = \\pi \\mathbf{P}$ and $\\sum_{j \\in \\mathcal{S}} \\pi_j = 1$ to find the stationary distribution.\n",
    "\n",
    "\n",
    "The equations $\\pi = \\pi \\mathbf{P}$ give\n",
    "$$\\begin{aligned}\n",
    "    \\pi_1 &= \\frac{1}{2} (\\pi_2 + \\pi_4) \\\\\n",
    "    \\pi_2 &= \\frac{1}{2} (\\pi_1 + \\pi_3) \\\\\n",
    "    \\pi_3 &= \\frac{1}{2} (\\pi_2 + \\pi_4) \\\\\n",
    "    \\pi_4 &= \\frac{1}{2} (\\pi_1 + \\pi_3) \\\\\n",
    "\\end{aligned}$$\n",
    "\n",
    "While you may use various techniques from linear algebra, you can often just simplify the system of equations with basic algebra.  In the example above, notice that $\\pi_1 = \\pi_3$ (both are equal to $(\\pi_2 + \\pi_4)/2$) and $\\pi_2 = \\pi_4$ (both are equal to $(\\pi_1 + \\pi_3)/2$).  Combining these then gives us $\\pi_1 = \\pi_2 = \\pi_3 = \\pi_4$.  \n",
    "\n",
    "To fully solve for $\\pi$, we need the last equation, $\\sum_{j \\in \\mathcal{S}} \\pi_j = 1$, which ensures that $\\pi$ is a valid distribution over $\\mathcal{S}$.\n",
    "\n",
    "So we can conclude that $\\pi_i = 1/4$ for all $i \\in \\mathcal{S}$.  In other words, the stationary distribution is uniform over the state space.\n",
    "\n",
    "(**Note:** Do not forget that you need the last equation $\\sum_{j \\in \\mathcal{S}} \\pi_j = 1$.  Since $\\mathbf{P}$ is a stochastic matrix — its rows sum to 1 — it is not full-rank and hence $\\pi = \\pi \\mathbf{P}$ represents only $|\\mathcal{S}| - 1$ linearly independent equations.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Numerical Estimation\n",
    "\n",
    "We can also use the various “long-run” interpretations of $\\pi$ to estimate it or, in some cases, calculate it.\n",
    "\n",
    "For the ride-share driver example, you saw in Exercise 6.1 above that for large $n$,:\n",
    "$$ \\pi_j \\approx \\frac{1}{n} \\sum_{k=1}^n \\mathbf{1}\\{X_k = j\\} $$\n",
    "and in Exercise 4.3 that, for large $n$,\n",
    "$$ \\pi_j \\approx p_{ij}^{(n)}.$$\n",
    "So, $\\pi \\approx \\pmatrix{0.4448 & 0.1909 & 0.2643 & 0.1}$.  (Remember that the limiting probability $\\lim_{n \\to \\infty} p_{ij}^{(n)}$ only exists for an aperiodic Markov chain.)\n",
    "\n",
    "In the case of the rat-in-a-maze, we would need to look at the long-run average probabilities instead of the limiting probabilities:\n",
    "$$\\pi_j = \\lim_{n \\to \\infty} \\frac{1}{n} \\sum_{k=1}^n p_{ij}^{(k)}$$\n",
    "However, as we noticed in Section 5, this DTMC is periodic with period $d = 2$ and, $\\mathbf{P}^{(m)} = \\mathbf{P}$ for any odd $m$ and $\\mathbf{P}^{(m)} = \\mathbf{P}^{(2)}$ for any even $m$.  Therefore\n",
    "$$\\pi_j = \\lim_{n \\to \\infty} \\frac{1}{n} \\sum_{k=1}^n p_{ij}^{(k)} = \\frac{1}{2} (p_{ij} + p_{ij}^{(2)}) = \\frac{1}{4}.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Guess-and-Check\n",
    "\n",
    "Recall the result above that a positive recurrent Markov chain is guaranteed to have a unique stationary distribution (that satisfies $\\pi = \\pi \\mathbf{P}$, $\\pi > 0$, and $\\sum_j \\pi_j = 1$).  Since $\\pi$ is unique, if we can guess a solution that satisfies the equations, then it must be the stationary distribution.\n",
    "\n",
    "This is actually more useful than it sounds and is not unlike how solving a partial differential equation often involves some (informed) guessing as to the form of the solution.  The guess is usually based on some understanding of the original problem, which may not be clear if you're just staring at $\\mathbf{P}$.\n",
    "\n",
    "Take, for example, the following DTMC on $\\mathcal{S} = \\{1, 2, 3\\}$.\n",
    "$$ \\mathbf{P} = \\pmatrix{0 & 1 & 0 \\\\ 1/2 & 0 & 1/2 \\\\ 0 & 1 & 0} $$\n",
    "This was the second maze example in Exercise 2.2.  We can see that if the Markov chain is in state $1$ or state $3$ then it always moves to state $2$ in the next step (with probability $1$).  On the other hand, if the Markov chain is in state $2$ then it will move to either state $1$ or state $3$ (each with probability $1/2$).  Based on this, we would guess that the Markov chain spends twice as much time in state $2$ as in either states $1$ or $3$.  \n",
    "\n",
    "Therefore our guess is that $\\pi_2 = 2 \\pi_1 = 2 \\pi_3$, which, as a distribution with $\\pi_1 + \\pi_2 + \\pi_3 = 1$, would be $\\pi = \\pmatrix{1/4 & 1/2 & 1/4}$.  Since we have constructed $\\pi$ such that $\\pi > 0$ and $\\sum_j \\pi_j = 1$, it only remains to check that $\\pi = \\pi \\mathbf{P}$:\n",
    "\n",
    "$$\\pi \\mathbf{P} = \\pmatrix{1/4 & 1/2 & 1/4} \\pmatrix{0 & 1 & 0 \\\\ 1/2 & 0 & 1/2 \\\\ 0 & 1 & 0}\n",
    "  = \\pmatrix{1/2 \\times 1/2 & 1/4 \\times 1 + 1/4 \\times 1 & 1/2 \\times 1/2} = \\pmatrix{1/4 & 1/2 & 1/4}\n",
    "  $$\n",
    "  \n",
    "Similarly, for the original rat-in-a-maze example, we might simply guess that $\\pi$ was uniform over $\\mathcal{S}$ based on the symmetry of the maze."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 6.2\n",
    "\n",
    "For each of the following, find the stationary distribution.  Check that your answer satisfies $\\pi = \\pi \\mathbf{P}$ and $\\sum_j \\pi_j = 1$.\n",
    "\n",
    "(**Note:** Each of these codeblocks randomly generate examples.  For the second codeblock, the Markov chain is not guaranteed to be irreducible, in which case you can just re-run the codeblock until it generates an irreducible Markov chain.  Better yet, you can write a function that checks whether the Markov chain is irreducible and, if not, adds the necessary transitions to make it irreducible.)"
   ]
  },
  {
   "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& 0& 1& 0\\\\ 0& 0& 1/2& 1/2\\\\ 1/3& 1/3& 0& 1/3\\\\ 0& 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=\"211pt\" height=\"133pt\"\n",
       " viewBox=\"0.00 0.00 211.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 207.3493,-129.3153 207.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=\"-62.6576\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-58.9576\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"108\" cy=\"-62.6576\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"108\" 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=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M46.4519,-62.6576C57.0929,-62.6576 69.1681,-62.6576 79.7874,-62.6576\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.2128,-59.1575 36.2128,-62.6576 46.2129,-66.1575 46.2128,-59.1575\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"79.8143,-66.1577 89.8142,-62.6576 79.8142,-59.1577 79.8143,-66.1577\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"185.3493\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"185.3493\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</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=\"M160.8967,-32.1177C151.8467,-37.3427 141.5896,-43.2647 132.5326,-48.4937\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"162.7863,-35.0683 169.6965,-27.0371 159.2862,-29.0061 162.7863,-35.0683\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"130.5398,-45.6028 123.6295,-53.6339 134.0398,-51.665 130.5398,-45.6028\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"185.3493\" cy=\"-107.3153\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"185.3493\" y=\"-103.6153\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;4 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M185.3493,-46.2355C185.3493,-56.6855 185.3493,-68.5293 185.3493,-78.9875\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"188.8494,-46.0742 185.3493,-36.0743 181.8494,-46.0743 188.8494,-46.0742\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"181.8494,-79.2678 185.3493,-89.2679 188.8494,-79.2679 181.8494,-79.2678\"/>\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=\"M132.4526,-76.7754C141.5026,-82.0004 151.7597,-87.9223 160.8167,-93.1514\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"134.0631,-73.6637 123.6528,-71.6948 130.563,-79.7259 134.0631,-73.6637\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"159.3095,-96.3226 169.7198,-98.2916 162.8095,-90.2604 159.3095,-96.3226\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7fb268b50950>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "n = 4 # number of rooms\n",
    "S = range(1,n+1)\n",
    "P = dtmc.rand_maze(n, p = [0,0.2,0.4,0.4])\n",
    "\n",
    "dtmc.disp_dtmc(P, S, frac=True)\n",
    "display(mcviz.dot_mc(P, S, engine='circo', bidir=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 6.3 (Optional)\n",
    "\n",
    "Find the distribution $\\pi$ that satisfies $\\pi = \\pi \\mathbf{P}$, $\\pi \\geq 0$, $\\sum_j \\pi_j = 1$ where $\\mathcal{S} = \\{1, 2, 3\\}$ and\n",
    "$$\\mathbf{P} =\n",
    "  \\begin{pmatrix}\n",
    "    0.5 & 0.25 & 0.25 \\\\\n",
    "    0 & 0.2 & 0.8 \\\\\n",
    "    0 & 0.8 & 0.2\n",
    "  \\end{pmatrix}$$"
   ]
  }
 ],
 "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
}