2-1-DTMC-example.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Discrete-Time Markov Chains: Section 1 - Example: A “Rat” in a “Maze”"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Setting\n",
    "\n",
    "This is very much a “toy” model, but is a simple and illustrative setting in which to introduce Markov chains.\n",
    "\n",
    "Suppose there is a “rat” that moves around a simple “maze” with four rooms.  Some of the rooms are connected to one another by doors, according to this illustration:\n",
    "\n",
    "<img src=\"Maze.svg\">\n",
    "![maze.svg](attachment:maze.svg)\n",
    "\n",
    "(If you prefer, you can think of this as a model of a [Roomba](https://www.irobot.com/roomba) moving through a house.)\n",
    "\n",
    "We want to model the rat's movements as a stochastic process.\n",
    "\n",
    "**Model Assumptions:**\n",
    "* We track the *sequence* of rooms that the rat visits -- only recording when the rat moves to a different room.  This ignores any movement within a room and the amount of time spent in a room.\n",
    "* The rat moves into any adjoining room (a room that is connected by a door) with equal probability.\n",
    "\n",
    "Let $X_0$ be the room it starts in, $X_1$ the room it is in after 1 move, etc., and in general $X_n$ is the room after $n$ moves.\n",
    "\n",
    "The sequence of rooms that the rat visits is a *stochastic process*:\n",
    "$$ (X_0, X_1, X_2, \\dots) $$\n",
    "I will sometimes write this more succinctly as $\\{X_n\\}$ or $\\{X_n, n \\geq 0\\}$.\n",
    "\n",
    "For now, you should **think of a stochastic process as a random path**.  In this case, our stochastic process is a sequence of rooms that describes the path of the rat through the maze.  This path is random because the movement of the rat is random.  In fact, we can look at a **sample path** of the stochastic process (this is analogous to a sample of a random variable).  For the stochastic process we've described, the following sample path\n",
    "\n",
    "$$ (1, 2, 1, 2, 3, 2, 3, 4, 1, 2, \\dots) $$\n",
    "\n",
    "is a realized path in which the rat starts in room 1 then moves to room 2 then moves to room 1 then moves to room 2 then moves to room 3, etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1.1\n",
    "\n",
    "Why are each of the following **not** valid sample paths of this stochastic process (the sequence of rooms the rat visits in this maze)?\n",
    "\n",
    "* $(1,2,3,1,2,1,4,3,2,\\dots)$\n",
    "* $(1,2,1,4,5,4,3,2,1,\\dots)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding Probability Distributions\n",
    "\n",
    "Suppose the rat starts in room 1.  Where will it go on its next move?  According to the second model assumption, it is equally like to move to either of the two adjoining rooms: room $2$ or room $4$.\n",
    "\n",
    "Stating this mathematically, the location of the rat after the first move is $X_1$, which is a random variable with the following probability distribution, given $X_0 = 1$ (the rat starts in room 1):\n",
    "\n",
    "$$ \\mathsf{P}(X_1 = 2 \\,|\\, X_0 = 1) = \\frac{1}{2} \\qquad\n",
    "   \\mathsf{P}(X_1 = 4 \\,|\\, X_0 = 1) = \\frac{1}{2} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1.2\n",
    "\n",
    "What is the probability distribution of $X_1$ given $X_0 = 2$?\n",
    "\n",
    "Construct a 4x4 table of **transition probabilities** where the element in row $i$ and column $j$ represents the probability that the it next moves to room $j$ given that it starts in room $i$:\n",
    "\n",
    "$$ \\mathsf{P}(X_1 = j \\,|\\, X_0 = i) $$\n",
    "\n",
    "The first row is filled out with the transition probabilities from room 1 ($i=1$) to every other room ($j=1,2,3,4$).\n",
    "\n",
    "| transition probability | to room 1  | to room 2   | to room 3   | to room 4   |\n",
    "|:--- |:---:|:---:|:---:|:---:|\n",
    "| from room 1 |  0 | 1/2 |  0  | 1/2 | \n",
    "| from room 2 | \n",
    "| from room 3 | \n",
    "| from room 4 | \n",
    "\n",
    "Note that $\\mathsf{P}(X_1 = 1\\,|\\,X_0=1) = 0$ because, under the first assumption, we only move to the next time step when the rat moves to a different room.  Why is $\\mathsf{P}(X_1 = 3\\,|\\, X_0 = 3) = 0$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simulation and Visualization\n",
    "\n",
    "The second assumption of the model (the rat moves into any adjoining room with equal probability) implicitly includes two assumptions we should state explicitly:\n",
    "\n",
    "* the transition probabilities do not change over time\n",
    "* do not depend on the rat's path\n",
    "\n",
    "In other words, the rat's behavior when it is in room $i$ is the same every time it is in room $i$.  It does not matter if it is time step $n = 0$ or $n = 100$.  It does not matter if it is its first visit to room $i$ or its billionth visit.  It does not matter what path it took to get to room $i$.\n",
    "\n",
    "We will state this later in more mathematical terms as the **Markov Property**.  For now, think of the rat as being “memoryless.”\n",
    "\n",
    "This memoryless property makes it particularly easy to simulate this stochastic process.  The next move only depends on the rat's current location, so we can easily simulate every move using the same table of transition probabilities you filled out in Exercise 1.2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1.3\n",
    "\n",
    "Suppose you wanted to simulate this process by tossing a (fair) coin repeatedly.  How would you come up with a sample path of the process?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python setup"
   ]
  },
  {
   "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",
    "import ipywidgets as widgets\n",
    "\n",
    "import dtmc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simulate a sample path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "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",
    "d_0 = [1, 0, 0, 0]\n",
    "\n",
    "steps = 50\n",
    "index = pd.Index(range(0,steps+1), name='n')\n",
    "sample_path = pd.DataFrame(dtmc.sim_path(P, d_0, steps=steps, S=S), \n",
    "                           index=index, columns=['X'])\n",
    "\n",
    "n_slider = widgets.IntSlider(value=0, min=min(index), max=max(index), description='n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sample Path Visualizations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the sample path simulated above, here are a few ways to “see” the dynamics of the stochastic process.\n",
    "\n",
    "List the sequence $(X_0, X_1, X_2, \\dots)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plot the stochastic process $\\{X_n, n \\geq 0\\}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "  <div class=\"bk-root\" id=\"d411fcc6-2b22-47a6-8b3d-67233f4fc91d\" data-root-id=\"1002\"></div>\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/javascript": [
       "(function(root) {\n",
       "  function embed_document(root) {\n",
       "    \n",
       "  var docs_json = {\"7ea2ae7d-cb9c-499e-b1cd-3417c57c772b\":{\"roots\":{\"references\":[{\"attributes\":{\"below\":[{\"id\":\"1013\",\"type\":\"LinearAxis\"}],\"center\":[{\"id\":\"1017\",\"type\":\"Grid\"},{\"id\":\"1022\",\"type\":\"Grid\"}],\"left\":[{\"id\":\"1018\",\"type\":\"LinearAxis\"}],\"plot_height\":400,\"plot_width\":800,\"renderers\":[{\"id\":\"1033\",\"type\":\"GlyphRenderer\"},{\"id\":\"1038\",\"type\":\"GlyphRenderer\"}],\"title\":{\"id\":\"1003\",\"type\":\"Title\"},\"toolbar\":{\"id\":\"1026\",\"type\":\"Toolbar\"},\"x_range\":{\"id\":\"1043\",\"type\":\"Range1d\"},\"x_scale\":{\"id\":\"1009\",\"type\":\"LinearScale\"},\"y_range\":{\"id\":\"1042\",\"type\":\"Range1d\"},\"y_scale\":{\"id\":\"1011\",\"type\":\"LinearScale\"}},\"id\":\"1002\",\"subtype\":\"Figure\",\"type\":\"Plot\"},{\"attributes\":{\"data_source\":{\"id\":\"1030\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"1031\",\"type\":\"Line\"},\"hover_glyph\":null,\"muted_glyph\":null,\"nonselection_glyph\":{\"id\":\"1032\",\"type\":\"Line\"},\"selection_glyph\":null,\"view\":{\"id\":\"1034\",\"type\":\"CDSView\"}},\"id\":\"1033\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"source\":{\"id\":\"1035\",\"type\":\"ColumnDataSource\"}},\"id\":\"1039\",\"type\":\"CDSView\"},{\"attributes\":{\"fill_alpha\":{\"value\":0.1},\"fill_color\":{\"value\":\"#1f77b4\"},\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"size\":{\"units\":\"screen\",\"value\":8},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"1037\",\"type\":\"Circle\"},{\"attributes\":{},\"id\":\"1047\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"fill_color\":{\"value\":\"#1f77b4\"},\"line_color\":{\"value\":\"#1f77b4\"},\"size\":{\"units\":\"screen\",\"value\":8},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"1036\",\"type\":\"Circle\"},{\"attributes\":{},\"id\":\"1019\",\"type\":\"BasicTicker\"},{\"attributes\":{\"dimensions\":\"width\"},\"id\":\"1024\",\"type\":\"WheelZoomTool\"},{\"attributes\":{},\"id\":\"1045\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"ticker\":{\"id\":\"1014\",\"type\":\"BasicTicker\"}},\"id\":\"1017\",\"type\":\"Grid\"},{\"attributes\":{\"line_alpha\":0.1,\"line_color\":\"#1f77b4\",\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"1032\",\"type\":\"Line\"},{\"attributes\":{},\"id\":\"1048\",\"type\":\"UnionRenderers\"},{\"attributes\":{\"source\":{\"id\":\"1030\",\"type\":\"ColumnDataSource\"}},\"id\":\"1034\",\"type\":\"CDSView\"},{\"attributes\":{\"ticks\":[1,2,3,4]},\"id\":\"1040\",\"type\":\"FixedTicker\"},{\"attributes\":{\"callback\":null,\"end\":5},\"id\":\"1042\",\"type\":\"Range1d\"},{\"attributes\":{},\"id\":\"1014\",\"type\":\"BasicTicker\"},{\"attributes\":{\"dimensions\":\"width\"},\"id\":\"1023\",\"type\":\"PanTool\"},{\"attributes\":{\"callback\":null,\"tooltips\":[[\"n\",\"@x\"],[\"X_n\",\"@y\"]]},\"id\":\"1025\",\"type\":\"HoverTool\"},{\"attributes\":{\"text\":\"DTMC Sample Path\"},\"id\":\"1003\",\"type\":\"Title\"},{\"attributes\":{\"axis_label\":\"X_n\",\"formatter\":{\"id\":\"1045\",\"type\":\"BasicTickFormatter\"},\"ticker\":{\"id\":\"1040\",\"type\":\"FixedTicker\"}},\"id\":\"1018\",\"type\":\"LinearAxis\"},{\"attributes\":{},\"id\":\"1049\",\"type\":\"Selection\"},{\"attributes\":{\"callback\":null,\"data\":{\"x\":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50],\"y\":[1,2,1,2,3,2,1,4,3,2,3,4,3,4,3,2,1,4,3,4,3,4,3,2,1,4,1,2,3,2,1,2,3,2,1,4,1,4,1,4,3,4,3,4,3,4,3,2,3,2,1]},\"selected\":{\"id\":\"1049\",\"type\":\"Selection\"},\"selection_policy\":{\"id\":\"1048\",\"type\":\"UnionRenderers\"}},\"id\":\"1030\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"line_color\":\"silver\",\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"1031\",\"type\":\"Line\"},{\"attributes\":{},\"id\":\"1009\",\"type\":\"LinearScale\"},{\"attributes\":{},\"id\":\"1011\",\"type\":\"LinearScale\"},{\"attributes\":{\"active_drag\":{\"id\":\"1023\",\"type\":\"PanTool\"},\"active_inspect\":\"auto\",\"active_multi\":null,\"active_scroll\":{\"id\":\"1024\",\"type\":\"WheelZoomTool\"},\"active_tap\":\"auto\",\"tools\":[{\"id\":\"1023\",\"type\":\"PanTool\"},{\"id\":\"1024\",\"type\":\"WheelZoomTool\"},{\"id\":\"1025\",\"type\":\"HoverTool\"}]},\"id\":\"1026\",\"type\":\"Toolbar\"},{\"attributes\":{\"axis_label\":\"n\",\"formatter\":{\"id\":\"1047\",\"type\":\"BasicTickFormatter\"},\"ticker\":{\"id\":\"1014\",\"type\":\"BasicTicker\"}},\"id\":\"1013\",\"type\":\"LinearAxis\"},{\"attributes\":{\"callback\":null,\"data\":{\"x\":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50],\"y\":[1,2,1,2,3,2,1,4,3,2,3,4,3,4,3,2,1,4,3,4,3,4,3,2,1,4,1,2,3,2,1,2,3,2,1,4,1,4,1,4,3,4,3,4,3,4,3,2,3,2,1]},\"selected\":{\"id\":\"1051\",\"type\":\"Selection\"},\"selection_policy\":{\"id\":\"1050\",\"type\":\"UnionRenderers\"}},\"id\":\"1035\",\"type\":\"ColumnDataSource\"},{\"attributes\":{},\"id\":\"1050\",\"type\":\"UnionRenderers\"},{\"attributes\":{\"data_source\":{\"id\":\"1035\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"1036\",\"type\":\"Circle\"},\"hover_glyph\":null,\"muted_glyph\":null,\"nonselection_glyph\":{\"id\":\"1037\",\"type\":\"Circle\"},\"selection_glyph\":null,\"view\":{\"id\":\"1039\",\"type\":\"CDSView\"}},\"id\":\"1038\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"bounds\":[-1,52],\"callback\":null,\"end\":51,\"start\":-1},\"id\":\"1043\",\"type\":\"Range1d\"},{\"attributes\":{},\"id\":\"1051\",\"type\":\"Selection\"},{\"attributes\":{\"dimension\":1,\"ticker\":{\"id\":\"1019\",\"type\":\"BasicTicker\"}},\"id\":\"1022\",\"type\":\"Grid\"}],\"root_ids\":[\"1002\"]},\"title\":\"Bokeh Application\",\"version\":\"1.3.4\"}};\n",
       "  var render_items = [{\"docid\":\"7ea2ae7d-cb9c-499e-b1cd-3417c57c772b\",\"notebook_comms_target\":\"1052\",\"roots\":{\"1002\":\"d411fcc6-2b22-47a6-8b3d-67233f4fc91d\"}}];\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": "1002"
      }
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot, handle = dtmc.plot_path(sample_path, S, show_line=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "b7f554959cdc491db3461c35a145f220",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='n', max=50), Output()), _dom_classes=('widget-interact',…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "widgets.interact(lambda y: dtmc.draw_rat_maze(sample_path['X'][y]), y=n_slider);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Transition Diagram Representation\n",
    "\n",
    "The below visualization is essentially the same as the one above.  The only difference is that we are representing the layout of the maze in a new way (by what mathematicians call a ”directed [graph](https://en.wikipedia.org/wiki/Graph_(discrete_mathematics))”).  In the context of Markov chains, this is called a **transition diagram.**\n",
    "\n",
    "In this case, each room is represented as a circle (or a “node”) and each door as a two-headed arrow (or a directed “edge”).  An adjoining room is any one that is connected by an edge.\n",
    "\n",
    "Because it will be more generally useful, we will use transition diagram representation instead of the floorplan-style layout from now on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "93a84328026c4d09ad0f1ad99e2a2b74",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='n', max=50), Output()), _dom_classes=('widget-interact',…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import mcviz\n",
    "\n",
    "mcviz.draw_interact(P, S, sample_path, bidir=True, n_slider=n_slider)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** These transition diagrams are drawn using a program called [graphviz](https://www.graphviz.org/) and the Python package [python-graphviz](https://graphviz.readthedocs.io/en/stable/) allows us to access this from Python (along with some helpful features).  These packages may not be automatically included in the Anaconda Distribution, in which case you will need to [install these packages](https://docs.anaconda.com/anaconda/navigator/tutorials/manage-packages/) in the environment you are using.  Azure Notebooks already includes them."
   ]
  }
 ],
 "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
}