Created
July 25, 2020 21:42
-
-
Save jtb/73c497b7e9a65351c025e8a30bcb7869 to your computer and use it in GitHub Desktop.
AbsorbingMarkovChain.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "nbformat": 4, | |
| "nbformat_minor": 0, | |
| "metadata": { | |
| "colab": { | |
| "name": "AbsorbingMarkovChain.ipynb", | |
| "provenance": [], | |
| "collapsed_sections": [ | |
| "Q_tqLpWUX5cA" | |
| ], | |
| "include_colab_link": true | |
| }, | |
| "kernelspec": { | |
| "name": "python3", | |
| "display_name": "Python 3" | |
| } | |
| }, | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "view-in-github", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "<a href=\"https://colab.research.google.com/gist/jtb/73c497b7e9a65351c025e8a30bcb7869/absorbingmarkovchain.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "TctT5OY8W1xf", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "# Absorbing Markov Chain\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "Q_tqLpWUX5cA", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "## Preliminary Installs, Imports, and Definitions\n", | |
| "Run me first!" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "E9TGxM_YrFdn", | |
| "colab_type": "code", | |
| "cellView": "both", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 170 | |
| }, | |
| "outputId": "92039b1a-643b-496d-b4a0-5fd5977bf5b9" | |
| }, | |
| "source": [ | |
| "# Install GraphViz\n", | |
| "!apt install -y graphviz\n", | |
| "!pip install graphviz\n", | |
| "\n", | |
| "# Define some classes and methods\n", | |
| "\n", | |
| "import numpy as np\n", | |
| "from numpy.linalg import inv\n", | |
| "from graphviz import Digraph\n", | |
| "import random\n", | |
| "from collections import Iterable\n", | |
| "\n", | |
| "class Node():\n", | |
| " def __init__(self, name):\n", | |
| " self.name = name\n", | |
| " self.transition = {}\n", | |
| "\n", | |
| " def add(self, tokens, state):\n", | |
| " if isinstance(tokens, Iterable):\n", | |
| " for token in tokens:\n", | |
| " self.transition[token] = state\n", | |
| " else:\n", | |
| " self.transition[tokens] = state\n", | |
| " \n", | |
| " def step(self, x):\n", | |
| " if x in self.transition:\n", | |
| " return self.transition[x]\n", | |
| " return self\n", | |
| " \n", | |
| " def __str__( self ):\n", | |
| " return self.name\n", | |
| " \n", | |
| "def run(start, tokens):\n", | |
| " current_node = start\n", | |
| " for token in tokens:\n", | |
| " current_node = current_node.step(token)\n", | |
| " return current_node\n", | |
| "\n", | |
| "def transMatrix(transient_nodes, absorbing_nodes, tokens, normalize = True):\n", | |
| " nodes = transient_nodes + absorbing_nodes\n", | |
| " indexOf = {}\n", | |
| " for idx,item in enumerate(nodes):\n", | |
| " indexOf[item] = idx\n", | |
| "\n", | |
| " mat = np.zeros((len(nodes), len(nodes)))\n", | |
| " for fromNode in nodes:\n", | |
| " for t in tokens:\n", | |
| " toNode = fromNode.step(t)\n", | |
| " mat[indexOf[fromNode]][indexOf[toNode]] += 1\n", | |
| " \n", | |
| " if normalize:\n", | |
| " totals = mat.sum(axis=1, keepdims=True)\n", | |
| " mat = mat / totals[:]\n", | |
| " return mat[0:len(transient_nodes), 0:len(transient_nodes)]\n", | |
| "\n", | |
| "def expectedSteps(transient, absorbing, tokens):\n", | |
| " Q = transMatrix(transient, absorbing, tokens)\n", | |
| " I = np.identity(len(transient))\n", | |
| " N = inv(I - Q)\n", | |
| " ones = np.ones(len(transient))[np.newaxis].transpose()\n", | |
| " return np.matmul(N, ones)[0][0];\n", | |
| "\n", | |
| "def graph(transient_nodes, absorbing_nodes, tokens):\n", | |
| " styles = {\n", | |
| " 'absorbing': {'shape': 'doublecircle'},\n", | |
| " 'transient': {'shape': 'circle'},\n", | |
| " 'start': {'shape': 'plaintext'}\n", | |
| " }\n", | |
| "\n", | |
| " fsm = Digraph()\n", | |
| " # fsm.attr(rankdir='LR', size=\"8,5\")\n", | |
| " fsm.attr(rankdir='LR')\n", | |
| " \n", | |
| " fsm.node('dummy', '', styles['start'])\n", | |
| " for node in transient_nodes:\n", | |
| " fsm.node(node.name, node.name, styles['transient'])\n", | |
| " for node in absorbing_nodes:\n", | |
| " fsm.node(node.name, node.name, styles['absorbing'])\n", | |
| " \n", | |
| " nodes = transient_nodes + absorbing_nodes\n", | |
| " label = {}\n", | |
| " for fromNode in transient_nodes:\n", | |
| " for t in tokens:\n", | |
| " toNode = fromNode.step(t)\n", | |
| " if (fromNode, toNode) in label:\n", | |
| " label[(fromNode, toNode)] += (\", \" + str(t))\n", | |
| " else:\n", | |
| " label[(fromNode, toNode)] = str(t)\n", | |
| " \n", | |
| " if (len(transient_nodes) > 0):\n", | |
| " fsm.edge('dummy', transient_nodes[0].name)\n", | |
| " else:\n", | |
| " fsm.edge('dummy', absorbing_nodes[0].name)\n", | |
| " \n", | |
| " for k, v in label.items():\n", | |
| " fsm.edge(k[0].name, k[1].name, v)\n", | |
| " \n", | |
| " return fsm\n", | |
| "\n", | |
| "def genSeq(transient_nodes, absorbing_nodes, tokens):\n", | |
| " absorbingSet = set(absorbing_nodes)\n", | |
| " seq = \"\"\n", | |
| " if (len(transient_nodes) <= 0):\n", | |
| " return\n", | |
| " curr_node = transient_nodes[0]\n", | |
| " while(curr_node not in absorbingSet):\n", | |
| " token = random.choice(tokens)\n", | |
| " seq += str(token)\n", | |
| " curr_node = curr_node.step(token)\n", | |
| " return seq\n", | |
| " \n", | |
| "\n" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "Reading package lists... Done\n", | |
| "Building dependency tree \n", | |
| "Reading state information... Done\n", | |
| "graphviz is already the newest version (2.40.1-2).\n", | |
| "The following package was automatically installed and is no longer required:\n", | |
| " libnvidia-common-410\n", | |
| "Use 'apt autoremove' to remove it.\n", | |
| "0 upgraded, 0 newly installed, 0 to remove and 10 not upgraded.\n", | |
| "Requirement already satisfied: graphviz in /usr/local/lib/python3.6/dist-packages (0.10.1)\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "19lXNW-eYa3h", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "## HTH Sequence" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "G4cuPrqMPid-", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 193 | |
| }, | |
| "outputId": "3489f1b4-0019-4c70-a181-141aceb85878" | |
| }, | |
| "source": [ | |
| "# Flip a fair coin until Heads, Tails, Heads appears\n", | |
| "# see https://en.wikipedia.org/wiki/Absorbing_Markov_chain#String_generation\n", | |
| "\n", | |
| "# Define the Markov chain. It has four states. The first state represents the\n", | |
| "# empty string, the second state the string \"H\", the third state the string\n", | |
| "# \"HT\", and the fourth (absorbing) state the string \"HTH\".\n", | |
| "# A state is transient if it can transition to another state. It is absorbing\n", | |
| "# if it is impossible to leave this state.\n", | |
| "\n", | |
| "# Transient states. The initial state should be listed first.\n", | |
| "start = Node(\"{}\")\n", | |
| "H = Node(\"H\")\n", | |
| "HT = Node(\"HT\")\n", | |
| "transient_states = [start, H, HT]\n", | |
| "\n", | |
| "# Absorbing states\n", | |
| "HTH = Node(\"HTH\")\n", | |
| "absorbing_states = [HTH]\n", | |
| "\n", | |
| "# Define transitions. Note that transitions from a state back to itself do not\n", | |
| "# need to be explicitly mentioned. Any transition not mentioned will be assumed\n", | |
| "# to be a self transition.\n", | |
| "start.add(\"H\", H)\n", | |
| "H.add(\"T\", HT)\n", | |
| "H.add(\"H\", H)\n", | |
| "HT.add(\"H\", HTH)\n", | |
| "HT.add(\"T\", start)\n", | |
| "\n", | |
| "# Display the Markov Chain just to check that we defined things correctly.\n", | |
| "graph(transient_states, absorbing_states, [\"H\", \"T\"])\n", | |
| "\n" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x7f872831d978>" | |
| ], | |
| "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: %3 Pages: 1 -->\n<svg width=\"430pt\" height=\"129pt\"\n viewBox=\"0.00 0.00 429.89 128.55\" 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 124.5473)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-124.5473 425.887,-124.5473 425.887,4 -4,4\"/>\n<!-- dummy -->\n<g id=\"node1\" class=\"node\">\n<title>dummy</title>\n</g>\n<!-- {} -->\n<g id=\"node2\" class=\"node\">\n<title>{}</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"110.4983\" cy=\"-34.5473\" rx=\"19.4965\" ry=\"19.4965\"/>\n<text text-anchor=\"middle\" x=\"110.4983\" y=\"-30.8473\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">{}</text>\n</g>\n<!-- dummy->{} -->\n<g id=\"edge1\" class=\"edge\">\n<title>dummy->{}</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M54.3405,-34.5473C62.7938,-34.5473 72.1455,-34.5473 80.7531,-34.5473\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"80.7732,-38.0474 90.7731,-34.5473 80.7731,-31.0474 80.7732,-38.0474\"/>\n</g>\n<!-- {}->{} -->\n<g id=\"edge3\" class=\"edge\">\n<title>{}->{}</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M104.0268,-53.0691C102.927,-62.999 105.0842,-72.0456 110.4983,-72.0456 113.8821,-72.0456 115.9936,-68.5118 116.833,-63.4371\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"120.3374,-63.1144 116.9698,-53.0691 113.338,-63.022 120.3374,-63.1144\"/>\n<text text-anchor=\"middle\" x=\"110.4983\" y=\"-75.8456\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">T</text>\n</g>\n<!-- H -->\n<g id=\"node3\" class=\"node\">\n<title>H</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"194.9965\" cy=\"-69.5473\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"194.9965\" y=\"-65.8473\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">H</text>\n</g>\n<!-- {}->H -->\n<g id=\"edge2\" class=\"edge\">\n<title>{}->H</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M128.8331,-42.1418C140.5142,-46.9802 155.8318,-53.3249 168.7866,-58.6909\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"167.5552,-61.9691 178.1334,-62.5624 170.234,-55.502 167.5552,-61.9691\"/>\n<text text-anchor=\"middle\" x=\"153.4965\" y=\"-57.3473\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">H</text>\n</g>\n<!-- H->H -->\n<g id=\"edge4\" class=\"edge\">\n<title>H->H</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M187.9653,-86.2114C186.4028,-96.1723 188.7465,-105.5473 194.9965,-105.5473 199.0004,-105.5473 201.4012,-101.6998 202.1989,-96.3155\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"205.6967,-96.1506 202.0278,-86.2114 198.6977,-96.2692 205.6967,-96.1506\"/>\n<text text-anchor=\"middle\" x=\"194.9965\" y=\"-109.3473\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">H</text>\n</g>\n<!-- HT -->\n<g id=\"node4\" class=\"node\">\n<title>HT</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"282.3945\" cy=\"-34.5473\" rx=\"23.2963\" ry=\"23.2963\"/>\n<text text-anchor=\"middle\" x=\"282.3945\" y=\"-30.8473\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">HT</text>\n</g>\n<!-- H->HT -->\n<g id=\"edge5\" class=\"edge\">\n<title>H->HT</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M211.8477,-62.7989C223.024,-58.3232 238.0255,-52.3156 251.3212,-46.9911\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"252.6399,-50.2333 260.622,-43.2665 250.0375,-43.735 252.6399,-50.2333\"/>\n<text text-anchor=\"middle\" x=\"235.9965\" y=\"-57.3473\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">T</text>\n</g>\n<!-- HT->{} -->\n<g id=\"edge7\" class=\"edge\">\n<title>HT->{}</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M258.9892,-31.5949C245.5555,-30.0488 228.356,-28.32 212.9965,-27.5473 197.0167,-26.7434 192.9745,-26.7086 176.9965,-27.5473 164.8369,-28.1855 151.478,-29.4759 139.9439,-30.7769\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"139.472,-27.3082 129.9511,-31.9562 140.2925,-34.2599 139.472,-27.3082\"/>\n<text text-anchor=\"middle\" x=\"194.9965\" y=\"-31.3473\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">T</text>\n</g>\n<!-- HTH -->\n<g id=\"node5\" class=\"node\">\n<title>HTH</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387.3397\" cy=\"-34.5473\" rx=\"30.5892\" ry=\"30.5892\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387.3397\" cy=\"-34.5473\" rx=\"34.5946\" ry=\"34.5946\"/>\n<text text-anchor=\"middle\" x=\"387.3397\" y=\"-30.8473\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">HTH</text>\n</g>\n<!-- HT->HTH -->\n<g id=\"edge6\" class=\"edge\">\n<title>HT->HTH</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M305.9462,-34.5473C316.7107,-34.5473 329.8367,-34.5473 342.3782,-34.5473\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"342.7109,-38.0474 352.7109,-34.5473 342.7108,-31.0474 342.7109,-38.0474\"/>\n<text text-anchor=\"middle\" x=\"329.2924\" y=\"-38.3473\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">H</text>\n</g>\n</g>\n</svg>\n" | |
| }, | |
| "metadata": { | |
| "tags": [] | |
| }, | |
| "execution_count": 33 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "RuB_DBjXRftL", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 68 | |
| }, | |
| "outputId": "d90b4b4d-e071-4e4d-b453-de78d987a281" | |
| }, | |
| "source": [ | |
| "# Let's use the Markov Chain to do some interesting things.\n", | |
| "\n", | |
| "# Generate a random string. This should end when the string hits HTH.\n", | |
| "print(genSeq(transient_states, absorbing_states, [\"H\", \"T\"]))\n", | |
| "\n", | |
| "# Find what state you are in after a given sequence, starting at 'start' state\n", | |
| "print(run(start, [\"T\", \"T\", \"H\", \"H\", \"T\"]))\n", | |
| "\n", | |
| "# Expected number of steps to get to HTH.\n", | |
| "print(expectedSteps(transient_states, absorbing_states, [\"H\", \"T\"]))" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "HTTTHTTTHHHHHTH\n", | |
| "HT\n", | |
| "10.0\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "GQK1xRJeUhCo", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "## Rolling Dice Sequence\n", | |
| "\n", | |
| "Alice wants to join her school's Probability Student Club. Membership dues are computed via one of two simple probabilistic games.\n", | |
| "\n", | |
| "The first game: roll a dice repeatedly. Stop rolling once you get a five followed by a six. Your number of rolls is the amount you pay, in dollars.\n", | |
| "\n", | |
| "The second game: same, except that the stopping condition is a five followed by a five.\n", | |
| "\n", | |
| "Which of the two games should Alice elect to play? Does it even matter?" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "F-ikL2iVUieT", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 179 | |
| }, | |
| "outputId": "460d8225-c80d-49a0-dc12-41d47c3775f7" | |
| }, | |
| "source": [ | |
| "# Expected Value for MC that finishes with 5,6\n", | |
| "\n", | |
| "start = Node(\"start\")\n", | |
| "middle = Node(\"5\")\n", | |
| "end = Node(\"56\")\n", | |
| "\n", | |
| "start.add(5, middle)\n", | |
| "middle.add([1,2,3,4], start)\n", | |
| "middle.add(6, end)\n", | |
| "\n", | |
| "trans = [start, middle]\n", | |
| "absorbing = [end]\n", | |
| "\n", | |
| "print(\"Expected Value for 5,6: \" + str(expectedSteps(trans, absorbing, [1,2,3,4,5,6])))\n", | |
| "print(\"==========================================\")\n", | |
| "graph(trans, absorbing, [1,2,3,4,5,6])\n" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "Expected Value for 5,6: 36.000000000000036\n", | |
| "==========================================\n" | |
| ], | |
| "name": "stdout" | |
| }, | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x7f87283396a0>" | |
| ], | |
| "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: %3 Pages: 1 -->\n<svg width=\"370pt\" height=\"93pt\"\n viewBox=\"0.00 0.00 369.59 93.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 88.9954)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-88.9954 365.5917,-88.9954 365.5917,4 -4,4\"/>\n<!-- dummy -->\n<g id=\"node1\" class=\"node\">\n<title>dummy</title>\n</g>\n<!-- start -->\n<g id=\"node2\" class=\"node\">\n<title>start</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"116.9977\" cy=\"-25.9977\" rx=\"25.9954\" ry=\"25.9954\"/>\n<text text-anchor=\"middle\" x=\"116.9977\" y=\"-22.2977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">start</text>\n</g>\n<!-- dummy->start -->\n<g id=\"edge1\" class=\"edge\">\n<title>dummy->start</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M54.0023,-25.9977C62.4127,-25.9977 71.8272,-25.9977 80.7623,-25.9977\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"80.9421,-29.4978 90.9421,-25.9977 80.9421,-22.4978 80.9421,-29.4978\"/>\n</g>\n<!-- start->start -->\n<g id=\"edge2\" class=\"edge\">\n<title>start->start</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M108.8202,-50.8745C108.2562,-61.2231 110.9821,-69.9954 116.9977,-69.9954 120.8515,-69.9954 123.3551,-66.3952 124.5086,-61.0868\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"128.0163,-61.0812 125.1752,-50.8745 121.0312,-60.6252 128.0163,-61.0812\"/>\n<text text-anchor=\"middle\" x=\"116.9977\" y=\"-73.7954\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1, 2, 3, 4, 6</text>\n</g>\n<!-- 5 -->\n<g id=\"node3\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"249.9954\" cy=\"-25.9977\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"249.9954\" y=\"-22.2977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- start->5 -->\n<g id=\"edge3\" class=\"edge\">\n<title>start->5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M143.2738,-25.9977C165.8857,-25.9977 198.4365,-25.9977 221.6338,-25.9977\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"221.8748,-29.4978 231.8748,-25.9977 221.8748,-22.4978 221.8748,-29.4978\"/>\n<text text-anchor=\"middle\" x=\"187.4954\" y=\"-29.7977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 5->start -->\n<g id=\"edge4\" class=\"edge\">\n<title>5->start</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M234.8897,-15.9277C228.6886,-12.3659 221.2667,-8.7988 213.9954,-6.9977 191.1308,-1.3342 184.0633,-2.2297 160.9954,-6.9977 157.2727,-7.7671 153.4775,-8.8671 149.7541,-10.1551\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"148.2032,-7.0035 140.1652,-13.9058 150.7532,-13.5225 148.2032,-7.0035\"/>\n<text text-anchor=\"middle\" x=\"187.4954\" y=\"-10.7977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1, 2, 3, 4</text>\n</g>\n<!-- 5->5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>5->5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M242.9641,-42.6618C241.4016,-52.6227 243.7454,-61.9977 249.9954,-61.9977 253.9993,-61.9977 256.4001,-58.1502 257.1977,-52.7659\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"260.6955,-52.601 257.0266,-42.6618 253.6965,-52.7196 260.6955,-52.601\"/>\n<text text-anchor=\"middle\" x=\"249.9954\" y=\"-65.7977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 56 -->\n<g id=\"node4\" class=\"node\">\n<title>56</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"336.7935\" cy=\"-25.9977\" rx=\"20.6302\" ry=\"20.6302\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"336.7935\" cy=\"-25.9977\" rx=\"24.5979\" ry=\"24.5979\"/>\n<text text-anchor=\"middle\" x=\"336.7935\" y=\"-22.2977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">56</text>\n</g>\n<!-- 5->56 -->\n<g id=\"edge6\" class=\"edge\">\n<title>5->56</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M268.403,-25.9977C278.0805,-25.9977 290.2728,-25.9977 301.6735,-25.9977\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"301.8262,-29.4978 311.8262,-25.9977 301.8262,-22.4978 301.8262,-29.4978\"/>\n<text text-anchor=\"middle\" x=\"289.9954\" y=\"-29.7977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n</g>\n</svg>\n" | |
| }, | |
| "metadata": { | |
| "tags": [] | |
| }, | |
| "execution_count": 35 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "eZ-JA7ShWg_Y", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 179 | |
| }, | |
| "outputId": "e4ba720a-8a86-4558-bc8a-cb26ee7ad21d" | |
| }, | |
| "source": [ | |
| "# Expected Value for MC that finishes with 5,5\n", | |
| "\n", | |
| "start = Node(\"start\")\n", | |
| "middle = Node(\"5\")\n", | |
| "end = Node(\"55\")\n", | |
| "\n", | |
| "start.add(5, middle)\n", | |
| "middle.add([1,2,3,4,6], start)\n", | |
| "middle.add(5, end)\n", | |
| "\n", | |
| "trans = [start, middle]\n", | |
| "absorbing = [end]\n", | |
| "\n", | |
| "print(\"Expected Value for 5,5: \" + str(expectedSteps(trans, absorbing, [1,2,3,4,5,6])))\n", | |
| "print(\"==========================================\")\n", | |
| "graph(trans, absorbing, [1,2,3,4,5,6])" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "Expected Value for 5,5: 42.00000000000004\n", | |
| "==========================================\n" | |
| ], | |
| "name": "stdout" | |
| }, | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x7f8741444208>" | |
| ], | |
| "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: %3 Pages: 1 -->\n<svg width=\"385pt\" height=\"93pt\"\n viewBox=\"0.00 0.00 384.59 93.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 88.9954)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-88.9954 380.5917,-88.9954 380.5917,4 -4,4\"/>\n<!-- dummy -->\n<g id=\"node1\" class=\"node\">\n<title>dummy</title>\n</g>\n<!-- start -->\n<g id=\"node2\" class=\"node\">\n<title>start</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"116.9977\" cy=\"-25.9977\" rx=\"25.9954\" ry=\"25.9954\"/>\n<text text-anchor=\"middle\" x=\"116.9977\" y=\"-22.2977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">start</text>\n</g>\n<!-- dummy->start -->\n<g id=\"edge1\" class=\"edge\">\n<title>dummy->start</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M54.0023,-25.9977C62.4127,-25.9977 71.8272,-25.9977 80.7623,-25.9977\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"80.9421,-29.4978 90.9421,-25.9977 80.9421,-22.4978 80.9421,-29.4978\"/>\n</g>\n<!-- start->start -->\n<g id=\"edge2\" class=\"edge\">\n<title>start->start</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M108.8202,-50.8745C108.2562,-61.2231 110.9821,-69.9954 116.9977,-69.9954 120.8515,-69.9954 123.3551,-66.3952 124.5086,-61.0868\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"128.0163,-61.0812 125.1752,-50.8745 121.0312,-60.6252 128.0163,-61.0812\"/>\n<text text-anchor=\"middle\" x=\"116.9977\" y=\"-73.7954\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1, 2, 3, 4, 6</text>\n</g>\n<!-- 5 -->\n<g id=\"node3\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"264.9954\" cy=\"-25.9977\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"264.9954\" y=\"-22.2977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- start->5 -->\n<g id=\"edge3\" class=\"edge\">\n<title>start->5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M143.116,-25.9977C169.2264,-25.9977 209.2747,-25.9977 236.2688,-25.9977\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"236.6124,-29.4978 246.6123,-25.9977 236.6123,-22.4978 236.6124,-29.4978\"/>\n<text text-anchor=\"middle\" x=\"194.9954\" y=\"-29.7977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 5->start -->\n<g id=\"edge4\" class=\"edge\">\n<title>5->start</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M249.8897,-15.9277C243.6886,-12.3659 236.2667,-8.7988 228.9954,-6.9977 199.6597,.2687 190.592,-.8802 160.9954,-6.9977 157.2727,-7.7671 153.4775,-8.8671 149.7541,-10.1551\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"148.2032,-7.0035 140.1652,-13.9058 150.7532,-13.5225 148.2032,-7.0035\"/>\n<text text-anchor=\"middle\" x=\"194.9954\" y=\"-10.7977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1, 2, 3, 4, 6</text>\n</g>\n<!-- 55 -->\n<g id=\"node4\" class=\"node\">\n<title>55</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"351.7935\" cy=\"-25.9977\" rx=\"20.6302\" ry=\"20.6302\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"351.7935\" cy=\"-25.9977\" rx=\"24.5979\" ry=\"24.5979\"/>\n<text text-anchor=\"middle\" x=\"351.7935\" y=\"-22.2977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">55</text>\n</g>\n<!-- 5->55 -->\n<g id=\"edge5\" class=\"edge\">\n<title>5->55</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M283.403,-25.9977C293.0805,-25.9977 305.2728,-25.9977 316.6735,-25.9977\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"316.8262,-29.4978 326.8262,-25.9977 316.8262,-22.4978 316.8262,-29.4978\"/>\n<text text-anchor=\"middle\" x=\"304.9954\" y=\"-29.7977\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n</g>\n</svg>\n" | |
| }, | |
| "metadata": { | |
| "tags": [] | |
| }, | |
| "execution_count": 36 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "DN2h-7oDNuK3", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "## Cereal Box Problem\n", | |
| "\n", | |
| "Your favorite box of cereal contains 1 of 3 prizes. How many boxes do you need to buy on average to collect all 3 prizes? Each prize is equally likely to be in each box." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "er8fHn9_OPtC", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 803 | |
| }, | |
| "outputId": "1c38d8d2-9515-4b45-b459-833c0b8e8f58" | |
| }, | |
| "source": [ | |
| "# There are more efficient ways to create the graph using probabilities rather\n", | |
| "# than type of prize, but oh well.\n", | |
| "\n", | |
| "n0 = Node(\"start\")\n", | |
| "n1 = Node(\"1\")\n", | |
| "n2 = Node(\"2\")\n", | |
| "n3 = Node(\"3\")\n", | |
| "n12 = Node(\"12\")\n", | |
| "n13 = Node(\"13\")\n", | |
| "n21 = Node(\"21\")\n", | |
| "n23 = Node(\"23\")\n", | |
| "n31 = Node(\"31\")\n", | |
| "n32 = Node(\"32\")\n", | |
| "done = Node(\"done\")\n", | |
| "\n", | |
| "# The three prizes.\n", | |
| "tokens = [1, 2, 3]\n", | |
| "\n", | |
| "n0.add(1, n1)\n", | |
| "n0.add(2, n2)\n", | |
| "n0.add(3, n3)\n", | |
| "\n", | |
| "n1.add(2, n12)\n", | |
| "n1.add(3, n13)\n", | |
| "n2.add(1, n21)\n", | |
| "n2.add(3, n23)\n", | |
| "n3.add(1, n31)\n", | |
| "n3.add(2, n32)\n", | |
| "\n", | |
| "n12.add(3, done)\n", | |
| "n13.add(2, done)\n", | |
| "n21.add(3, done)\n", | |
| "n23.add(1, done)\n", | |
| "n31.add(2, done)\n", | |
| "n32.add(1, done)\n", | |
| "\n", | |
| "trans = [n0, n1, n2, n3, n12, n13, n21, n23, n31, n32]\n", | |
| "absorbing = [done]\n", | |
| "\n", | |
| "print(\"Expected Value for 3 prizes: \" + str(expectedSteps(trans, absorbing, tokens)))\n", | |
| "print(\"Example sequence: \" + genSeq(trans, absorbing, tokens))\n", | |
| "print(\"==========================================\")\n", | |
| "graph(trans, absorbing, tokens)\n" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "Expected Value for 3 prizes: 5.499999999999999\n", | |
| "Example sequence: 3113332\n", | |
| "==========================================\n" | |
| ], | |
| "name": "stdout" | |
| }, | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "<graphviz.dot.Digraph at 0x7fe7e8911f60>" | |
| ], | |
| "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: %3 Pages: 1 -->\n<svg width=\"427pt\" height=\"548pt\"\n viewBox=\"0.00 0.00 427.09 547.60\" 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 543.5963)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-543.5963 423.0865,-543.5963 423.0865,4 -4,4\"/>\n<!-- dummy -->\n<g id=\"node1\" class=\"node\">\n<title>dummy</title>\n</g>\n<!-- start -->\n<g id=\"node2\" class=\"node\">\n<title>start</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"116.9977\" cy=\"-249.7982\" rx=\"25.9954\" ry=\"25.9954\"/>\n<text text-anchor=\"middle\" x=\"116.9977\" y=\"-246.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">start</text>\n</g>\n<!-- dummy->start -->\n<g id=\"edge1\" class=\"edge\">\n<title>dummy->start</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M54.0023,-249.7982C62.4127,-249.7982 71.8272,-249.7982 80.7623,-249.7982\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"80.9421,-253.2983 90.9421,-249.7982 80.9421,-246.2983 80.9421,-253.2983\"/>\n</g>\n<!-- 1 -->\n<g id=\"node3\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"204.9954\" cy=\"-392.7982\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"204.9954\" y=\"-389.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- start->1 -->\n<g id=\"edge2\" class=\"edge\">\n<title>start->1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M130.7473,-272.1419C146.8327,-298.2814 173.3726,-341.4098 189.9829,-368.4021\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"187.1888,-370.5401 195.4106,-377.2224 193.1505,-366.8714 187.1888,-370.5401\"/>\n<text text-anchor=\"middle\" x=\"164.9954\" y=\"-337.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node4\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"204.9954\" cy=\"-249.7982\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"204.9954\" y=\"-246.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- start->2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>start->2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M143.3999,-249.7982C153.9553,-249.7982 166.1284,-249.7982 176.8513,-249.7982\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"176.9771,-253.2983 186.9771,-249.7982 176.977,-246.2983 176.9771,-253.2983\"/>\n<text text-anchor=\"middle\" x=\"164.9954\" y=\"-253.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node5\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"204.9954\" cy=\"-113.7982\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"204.9954\" y=\"-110.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- start->3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>start->3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M131.136,-227.9474C147.0594,-203.338 172.8622,-163.4598 189.3711,-137.9454\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"192.5034,-139.5473 194.9973,-129.2502 186.6263,-135.7446 192.5034,-139.5473\"/>\n<text text-anchor=\"middle\" x=\"164.9954\" y=\"-185.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 1->1 -->\n<g id=\"edge5\" class=\"edge\">\n<title>1->1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M197.9641,-409.4622C196.4016,-419.4232 198.7454,-428.7982 204.9954,-428.7982 208.9993,-428.7982 211.4001,-424.9507 212.1977,-419.5664\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"215.6955,-419.4015 212.0266,-409.4622 208.6965,-419.5201 215.6955,-419.4015\"/>\n<text text-anchor=\"middle\" x=\"204.9954\" y=\"-432.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 12 -->\n<g id=\"node6\" class=\"node\">\n<title>12</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"287.7935\" cy=\"-485.7982\" rx=\"20.5982\" ry=\"20.5982\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-482.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">12</text>\n</g>\n<!-- 1->12 -->\n<g id=\"edge6\" class=\"edge\">\n<title>1->12</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M217.2125,-406.5206C230.3197,-421.2428 251.3672,-444.8836 267.0726,-462.5241\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"264.6013,-465.0119 273.865,-470.1534 269.8295,-460.3572 264.6013,-465.0119\"/>\n<text text-anchor=\"middle\" x=\"244.9954\" y=\"-445.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 13 -->\n<g id=\"node7\" class=\"node\">\n<title>13</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"287.7935\" cy=\"-392.7982\" rx=\"20.5982\" ry=\"20.5982\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-389.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">13</text>\n</g>\n<!-- 1->13 -->\n<g id=\"edge7\" class=\"edge\">\n<title>1->13</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M223.371,-392.7982C233.1191,-392.7982 245.3644,-392.7982 256.5542,-392.7982\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"256.8433,-396.2983 266.8432,-392.7982 256.8432,-389.2983 256.8433,-396.2983\"/>\n<text text-anchor=\"middle\" x=\"244.9954\" y=\"-396.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 2->2 -->\n<g id=\"edge9\" class=\"edge\">\n<title>2->2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M197.9641,-266.4622C196.4016,-276.4232 198.7454,-285.7982 204.9954,-285.7982 208.9993,-285.7982 211.4001,-281.9507 212.1977,-276.5664\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"215.6955,-276.4015 212.0266,-266.4622 208.6965,-276.5201 215.6955,-276.4015\"/>\n<text text-anchor=\"middle\" x=\"204.9954\" y=\"-289.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 21 -->\n<g id=\"node8\" class=\"node\">\n<title>21</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"287.7935\" cy=\"-299.7982\" rx=\"20.5982\" ry=\"20.5982\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-296.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">21</text>\n</g>\n<!-- 2->21 -->\n<g id=\"edge8\" class=\"edge\">\n<title>2->21</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M220.5691,-259.2028C231.9114,-266.0522 247.5599,-275.5019 260.9052,-283.5609\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"259.3255,-286.6956 269.6951,-288.8689 262.9441,-280.7034 259.3255,-286.6956\"/>\n<text text-anchor=\"middle\" x=\"244.9954\" y=\"-279.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 23 -->\n<g id=\"node9\" class=\"node\">\n<title>23</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"287.7935\" cy=\"-206.7982\" rx=\"20.5982\" ry=\"20.5982\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-203.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">23</text>\n</g>\n<!-- 2->23 -->\n<g id=\"edge10\" class=\"edge\">\n<title>2->23</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M221.3536,-241.3027C232.4274,-235.5517 247.3301,-227.8122 260.2151,-221.1206\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"261.8957,-224.1917 269.1572,-216.4767 258.6695,-217.9795 261.8957,-224.1917\"/>\n<text text-anchor=\"middle\" x=\"244.9954\" y=\"-234.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 3->3 -->\n<g id=\"edge13\" class=\"edge\">\n<title>3->3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M197.9641,-130.4622C196.4016,-140.4232 198.7454,-149.7982 204.9954,-149.7982 208.9993,-149.7982 211.4001,-145.9507 212.1977,-140.5664\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"215.6955,-140.4015 212.0266,-130.4622 208.6965,-140.5201 215.6955,-140.4015\"/>\n<text text-anchor=\"middle\" x=\"204.9954\" y=\"-153.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 31 -->\n<g id=\"node10\" class=\"node\">\n<title>31</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"287.7935\" cy=\"-113.7982\" rx=\"20.5982\" ry=\"20.5982\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-110.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">31</text>\n</g>\n<!-- 3->31 -->\n<g id=\"edge11\" class=\"edge\">\n<title>3->31</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M223.371,-113.7982C233.1191,-113.7982 245.3644,-113.7982 256.5542,-113.7982\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"256.8433,-117.2983 266.8432,-113.7982 256.8432,-110.2983 256.8433,-117.2983\"/>\n<text text-anchor=\"middle\" x=\"244.9954\" y=\"-117.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 32 -->\n<g id=\"node11\" class=\"node\">\n<title>32</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"287.7935\" cy=\"-20.7982\" rx=\"20.5982\" ry=\"20.5982\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-17.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">32</text>\n</g>\n<!-- 3->32 -->\n<g id=\"edge12\" class=\"edge\">\n<title>3->32</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M217.2125,-100.0757C230.3197,-85.3536 251.3672,-61.7127 267.0726,-44.0722\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"269.8295,-46.2391 273.865,-36.4429 264.6013,-41.5844 269.8295,-46.2391\"/>\n<text text-anchor=\"middle\" x=\"244.9954\" y=\"-77.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 12->12 -->\n<g id=\"edge14\" class=\"edge\">\n<title>12->12</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M280.1954,-505.3618C279.0265,-515.4777 281.5592,-524.5963 287.7935,-524.5963 291.7874,-524.5963 294.2622,-520.854 295.2177,-515.5047\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"298.7196,-515.4204 295.3917,-505.3618 291.7206,-515.3003 298.7196,-515.4204\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-528.3963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1, 2</text>\n</g>\n<!-- done -->\n<g id=\"node12\" class=\"node\">\n<title>done</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"385.8391\" cy=\"-239.7982\" rx=\"29.4667\" ry=\"29.4667\"/>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"385.8391\" cy=\"-239.7982\" rx=\"33.4967\" ry=\"33.4967\"/>\n<text text-anchor=\"middle\" x=\"385.8391\" y=\"-236.0982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">done</text>\n</g>\n<!-- 12->done -->\n<g id=\"edge15\" class=\"edge\">\n<title>12->done</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M300.4811,-469.15C303.3735,-464.9279 306.2738,-460.3073 308.5917,-455.7982 338.2994,-398.0067 361.5176,-326.1404 374.4508,-281.6157\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"377.8159,-282.5779 377.2071,-272.0006 371.0869,-280.6489 377.8159,-282.5779\"/>\n<text text-anchor=\"middle\" x=\"330.5917\" y=\"-419.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 13->13 -->\n<g id=\"edge16\" class=\"edge\">\n<title>13->13</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M280.1954,-412.3618C279.0265,-422.4777 281.5592,-431.5963 287.7935,-431.5963 291.7874,-431.5963 294.2622,-427.854 295.2177,-422.5047\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"298.7196,-422.4204 295.3917,-412.3618 291.7206,-422.3003 298.7196,-422.4204\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-435.3963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1, 3</text>\n</g>\n<!-- 13->done -->\n<g id=\"edge17\" class=\"edge\">\n<title>13->done</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M299.8071,-375.7559C302.7199,-371.5457 305.7984,-367.0293 308.5917,-362.7982 327.3987,-334.3097 347.9164,-301.5556 363.0764,-277.0137\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"366.1386,-278.716 368.4062,-268.3666 360.1796,-275.043 366.1386,-278.716\"/>\n<text text-anchor=\"middle\" x=\"330.5917\" y=\"-335.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 21->21 -->\n<g id=\"edge18\" class=\"edge\">\n<title>21->21</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M280.1954,-319.3618C279.0265,-329.4777 281.5592,-338.5963 287.7935,-338.5963 291.7874,-338.5963 294.2622,-334.854 295.2177,-329.5047\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"298.7196,-329.4204 295.3917,-319.3618 291.7206,-329.3003 298.7196,-329.4204\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-342.3963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1, 2</text>\n</g>\n<!-- 21->done -->\n<g id=\"edge19\" class=\"edge\">\n<title>21->done</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M305.7766,-288.7932C317.6797,-281.509 333.7304,-271.6866 348.3352,-262.749\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"350.4893,-265.5343 357.192,-257.3291 346.8354,-259.5635 350.4893,-265.5343\"/>\n<text text-anchor=\"middle\" x=\"330.5917\" y=\"-278.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 23->23 -->\n<g id=\"edge21\" class=\"edge\">\n<title>23->23</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M280.1954,-226.3618C279.0265,-236.4777 281.5592,-245.5963 287.7935,-245.5963 291.7874,-245.5963 294.2622,-241.854 295.2177,-236.5047\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"298.7196,-236.4204 295.3917,-226.3618 291.7206,-236.3003 298.7196,-236.4204\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-249.3963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2, 3</text>\n</g>\n<!-- 23->done -->\n<g id=\"edge20\" class=\"edge\">\n<title>23->done</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M307.6345,-213.4762C318.2468,-217.0481 331.7277,-221.5854 344.4959,-225.8829\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"343.4675,-229.2297 354.0615,-229.1025 345.7005,-222.5954 343.4675,-229.2297\"/>\n<text text-anchor=\"middle\" x=\"330.5917\" y=\"-225.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 31->31 -->\n<g id=\"edge22\" class=\"edge\">\n<title>31->31</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M280.1954,-133.3618C279.0265,-143.4777 281.5592,-152.5963 287.7935,-152.5963 291.7874,-152.5963 294.2622,-148.854 295.2177,-143.5047\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"298.7196,-143.4204 295.3917,-133.3618 291.7206,-143.3003 298.7196,-143.4204\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-156.3963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1, 3</text>\n</g>\n<!-- 31->done -->\n<g id=\"edge23\" class=\"edge\">\n<title>31->done</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M300.6113,-130.2705C315.348,-149.2089 339.947,-180.8215 358.9398,-205.2294\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"356.24,-207.4592 365.1435,-213.2019 361.7646,-203.1603 356.24,-207.4592\"/>\n<text text-anchor=\"middle\" x=\"330.5917\" y=\"-176.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 32->32 -->\n<g id=\"edge25\" class=\"edge\">\n<title>32->32</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M280.1954,-40.3618C279.0265,-50.4777 281.5592,-59.5963 287.7935,-59.5963 291.7874,-59.5963 294.2622,-55.854 295.2177,-50.5047\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"298.7196,-50.4204 295.3917,-40.3618 291.7206,-50.3003 298.7196,-50.4204\"/>\n<text text-anchor=\"middle\" x=\"287.7935\" y=\"-63.3963\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2, 3</text>\n</g>\n<!-- 32->done -->\n<g id=\"edge24\" class=\"edge\">\n<title>32->done</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M296.3229,-39.8499C312.2321,-75.3855 346.7382,-152.4601 367.9584,-199.8589\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"364.8639,-201.5125 372.1446,-209.2094 371.2529,-198.6522 364.8639,-201.5125\"/>\n<text text-anchor=\"middle\" x=\"330.5917\" y=\"-127.5982\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n</g>\n</svg>\n" | |
| }, | |
| "metadata": { | |
| "tags": [] | |
| }, | |
| "execution_count": 5 | |
| } | |
| ] | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment