2-2-DTMC-MathConcepts.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DTMC: Section 2 - Mathematical Concepts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Section 1, we introduced a toy model of a “rat” moving randomly around a ”maze” and looked at a simulated sample path.  \n",
    "\n",
    "In this section, we will introduce some concepts that help us describe the *stochastic process* that represents the random path of the rat in the maze.  These are concepts that are fundamental to Markov chains, which are the underlying theme of this course.\n",
    "\n",
    "Remember that the stochastic process is denoted $\\{X_n\\}$ (or $\\{X_n, n \\geq 0\\}$) is a sequence of random variables:\n",
    "\n",
    "$$ (X_0, X_1, X_2, \\dots) $$\n",
    "\n",
    "where $X_n$ represents the room the rat is in after the $n$th move (so $X_0$ is the starting position of the rat) and the time index $n$ may take values $0, 1, 2, \\dots$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## State Space\n",
    "\n",
    "This is the set of values that a stochastic process can move among (you can think of these as “locations” but in the abstract, just needs to be a number and does not have to represent any sort of physical location).\n",
    "\n",
    "**Notation:** We denote the state space of a Markov chain as $\\mathcal{S}$.\n",
    "\n",
    "For the rat in the maze example of Section 1, the state space is\n",
    "\n",
    "$$ \\mathcal{S} = \\{1, 2, 3, 4\\} $$\n",
    "\n",
    "where each state represents a particular room in the maze."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Transition Probabilities\n",
    "\n",
    "Each random variable $X_n$ in the sequence represents the location of the stochastic process (in the state space) at a time $n$.\n",
    "\n",
    "We can think of a time step as a transition:\n",
    "* $X_0 \\to X_1$: one-step transition (or $X_n \\to X_{n+1}$)\n",
    "* $X_0 \\to X_2$: two-step transition (or $X_n \\to X_{n+2}$)\n",
    "* ...\n",
    "* $X_0 \\to X_m$: $m$-step transition (or $X_n \\to X_{n+m}$)\n",
    "\n",
    "and define the *transition probability* $p_{ij}$ using conditional probability:\n",
    "$$ p_{ij} \\overset{\\mathsf{def}}{=} \\mathsf{P}\\left(X_1 = j \\,|\\, X_0 = i\\right) $$\n",
    "The probability that the stochastic process next moves to state $j$ given that we are in state $i$.\n",
    "\n",
    "Similarly, the $m$-step transition probability:\n",
    "$$ \\mathsf{P}\\left(X_m = j \\,|\\, X_0 = i\\right) $$\n",
    "\n",
    "In Section 1, Exercise 1.2, you wrote out all the one-step transition probabilities in a table:\n",
    "\n",
    "| one-step trans. prob. | to state 1  | to state 2   | to state 3   | to state 4   |\n",
    "|:--- |:---:|:---:|:---:|:---:|\n",
    "| from state 1 |  0  | 1/2 |  0  | 1/2 | \n",
    "| from state 2 | 1/2 |  0  | 1/2 |  0  |\n",
    "| from state 3 |  0  | 1/2 |  0  | 1/2 | \n",
    "| from state 4 | 1/2 |  0  | 1/2 |  0  |\n",
    "\n",
    "We will write this as a (square) matrix $\\mathbf{P}$ called the **transition probability matrix** where the element in the $i$th row and $j$th column of the matrix is the one-step transition probability *from* state $i$ *to* state $j$:\n",
    "\n",
    "$$\\mathbf{P} = \\begin{pmatrix} \n",
    "    p_{1 1} & p_{1 2} & p_{1 3} & p_{1 4} \\\\\n",
    "    p_{2 1} & p_{2 2} & p_{2 3} & p_{2 4} \\\\\n",
    "    p_{3 1} & p_{3 2} & p_{3 3} & p_{3 4} \\\\\n",
    "    p_{4 1} & p_{4 2} & p_{4 3} & p_{4 4} \\\\\n",
    "  \\end{pmatrix} =\n",
    "  \\begin{pmatrix}\n",
    "    0 & 1/2 & 0 & 1/2 \\\\\n",
    "    1/2 & 0 & 1/2 & 0 \\\\\n",
    "    0 & 1/2 & 0 & 1/2 \\\\\n",
    "    1/2 & 0 & 1/2 & 0 \\\\\n",
    "  \\end{pmatrix}$$\n",
    "\n",
    "This is simply notation, but it will enable us to write things concisely with vectors, matrices, linear algebra.\n",
    "\n",
    "**Important:** Please make sure that you follow the convention of representing $\\mathbf{P}$ as described above.  In particular, each row of $\\mathbf{P}$ must sum to $1$.  (You should be able to explain why.)  In this particular example, due to the layout of the rooms and assumptions of the model, the columns also happen to sum to $1$, but we will see other DTMC examples where that is not the case."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2.1\n",
    "\n",
    "For the rat in the maze:\n",
    "\n",
    "* What is the probability that $X_1 = 1$ given $X_0 = 2$?\n",
    "    \n",
    "    $ \\mathsf{P}\\left(X_1 = 1 \\,|\\, X_0 = 2\\right) = $\n",
    "\n",
    "\n",
    "* What is the probability that $X_2 = 1$ given $X_0 = 1$ and $X_1 = 2$?\n",
    "    \n",
    "    $ \\mathsf{P}\\left(X_2 = 1 \\,|\\, X_0 = 1,\\ X_1 = 2 \\right) = $\n",
    "    \n",
    "    \n",
    "* What is the probability that $X_2 = 1$ given $X_0 = 3$ and $X_1 = 2$?\n",
    "    \n",
    "    $ \\mathsf{P}\\left(X_2 = 1 \\,|\\, X_0 = 3,\\ X_1 = 2 \\right) = $\n",
    "    \n",
    "    \n",
    "* What about\n",
    "    \n",
    "    $ \\mathsf{P}\\left(X_4 = 1 \\,|\\, X_0 = 2, X_2 = 3, X_3 = 2\\right) = $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Markov Property"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exercise 2.1 should emphasize that, according to our model assumptions, each of the above is simply $p_{21} = 1/2$ -- the future path of the rat does not depend on the past that brought the rat to room 2.\n",
    "\n",
    "In general, this is known as the Markov property (a property of some stochastic processes):\n",
    "\n",
    "$$ \\mathsf{P}\\left(X_{n+1} = j \\,|\\, X_0 = i_0, X_1 = i_1, \\dots, X_n = i\\right) = \\mathsf{P}\\left(X_{n+1} = j \\,|\\, X_n = i\\right) $$\n",
    "\n",
    "Based on the assumptions of our toy model, the stochastic process representing the path of the rat through the maze satisfies the Markov property.\n",
    "\n",
    "Interpretation(s):\n",
    "* The stochastic process has no memory of the past (may depend on the present).\n",
    "* The future path is independent of the past history (given the present state).\n",
    "\n",
    "**Remember:** This is a property of some (but not all) stochastic processes.\n",
    "\n",
    "**Note:**  This property is named after the Russian Mathematician [Andrey Markov](https://en.wikipedia.org/wiki/Andrey_Markov) and the class of stochastic processes that satisfy this property are known as Markov processes (of which Markov chains are a subclass).  However, you may find it more useful or functional to think of the Markov property as a “memoryless” property."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Discrete-Time Markov Chain (definition)\n",
    "\n",
    "**Definition:** A discrete-time Markov chain is:\n",
    "* a stochastic process $\\{X_n, n \\geq 0\\}$\n",
    "* that lives on a (countable) state space $\\mathcal{S}$\n",
    "* and satisfies the Markov property\n",
    "    \n",
    "    $$ \\mathsf{P}\\left(X_{n+1} = j \\,|\\, X_0 = i_0, X_1 = i_1, \\dots, X_n = i\\right) = \\mathsf{P}\\left(X_{n+1} = j \\,|\\, X_n = i\\right) $$\n",
    "    \n",
    "    for all times $n \\geq 0$ and states $i, j \\in \\mathcal{S}$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Transition Diagram\n",
    "\n",
    "We saw in Section 1 that we can represent the stochastic process by its **transition diagram**: each state in $\\mathcal{S}$ is represented as a circle and each (non-zero one-step) transition as an arrow.  \n",
    "\n",
    "For a general Markov chain, some transitions may be only in one direction and we need to specify the probability associated with each transition.  For the rat in the maze example(s), the basic model assumptions imply that all transitions occur can in either direction and the probability of each transition can be deduced from only the nodes and edges."
   ]
  },
  {
   "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"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathcal{S} = \\{1,2,3,4\\}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\mathbf{P} = \\pmatrix{0& 1/2& 0& 1/2\\\\ 1/2& 0& 1/2& 0\\\\ 0& 1/2& 0& 1/2\\\\ 1/2& 0& 1/2& 0}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"182pt\" height=\"182pt\"\n",
       " viewBox=\"0.00 0.00 181.51 181.51\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 177.5099)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-177.5099 177.5099,-177.5099 177.5099,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"86.7549\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"86.7549\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-86.7549\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-83.0549\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M66.6772,-38.0778C57.6491,-47.1058 47.0199,-57.735 38.001,-66.754\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"69.2264,-40.4783 73.8227,-30.9323 64.2767,-35.5285 69.2264,-40.4783\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"35.4705,-64.3347 30.8743,-73.8806 40.4203,-69.2844 35.4705,-64.3347\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"155.5099\" cy=\"-86.7549\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"155.5099\" y=\"-83.0549\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;4 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M106.8327,-38.0778C115.8608,-47.1058 126.4899,-57.735 135.5089,-66.754\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"109.2332,-35.5285 99.6872,-30.9323 104.2834,-40.4783 109.2332,-35.5285\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"133.0896,-69.2844 142.6356,-73.8806 138.0394,-64.3347 133.0896,-69.2844\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"86.7549\" cy=\"-155.5099\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"86.7549\" y=\"-151.8099\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M38.0778,-106.8327C47.1058,-115.8608 57.735,-126.4899 66.754,-135.5089\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"40.4783,-104.2834 30.9323,-99.6872 35.5285,-109.2332 40.4783,-104.2834\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"64.3347,-138.0394 73.8806,-142.6356 69.2844,-133.0896 64.3347,-138.0394\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M106.8327,-135.4321C115.8608,-126.404 126.4899,-115.7749 135.5089,-106.7559\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"104.2834,-133.0316 99.6872,-142.5776 109.2332,-137.9814 104.2834,-133.0316\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"138.0394,-109.1752 142.6356,-99.6292 133.0896,-104.2254 138.0394,-109.1752\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7ff0e0148a10>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "from IPython.display import display, Math\n",
    "\n",
    "import dtmc\n",
    "import mcviz\n",
    "\n",
    "P = np.array([[0, 0.5, 0, 0.5],\n",
    "              [0.5, 0, 0.5, 0],\n",
    "              [0, 0.5, 0, 0.5],\n",
    "              [0.5, 0, 0.5, 0]])\n",
    "\n",
    "S = [1, 2, 3, 4]\n",
    "\n",
    "dtmc.disp_dtmc(P, S, frac=True)\n",
    "display(mcviz.dot_mc(P, list(map(str, S)), bidir=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2.2: Maze Examples\n",
    "\n",
    "For each of the following mazes, write down the state space $\\mathcal{S}$ and (one-step) transition probability matrix $\\mathbf{P}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"152pt\" height=\"44pt\"\n",
       " viewBox=\"0.00 0.00 152.00 44.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 40)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-40 148,-40 148,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"126\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M46.46,-18C62.2878,-18 81.9189,-18 97.718,-18\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.3208,-14.5001 36.3207,-18 46.3207,-21.5001 46.3208,-14.5001\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"97.9499,-21.5001 107.9498,-18 97.9498,-14.5001 97.9499,-21.5001\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7ff0b08f8490>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mcviz.dot_mc([[0, 1], [1, 0]], ['1', '2'], bidir=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"260pt\" height=\"44pt\"\n",
       " viewBox=\"0.00 0.00 260.00 44.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 40)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-40 256,-40 256,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"126\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M46.46,-18C62.2878,-18 81.9189,-18 97.718,-18\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"46.3208,-14.5001 36.3207,-18 46.3207,-21.5001 46.3208,-14.5001\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"97.9499,-21.5001 107.9498,-18 97.9498,-14.5001 97.9499,-21.5001\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"234\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M154.46,-18C170.2878,-18 189.9189,-18 205.718,-18\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"154.3208,-14.5001 144.3207,-18 154.3207,-21.5001 154.3208,-14.5001\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"205.9499,-21.5001 215.9498,-18 205.9498,-14.5001 205.9499,-21.5001\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7ff0e0148810>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mcviz.dot_mc([[0, 1, 0], [0.5, 0, 0.5], [0, 1, 0]], ['1', '2', '3'], bidir=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: Markov chain Pages: 1 -->\n",
       "<svg width=\"136pt\" height=\"188pt\"\n",
       " viewBox=\"0.00 0.00 136.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\n",
       "<title>Markov chain</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-184 132,-184 132,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"37\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"37\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M29.8072,-134.7429C28.3022,-129.0398 26.715,-123.0251 25.2094,-117.3197\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"26.4649,-135.7949 32.4006,-144.5708 33.2332,-134.0087 26.4649,-135.7949\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"28.5586,-116.2942 22.6229,-107.5182 21.7903,-118.0803 28.5586,-116.2942\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"64\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"64\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;5 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M42.2293,-134.1102C47.0016,-108.6584 54.017,-71.2424 58.7848,-45.8143\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"38.7679,-133.5797 40.365,-144.0535 45.648,-134.8698 38.7679,-133.5797\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"62.2745,-46.1941 60.6774,-35.7204 55.3944,-44.904 62.2745,-46.1941\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;5 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M33.2569,-66.1196C38.2329,-58.3311 43.7563,-49.6857 48.7331,-41.8961\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"30.1899,-64.4193 27.7554,-74.7307 36.0888,-68.1881 30.1899,-64.4193\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"51.8241,-43.5587 54.2586,-33.2473 45.9253,-39.7899 51.8241,-43.5587\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"110\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"110\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"110\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"110\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\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=\"M110,-133.5726C110,-128.6792 110,-123.5904 110,-118.6901\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"106.5001,-133.8313 110,-143.8314 113.5001,-133.8314 106.5001,-133.8313\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"113.5001,-118.4132 110,-108.4133 106.5001,-118.4133 113.5001,-118.4132\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M94.7431,-66.1196C89.7671,-58.3311 84.2437,-49.6857 79.2669,-41.8961\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"91.9112,-68.1881 100.2446,-74.7307 97.8101,-64.4193 91.9112,-68.1881\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"82.0747,-39.7899 73.7414,-33.2473 76.1759,-43.5587 82.0747,-39.7899\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7ff0c0ca1310>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 5 # number of rooms\n",
    "mcviz.dot_mc(dtmc.rand_maze(n, p = [0,0.3,0.4,0.3]), list(map(str, range(1,n+1))), engine='dot', bidir=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** The codeblock above randomly generates a maze with $n$ rooms.  Re-run the codeblock to get new mazes.  You can change the number of rooms."
   ]
  }
 ],
 "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
}