3-3-RW-Reflected.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "import ipywidgets as widgets\n",
    "from IPython.display import display, Math"
   ]
  },
  {
   "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=\"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 bokeh.plotting as bplt\n",
    "from bokeh.models import Range1d, LabelSet, ColumnDataSource\n",
    "from bokeh.models.glyphs import Step, Line\n",
    "from bokeh.io import output_notebook, push_notebook\n",
    "output_notebook()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Random Walk: Section 3 - Reflecting Barriers\n",
    "\n",
    "In the simple random walk (every step was up or down by 1), we had an infinite state space Markov chain that was either transient (for $p \\neq 0.5$) or null recurrent ($p = 0.5$).  There was no value of $p$ that allowed for a positive recurrent random walk.\n",
    "\n",
    "To see an example of an infinite state space Markov chain that is positive recurrent, we will add a “reflecting barrier” to the random walk.  In particular, we restrict the state space to the *non-negative* integers $\\mathcal{S} = \\{0, 1, 2, 3, \\dots\\}$ and make $p_{00} = 1 - p$.\n",
    "\n",
    "For any state $i \\geq 1$, the behavior is exactly the same as the simple random walk:\n",
    "$$p_{ij} = \\begin{cases}\n",
    "    p & j = i + 1 \\\\\n",
    "    1 - p & j = i - 1 \\\\\n",
    "    0 & \\text{otherwise (i.e., any other state $j$)}\n",
    "  \\end{cases}$$\n",
    "only the behavior for state $0$ changes:\n",
    "$$p_{01} = p \\qquad p_{00} = 1 - p$$\n",
    "If you were to write (part of) this in the usual matrix form, it would be:\n",
    "$$\\mathbf{P} = \\begin{pmatrix}\n",
    "    1-p & p & 0 & 0 & \\dots \\\\\n",
    "    1-p & 0 & p & 0 & \\dots \\\\\n",
    "    0 & 1-p & 0 & p & \\dots \\\\\n",
    "    0 & 0 & 1-p & 0 & \\dots \\\\\n",
    "    \\vdots & \\vdots & \\vdots & \\vdots & \\ddots \\\\\n",
    "  \\end{pmatrix}$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Positive Recurrence for $p < 0.5$\n",
    "\n",
    "As with the original random walk, you should (quickly) check that this Markov chain is irreducible.\n",
    "\n",
    "We will show that, for $p < 0.5$, the Markov chain is positive recurrent.  To do so, we will rely on the theorem from Section 6 of Discrete-Time Markov Chains, which we restate here.\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",
    "So if we can find a solution $\\pi$ that satisfies the above, then the Markov chain is positive recurrent.  The basic steps will be the same as when we had a finite state space:\n",
    "* Write a system of equations.\n",
    "* Solve for $\\pi$.\n",
    "\n",
    "However, we will need a way to handle the fact that there are an infinite number of equations and elements of $\\pi$ to solve.  We will do so by identifying a recursion relationship and applying the [principle of mathematical induction](https://en.wikipedia.org/wiki/Mathematical_induction).\n",
    "\n",
    "We will start by listing the system of equations $\\pi = \\pi \\mathbf{P}$:\n",
    "$$\\begin{aligned}\n",
    "    \\pi_0 &= (1 - p) \\pi_0 + (1 - p) \\pi_1 \\\\\n",
    "    \\pi_1 &= p \\pi_0 + (1 - p) \\pi_2 \\\\\n",
    "    \\pi_2 &= p \\pi_1 + (1 - p) \\pi_3 \\\\\n",
    "    &\\,\\,\\vdots \\\\\n",
    "    \\pi_i &= p \\pi_{i-1} + (1 - p) \\pi_{i+1} \\qquad i \\geq 1\n",
    "  \\end{aligned}$$\n",
    "  \n",
    "**Base Case:** The first equation (for $\\pi_0$) yields a relationship between state $1$ and state $0$:\n",
    "$$\\begin{aligned}\n",
    "    \\pi_0 &= (1 - p) \\pi_0 + (1 - p) \\pi_1 \\\\\n",
    "    p \\pi_0 &= (1 - p) \\pi_1 \\\\\n",
    "  \\end{aligned}$$\n",
    "Combining this with the second equation (for $\\pi_1$) yields:\n",
    "$$\\begin{aligned}\n",
    "    \\pi_1 &= p \\pi_0 + (1 - p) \\pi_2 \\\\\n",
    "    \\pi_1 &= (1 - p) \\pi_1 + (1 - p) \\pi_2 \\\\\n",
    "    p \\pi_1 &= (1 - p) \\pi_2\n",
    "  \\end{aligned}$$\n",
    "**Inductive Step:** We see that this pattern repeats in the sense that, if the pattern holds for states $i-1$ and $i$ ($p \\pi_{i-1} = (1 - p) \\pi_i$) then\n",
    "$$\\begin{aligned}\n",
    "    \\pi_i &= p \\pi_{i-1} + (1 - p) \\pi_{i+1} \\\\\n",
    "    \\pi_i &= (1 - p) \\pi_i + (1 - p) \\pi_{i+1} \\\\\n",
    "    p \\pi_i &= (1 - p) \\pi_{i+1}\n",
    "  \\end{aligned}$$\n",
    "the pattern holds for states $i$ and $i + 1$.\n",
    "\n",
    "Therefore, we have the following *recursion*, for all $i \\geq 0$:\n",
    "$$\\pi_{i+1} = \\frac{p}{1-p} \\pi_i$$\n",
    "\n",
    "Building this up from $i = 0$:\n",
    "$$\\begin{aligned}\n",
    "    \\pi_1 &= \\frac{p}{1 - p} \\pi_0 \\\\\n",
    "    \\pi_2 &= \\frac{p}{1 - p} \\pi_1 = \\left(\\frac{p}{1 - p}\\right)^2 \\pi_0 \\\\\n",
    "    \\pi_3 &= \\frac{p}{1 - p} \\pi_2 = \\left(\\frac{p}{1 - p}\\right)^3 \\pi_0 \\\\\n",
    "    &\\,\\,\\vdots \\\\\n",
    "    \\pi_i &= \\frac{p}{1 - p} \\pi_{i-1} = \\left(\\frac{p}{1 - p}\\right)^i \\pi_0 \\\\\n",
    "  \\end{aligned}$$\n",
    "\n",
    "At this point we only have one “unknown” to solve for: $\\pi_0$.  Fortunately, we have another equation to use, $\\sum_j \\pi_j = 1$.\n",
    "$$\\begin{aligned}\n",
    "    \\sum_{i=0}^\\infty \\pi_i &= 1 \\\\\n",
    "    \\sum_{i=0}^\\infty \\left(\\frac{p}{1 - p}\\right)^i \\pi_0 &= 1 \\\\\n",
    "    \\pi_0 \\left(\\sum_{i=0}^\\infty \\left(\\frac{p}{1 - p}\\right)^i\\right) &= 1 \\\\\n",
    "    \\pi_0 \\left(\\frac{1}{1 - \\frac{p}{1-p}}\\right) &= 1 \\\\\n",
    "    \\pi_0 &= 1 - \\frac{p}{1-p} \\\\\n",
    "  \\end{aligned}$$\n",
    "\n",
    "In summary, the stationary distribution for the reflected random walk ($p < 0.5$) is:\n",
    "$$ \\pi_i = \\left(\\frac{p}{1 - p}\\right)^i \\left(1 - \\frac{p}{1-p}\\right) \\qquad \\text{for any } i \\in \\mathcal{S} = \\{0, 1, 2, 3, \\dots\\}$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = 0.7\n",
    "steps = 1000\n",
    "X_0 = 0\n",
    "delta = np.random.choice([-1,1], size=[1,steps], p=[1-p, p])\n",
    "sample_path = pd.DataFrame(np.append(np.array(X_0), np.cumsum(delta)), index=pd.Index(range(0,steps+1)), columns=['Random Walk'])\n",
    "sample_path['Regulator'] = sample_path['Random Walk'].cummin()\n",
    "sample_path['Reflected Random Walk'] = sample_path['Random Walk'] - sample_path['Regulator']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "  <div class=\"bk-root\" id=\"4139b64d-5a8d-436c-9671-0e3492ebacb5\" 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 = {\"226399c9-2ccf-4216-9090-d3190c39c315\":{\"roots\":{\"references\":[{\"attributes\":{\"below\":[{\"id\":\"1013\",\"type\":\"LinearAxis\"}],\"center\":[{\"id\":\"1017\",\"type\":\"Grid\"},{\"id\":\"1022\",\"type\":\"Grid\"}],\"left\":[{\"id\":\"1018\",\"type\":\"LinearAxis\"}],\"renderers\":[{\"id\":\"1038\",\"type\":\"GlyphRenderer\"}],\"title\":{\"id\":\"1003\",\"type\":\"Title\"},\"toolbar\":{\"id\":\"1029\",\"type\":\"Toolbar\"},\"x_range\":{\"id\":\"1005\",\"type\":\"DataRange1d\"},\"x_scale\":{\"id\":\"1009\",\"type\":\"LinearScale\"},\"y_range\":{\"id\":\"1007\",\"type\":\"DataRange1d\"},\"y_scale\":{\"id\":\"1011\",\"type\":\"LinearScale\"}},\"id\":\"1002\",\"subtype\":\"Figure\",\"type\":\"Plot\"},{\"attributes\":{},\"id\":\"1026\",\"type\":\"SaveTool\"},{\"attributes\":{\"active_drag\":\"auto\",\"active_inspect\":\"auto\",\"active_multi\":null,\"active_scroll\":\"auto\",\"active_tap\":\"auto\",\"tools\":[{\"id\":\"1023\",\"type\":\"PanTool\"},{\"id\":\"1024\",\"type\":\"WheelZoomTool\"},{\"id\":\"1025\",\"type\":\"BoxZoomTool\"},{\"id\":\"1026\",\"type\":\"SaveTool\"},{\"id\":\"1027\",\"type\":\"ResetTool\"},{\"id\":\"1028\",\"type\":\"HelpTool\"}]},\"id\":\"1029\",\"type\":\"Toolbar\"},{\"attributes\":{},\"id\":\"1023\",\"type\":\"PanTool\"},{\"attributes\":{\"source\":{\"id\":\"1036\",\"type\":\"ColumnDataSource\"}},\"id\":\"1039\",\"type\":\"CDSView\"},{\"attributes\":{},\"id\":\"1042\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"overlay\":{\"id\":\"1045\",\"type\":\"BoxAnnotation\"}},\"id\":\"1025\",\"type\":\"BoxZoomTool\"},{\"attributes\":{},\"id\":\"1046\",\"type\":\"UnionRenderers\"},{\"attributes\":{},\"id\":\"1019\",\"type\":\"BasicTicker\"},{\"attributes\":{},\"id\":\"1024\",\"type\":\"WheelZoomTool\"},{\"attributes\":{},\"id\":\"1027\",\"type\":\"ResetTool\"},{\"attributes\":{\"line_color\":\"blue\",\"x\":{\"field\":\"index\"},\"y\":{\"field\":\"Reflected Random Walk\"}},\"id\":\"1037\",\"type\":\"Line\"},{\"attributes\":{},\"id\":\"1047\",\"type\":\"Selection\"},{\"attributes\":{\"formatter\":{\"id\":\"1042\",\"type\":\"BasicTickFormatter\"},\"ticker\":{\"id\":\"1014\",\"type\":\"BasicTicker\"}},\"id\":\"1013\",\"type\":\"LinearAxis\"},{\"attributes\":{\"callback\":null},\"id\":\"1005\",\"type\":\"DataRange1d\"},{\"attributes\":{\"align\":\"center\",\"text\":\"Reflected Random Walk\",\"text_font_size\":{\"value\":\"25px\"}},\"id\":\"1003\",\"type\":\"Title\"},{\"attributes\":{},\"id\":\"1014\",\"type\":\"BasicTicker\"},{\"attributes\":{\"formatter\":{\"id\":\"1044\",\"type\":\"BasicTickFormatter\"},\"ticker\":{\"id\":\"1019\",\"type\":\"BasicTicker\"}},\"id\":\"1018\",\"type\":\"LinearAxis\"},{\"attributes\":{},\"id\":\"1044\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{},\"id\":\"1009\",\"type\":\"LinearScale\"},{\"attributes\":{\"data_source\":{\"id\":\"1036\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"1037\",\"type\":\"Line\"},\"hover_glyph\":null,\"muted_glyph\":null,\"view\":{\"id\":\"1039\",\"type\":\"CDSView\"}},\"id\":\"1038\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"bottom_units\":\"screen\",\"fill_alpha\":{\"value\":0.5},\"fill_color\":{\"value\":\"lightgrey\"},\"left_units\":\"screen\",\"level\":\"overlay\",\"line_alpha\":{\"value\":1.0},\"line_color\":{\"value\":\"black\"},\"line_dash\":[4,4],\"line_width\":{\"value\":2},\"render_mode\":\"css\",\"right_units\":\"screen\",\"top_units\":\"screen\"},\"id\":\"1045\",\"type\":\"BoxAnnotation\"},{\"attributes\":{\"ticker\":{\"id\":\"1014\",\"type\":\"BasicTicker\"}},\"id\":\"1017\",\"type\":\"Grid\"},{\"attributes\":{\"dimension\":1,\"ticker\":{\"id\":\"1019\",\"type\":\"BasicTicker\"}},\"id\":\"1022\",\"type\":\"Grid\"},{\"attributes\":{},\"id\":\"1011\",\"type\":\"LinearScale\"},{\"attributes\":{\"callback\":null},\"id\":\"1007\",\"type\":\"DataRange1d\"},{\"attributes\":{},\"id\":\"1028\",\"type\":\"HelpTool\"},{\"attributes\":{\"callback\":null,\"data\":{\"Random Walk\":[0,1,2,3,2,1,0,1,2,3,4,3,2,1,2,3,2,1,2,3,2,3,2,3,4,3,2,3,4,5,6,7,8,9,8,9,8,9,8,9,10,9,8,9,8,9,10,11,10,11,12,13,14,15,16,17,18,19,20,21,20,21,22,21,20,19,20,19,18,19,18,19,20,19,20,21,20,21,20,21,22,23,24,23,22,21,22,23,22,21,22,21,22,23,24,23,24,23,24,25,24,25,26,25,26,25,26,25,26,27,26,27,26,27,28,27,28,29,30,31,32,33,34,35,36,37,38,39,40,39,40,39,40,41,40,41,40,41,42,43,44,43,42,41,40,41,42,43,44,45,46,47,46,47,48,47,46,47,46,45,46,47,48,49,48,47,48,49,50,51,52,51,52,53,54,55,56,57,58,59,58,59,60,59,60,59,60,59,58,59,60,61,60,59,60,61,60,61,62,63,64,63,64,65,66,67,68,69,68,69,70,71,72,73,74,75,76,77,78,79,80,79,80,81,82,81,80,81,82,81,82,83,84,85,84,85,86,87,86,85,86,87,88,89,88,89,88,89,90,89,90,91,90,89,90,91,90,91,90,89,90,91,90,91,92,93,94,93,94,93,94,95,96,97,96,95,96,97,98,99,100,99,100,99,100,99,100,99,100,99,100,99,100,99,100,99,100,101,102,103,104,105,106,107,108,109,110,111,110,111,112,111,110,111,110,109,110,109,110,111,112,113,112,111,110,111,110,111,112,111,112,113,114,113,114,115,116,117,118,119,118,119,118,119,118,119,120,119,118,119,120,121,120,121,120,119,118,119,120,119,118,119,120,121,122,123,122,121,120,119,118,119,118,119,118,117,118,119,120,121,122,123,124,125,124,125,124,125,126,125,126,127,126,127,128,129,128,127,128,129,128,127,128,129,130,129,130,131,132,133,134,135,134,135,134,135,136,137,136,135,136,135,134,135,136,135,134,135,136,137,138,139,140,141,140,141,142,143,144,143,144,145,146,147,148,147,148,147,146,145,146,147,146,145,144,145,146,147,148,147,148,147,148,149,150,151,152,153,154,155,154,155,156,157,158,159,158,159,158,159,160,159,158,157,158,159,158,159,160,159,158,159,158,159,160,161,160,161,162,163,164,163,162,161,162,163,162,163,164,165,166,167,168,169,170,171,172,171,170,171,170,171,172,173,174,173,172,173,174,175,176,177,178,177,178,179,180,181,180,181,182,183,184,185,186,185,186,187,188,187,186,187,186,187,186,185,186,187,188,189,188,189,190,191,190,189,188,189,188,189,188,189,190,191,192,193,192,193,194,195,196,197,198,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,214,215,216,215,216,215,214,215,216,217,216,215,216,215,216,217,216,217,216,217,218,217,218,219,220,219,220,221,222,223,224,225,226,227,228,229,230,231,230,231,232,233,234,233,234,233,234,235,234,233,234,235,236,237,236,237,236,237,238,237,238,239,240,241,240,241,240,241,240,241,242,241,242,241,242,243,244,245,244,245,246,247,248,249,250,251,252,253,252,253,254,255,254,253,254,255,256,255,254,255,254,255,256,257,258,259,260,261,260,261,260,261,262,263,264,265,266,265,266,265,266,265,266,267,268,267,268,269,268,269,270,271,270,271,272,273,274,275,276,275,276,277,276,277,278,279,280,281,282,283,284,285,286,287,286,285,286,287,288,289,290,291,290,291,292,293,294,295,296,297,298,299,300,301,302,301,302,301,302,303,304,305,304,305,306,307,306,307,308,309,308,309,310,311,312,313,312,311,310,311,312,313,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,325,326,325,326,327,328,329,330,329,330,329,330,331,332,333,334,333,332,331,332,333,334,333,334,333,334,335,334,333,334,335,336,337,336,337,338,337,338,337,338,337,338,339,340,341,342,343,342,343,344,345,344,345,344,345,346,347,348,349,350,351,350,349,350,349,350,351,352,351,352,353,354,353,354,353,354,355,354,353,354,355,356,355,354,355,356,357,358,359,360,359,358,357,358,357,358,357,358,359,360,359,360,361,362,361,360,361,360,359,358,359,360,361,360,361,362,363,364,365,366,367,368,367,368,369,368,369,370,369,370,371,372,373,374,375,376,375,374,373,374,373,374,375,374,375,374,375,376,375,376,377,378,379,380,381,382,383,384,383,382,383,382,383,384,385,386,385,386,387,388,389,388,387,388,387,388,389,388,387,386,387,386],\"Reflected Random Walk\":[0,1,2,3,2,1,0,1,2,3,4,3,2,1,2,3,2,1,2,3,2,3,2,3,4,3,2,3,4,5,6,7,8,9,8,9,8,9,8,9,10,9,8,9,8,9,10,11,10,11,12,13,14,15,16,17,18,19,20,21,20,21,22,21,20,19,20,19,18,19,18,19,20,19,20,21,20,21,20,21,22,23,24,23,22,21,22,23,22,21,22,21,22,23,24,23,24,23,24,25,24,25,26,25,26,25,26,25,26,27,26,27,26,27,28,27,28,29,30,31,32,33,34,35,36,37,38,39,40,39,40,39,40,41,40,41,40,41,42,43,44,43,42,41,40,41,42,43,44,45,46,47,46,47,48,47,46,47,46,45,46,47,48,49,48,47,48,49,50,51,52,51,52,53,54,55,56,57,58,59,58,59,60,59,60,59,60,59,58,59,60,61,60,59,60,61,60,61,62,63,64,63,64,65,66,67,68,69,68,69,70,71,72,73,74,75,76,77,78,79,80,79,80,81,82,81,80,81,82,81,82,83,84,85,84,85,86,87,86,85,86,87,88,89,88,89,88,89,90,89,90,91,90,89,90,91,90,91,90,89,90,91,90,91,92,93,94,93,94,93,94,95,96,97,96,95,96,97,98,99,100,99,100,99,100,99,100,99,100,99,100,99,100,99,100,99,100,101,102,103,104,105,106,107,108,109,110,111,110,111,112,111,110,111,110,109,110,109,110,111,112,113,112,111,110,111,110,111,112,111,112,113,114,113,114,115,116,117,118,119,118,119,118,119,118,119,120,119,118,119,120,121,120,121,120,119,118,119,120,119,118,119,120,121,122,123,122,121,120,119,118,119,118,119,118,117,118,119,120,121,122,123,124,125,124,125,124,125,126,125,126,127,126,127,128,129,128,127,128,129,128,127,128,129,130,129,130,131,132,133,134,135,134,135,134,135,136,137,136,135,136,135,134,135,136,135,134,135,136,137,138,139,140,141,140,141,142,143,144,143,144,145,146,147,148,147,148,147,146,145,146,147,146,145,144,145,146,147,148,147,148,147,148,149,150,151,152,153,154,155,154,155,156,157,158,159,158,159,158,159,160,159,158,157,158,159,158,159,160,159,158,159,158,159,160,161,160,161,162,163,164,163,162,161,162,163,162,163,164,165,166,167,168,169,170,171,172,171,170,171,170,171,172,173,174,173,172,173,174,175,176,177,178,177,178,179,180,181,180,181,182,183,184,185,186,185,186,187,188,187,186,187,186,187,186,185,186,187,188,189,188,189,190,191,190,189,188,189,188,189,188,189,190,191,192,193,192,193,194,195,196,197,198,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,214,215,216,215,216,215,214,215,216,217,216,215,216,215,216,217,216,217,216,217,218,217,218,219,220,219,220,221,222,223,224,225,226,227,228,229,230,231,230,231,232,233,234,233,234,233,234,235,234,233,234,235,236,237,236,237,236,237,238,237,238,239,240,241,240,241,240,241,240,241,242,241,242,241,242,243,244,245,244,245,246,247,248,249,250,251,252,253,252,253,254,255,254,253,254,255,256,255,254,255,254,255,256,257,258,259,260,261,260,261,260,261,262,263,264,265,266,265,266,265,266,265,266,267,268,267,268,269,268,269,270,271,270,271,272,273,274,275,276,275,276,277,276,277,278,279,280,281,282,283,284,285,286,287,286,285,286,287,288,289,290,291,290,291,292,293,294,295,296,297,298,299,300,301,302,301,302,301,302,303,304,305,304,305,306,307,306,307,308,309,308,309,310,311,312,313,312,311,310,311,312,313,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,325,326,325,326,327,328,329,330,329,330,329,330,331,332,333,334,333,332,331,332,333,334,333,334,333,334,335,334,333,334,335,336,337,336,337,338,337,338,337,338,337,338,339,340,341,342,343,342,343,344,345,344,345,344,345,346,347,348,349,350,351,350,349,350,349,350,351,352,351,352,353,354,353,354,353,354,355,354,353,354,355,356,355,354,355,356,357,358,359,360,359,358,357,358,357,358,357,358,359,360,359,360,361,362,361,360,361,360,359,358,359,360,361,360,361,362,363,364,365,366,367,368,367,368,369,368,369,370,369,370,371,372,373,374,375,376,375,374,373,374,373,374,375,374,375,374,375,376,375,376,377,378,379,380,381,382,383,384,383,382,383,382,383,384,385,386,385,386,387,388,389,388,387,388,387,388,389,388,387,386,387,386],\"Regulator\":[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],\"index\":[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,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753,754,755,756,757,758,759,760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,881,882,883,884,885,886,887,888,889,890,891,892,893,894,895,896,897,898,899,900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,999,1000]},\"selected\":{\"id\":\"1047\",\"type\":\"Selection\"},\"selection_policy\":{\"id\":\"1046\",\"type\":\"UnionRenderers\"}},\"id\":\"1036\",\"type\":\"ColumnDataSource\"}],\"root_ids\":[\"1002\"]},\"title\":\"Bokeh Application\",\"version\":\"1.3.4\"}};\n",
       "  var render_items = [{\"docid\":\"226399c9-2ccf-4216-9090-d3190c39c315\",\"roots\":{\"1002\":\"4139b64d-5a8d-436c-9671-0e3492ebacb5\"}}];\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": [
    "plt = bplt.figure(title='Reflected Random Walk')\n",
    "plt.title.align = 'center'\n",
    "plt.title.text_font_size = '25px'\n",
    "source = ColumnDataSource(sample_path)\n",
    "glyph = Line(x=\"index\", y=\"Reflected Random Walk\", line_color=\"blue\")\n",
    "plt.add_glyph(source, glyph)\n",
    "bplt.show(plt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Regulator Process (Optional)\n",
    "\n",
    "To simulate the reflected random walk, we did not (directly) simulate the Markov chain as presented in the beginning of the section.  Rather, we simulated a (unreflected) random walk with the same $p$ and then constructed the reflected random walk via the “regulator process.”\n",
    "\n",
    "In particular:\n",
    "* Let $\\{X_n,\\, n \\geq 0\\}$ be the (unreflected) random walk.\n",
    "* Let $\\{Y_n,\\, n \\geq 0\\}$ be:\n",
    "$$ Y_n = -\\min\\{0, X_0,\\dots,X_n\\} $$\n",
    "* Then $X_n + Y_n$ is the reflected random walk."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deriving the Summation Formula (Optional)\n",
    "\n",
    "In both the Gambler's Ruin and the Reflected Random Walk, we made use of the following summation formula (for non-negative $x$):\n",
    "\n",
    "$$\\sum_{i=0}^n x^i = \\frac{1 - x^{n+1}}{1 - x} \\qquad x \\neq 1$$\n",
    "\n",
    "This is not very difficult to derive (and may be easier than memorizing it).  It suffices to show: \n",
    "\n",
    "$$(1 - x) \\sum_{i=0}^n x^i = 1 - x^{n+1}$$\n",
    "\n",
    "because we can then divide both sides by $(1 - x)$ to get the desired summation formula (this is the step that requires $x \\neq 1$).\n",
    "\n",
    "The key is to recognize a [*telescoping series*](https://en.wikipedia.org/wiki/Telescoping_series):\n",
    "\n",
    "$$\\require{cancel}\n",
    "  \\begin{aligned}\n",
    "    (1 - x) \\sum_{i=0}^n x^i &= \\sum_{i=0}^n (x^i - x^{i+1}) \\\\\n",
    "    &= (1 - x) + (x - x^2) + \\dots + (x^{n-1} - x^n) + (x^n - x^{n+1}) \\\\\n",
    "    &= 1 - x^{n+1}\n",
    "  \\end{aligned}$$\n",
    "  \n",
    "In the case of the reflected random walk, we were faced with the infinite sum, and needed to take the limit as $n \\to \\infty$.  The summation converges (is finite) only for $x < 1$:\n",
    "\n",
    "$$\\sum_{i=0}^\\infty x^i = \\lim_{n \\to \\infty} \\sum_{i=0}^n x^i = \\lim_{n \\to \\infty} \\frac{1 - x^{n+1}}{1 - x} = \\frac{1 - \\lim_{n \\to \\infty} x^{n+1}}{1 - x} = \\frac{1}{1 - x}$$"
   ]
  }
 ],
 "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
}