Jeff Hussmann 01-22-14 gnomes and trolls.ipynb

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`numpy` has useful functions for generating random numbers and maninulating arrays.\n",
      "`matplotlib` has useful functions for plotting things."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np\n",
      "import matplotlib.pyplot as plt"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We will explicitly model the process of picking a bridge and then picking a creature, rejecting any trial in which a gnome is picked.\n",
      "\n",
      "`numpy.random.choice` is a convenient way to pick from a set of objects with specified weights (i.e draw from a [categorical distribution](http://en.wikipedia.org/wiki/Categorical_distribution)). "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "bridges = ['TGGGG', 'TTGGG', 'GGGGG']\n",
      "ps = [0.2, 0.2, 0.6]\n",
      "trials = []\n",
      "\n",
      "while len(trials) < 100000:\n",
      "    bridge = np.random.choice(bridges, p=ps)\n",
      "    creature = np.random.choice(list(bridge))\n",
      "    if creature == 'T':\n",
      "        if bridge.count('T') == 1:\n",
      "            trials.append(1)\n",
      "        else:\n",
      "            trials.append(0)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`trials` is now a list of 0's and 1's that we need to convert into a list of \"fraction of safe passages so far\"."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "cumulative_fractions = np.cumsum(trials) / (np.arange(len(trials)) + 1.)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "plt.semilogx(cumulative_fractions)\n",
      "plt.ylim(0, 1)\n",
      "plt.axhline(1. / 3, color='red', linestyle='--')\n",
      "plt.xlabel('Number of trials')\n",
      "plt.ylabel('Cumulative fraction of safe passages');"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAEUCAYAAAAx56EeAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XlYVdX+P/D3YXAicMgZUBRQRAQV0ExNFBWHxMxUvH1z\nnlOzX6U23NCmq2a3NMwwycyr5JyailOg19kQRxwRCylNQsRQEA7r98e6HEAOnHGfw/B+PQ9P7H32\nXvvDkvaHtdbea6mEEAJERERPsLF2AEREVD4xQRARkVZMEEREpBUTBBERacUEQUREWjFBEBGRVoom\niHHjxqFRo0Zo165dqcfMnDkTnp6e8PPzQ0JCgpLhEBGRARRNEGPHjkVMTEypn+/atQvXr1/HtWvX\nsGLFCkydOlXJcIiIyACKJoju3bujbt26pX6+fft2jB49GgDQuXNnZGRk4M6dO0qGREREerLqGERq\naipcXV012y4uLrh165YVIyIiogJWH6R+cqYPlUplpUiIiKgoO2te3NnZGSkpKZrtW7duwdnZucRx\nHh4eSEpKsmRoREQVnru7O65fv270+VZtQYSGhuL7778HABw/fhx16tRBo0aNShyXlJQEIYTZvsLD\nw816fFmfa/tM174nPy/rs8pWF4Zssy5YF6yLsrdN/cNa0RbEyJEjcfDgQaSlpcHV1RXz589Hbm4u\nAGDy5MkYMGAAdu3aBQ8PDzg4OGDVqlVKhqMRFBRk1uPL+lzbZ7r2Pfm5ofEaorzVhaHb5sS6ML5s\n1oX+x1eouhAVQAUJ0yLCw8OtHUK5wbooxLooxLooZOq90+qD1GQYJf9SqmhYF4VYF4VYF+aj+l+W\nKddUKhUqQJhEROWKqfdOtiCIiEgrJggiItKKCYKIiLRigiAiIq2YIIiISCsmCCIi0ooJgoiItGKC\nICIirZggiIhIKyYIIiLSigmCiIi0YoIgIiKtmCCIiEgrJggiItJKZ4J46623kJmZidzcXAQHB6N+\n/fpYs2aNJWIjIiIr0pkg9u7dCycnJ/z0009wc3NDUlISPv30U0vERkREVqQzQeTl5QEAfvrpJ7z0\n0kuoXbs2VCqV4oEREZF12ek6YNCgQfDy8kKNGjWwfPly/Pnnn6hRo4YlYiMiIivSa8nR9PR01K5d\nG7a2tsjKysKDBw/QuHFjS8QHgEuOEhEZQ/ElR7OysrBs2TJMmTIFAPD777/jl19+MfqCRERUMehM\nEGPHjkW1atVw9OhRAEDTpk3x7rvvKh4YERFZl84EkZSUhDlz5qBatWoAAAcHB8WDIiIi69OZIKpX\nr45Hjx5ptpOSklC9enVFgyIiIuvT+RTTvHnz0K9fP9y6dQv/+Mc/cOTIEXz33XcWCI2IiKxJr6eY\n0tLScPz4cQDAM888g/r16yseWFF8iomIyHCm3jt1Joj4+HjNi3FCCKhUKtSuXRvNmzeHnZ3OBohZ\nMEEQERlO8QTxzDPPID4+Hr6+vgCA8+fPo23btrh//z6WL1+OkJAQoy+ud5BMEEREBlP8PYimTZvi\nzJkziI+PR3x8PM6cOYOWLVti3759mD17ttEXJiKi8k1ngrhy5Qratm2r2fb29sbly5fh7u7OOZmI\niCoxnYMIbdu2xdSpUxEWFgYhBDZs2ABvb2/k5OTA3t7eEjESEZEV6ByDePjwIb766iscOXIEANC1\na1dMmzYNNWrUQFZWFhwdHZUPkmMQREQGU3yQujxggiAiMpyp906dXUxXr17FO++8g8TERM0b1SqV\nCjdu3DD6okREVP7pNVnflClTYGdnh9jYWIwePRovv/yyJWIjIiIr0pkgHj16hN69e0MIATc3N8yb\nNw87d+7Uq/CYmBh4eXnB09MTCxcuLPF5Wloa+vXrh/bt28PHx4dTeBARlSM6E0SNGjWgVqvh4eGB\niIgIbNmyBVlZWToLVqvVmD59OmJiYpCYmIjo6GhcunSp2DERERHo0KEDzpw5g7i4OLzxxhuaJU6J\niMi6dCaIL774Ag8fPsTSpUvxyy+/4D//+Q9Wr16ts+CTJ0/Cw8MDbm5usLe3R1hYGLZt21bsmCZN\nmiAzMxMAkJmZiaefftpi03cQEVHZdN6NO3XqBABwdHREVFQU/v77b9SuXVtnwampqXB1ddVsu7i4\n4MSJE8WOmThxInr16oWmTZviwYMH2LBhg6HxExGRQnQmiJEjRyIyMhK2trYIDAzE/fv38dprr+mc\nZkOft6w/+eQTtG/fHnFxcUhKSkKfPn1w9uxZre9WzJs3T/N9UFAQgoKCdJZPRFSVxMXFIS4uzmzl\n6UwQiYmJcHJywtq1a9G/f38sWLAAHTt21JkgnJ2dkZKSotlOSUmBi4tLsWOOHj2qWb7U3d0dLVq0\nwJUrVxAQEFCivKIJgoiISnryj+f58+ebVJ7OMYi8vDzk5ubixx9/xKBBg2Bvb69X6yAgIADXrl3D\nzZs38fjxY6xfvx6hoaHFjvHy8sL+/fsBAHfu3MGVK1fQsmVLI38UIiIyJ50tiMmTJ8PNzQ2+vr54\n7rnncPPmTb3GIOzs7BAREYGQkBCo1WqMHz8ebdq0QWRkpKbcd955B2PHjoWfnx/y8/OxaNEi1KtX\nz/SfioiITGbwVBtCCKjVaos+bcSpNoiIDKf4ehBLlixBZmYmhBAYP348OnbsiAMHDhh9QSIiqhh0\nJoioqCg4OTlh7969SE9Px5o1azB37lxLxEZERFakM0EUNE927tyJV155BT4+PooHRURE1qczQfj7\n+6Nv377YtWsXQkJCkJmZCRsbnacREVEFp3OQWq1W48yZM3B3d0edOnXw119/ITU1Fb6+vpaKkYPU\nRERGUHw9CFtbW7Ro0QJXr15Fdna20RciIqKKRWeC+Oabb7B06VKkpKSgQ4cOOH78OLp06YKff/7Z\nEvFZ3cSJQEgI8NJL1o6EiMiy9HrM9eTJk3Bzc0NsbCwSEhL0elGuMtixA1i1CtiyxdqREBFZnl7r\nQdSsWRMAkJ2dDS8vL1y5ckXxwKztwQPg1VeBr78G4uIADoEQUVWjM0G4urri3r17eOGFF9CnTx+E\nhobCzc3NAqFZ13vvAcHBwPjxgJ0dcO2atSMiIrIsg6baiIuLQ2ZmJvr164dq1aopGVcxln6K6eRJ\nYPBg4MIF4OmngVGjgG7dgEmTLBYCEZHJFJ9qAwDi4+OxZMkSnDt3Di4uLhZNDpaWmysHpj/7TCYH\nAAgKkt1MRERVic4E8cEHH2DMmDFIT09HWloaxo4diw8//NASsVnFZ58BTZoAI0cW7itIEByHIKKq\nRGcXU6tWrXDu3DnUqFEDAPDo0SP4+fnh6tWrFgkQsFwX0/XrwDPPAKdOAS1aFO4XAmjeHNi/H2jV\nSvEwiIjMQvEuJmdnZzx69EiznZ2dXWJluMpACGDKFODtt4snBwBQqdjNRERVj84E4eTkhLZt22LM\nmDEYM2YMfHx8ULt2bcyYMQMzZ860RIwW8f33wL17wGuvaf+cCYKIqhqdXUzfffdd4cH/a64U/e/o\n0aOVjlHxLqa7dwEfH2D3bqBjR+3H3Lghn2RKTZUtCiKi8s7Ue6fBK8pZg9IJ4pVXgEaNgMWLSz+G\n4xBEVNEoPllfZbd3L3D4sHznoSxFxyGYIIioKqjSCztkZcmB6eXLAQcH3cdzHIKIqhK9u5gePnyI\nWrVqKR2PVkp1Mc2eLccU1q7V73iOQxBRRaL4Y65Hjx6Ft7c3WrduDQA4c+YMpk2bZvQFy4uEBGD1\nauDzz/U/p0ULzstERFWHzgQxa9YsxMTEoH79+gCA9u3b4+DBg4oHpiS1Wk6nsWAB0LCh/ufxfQgi\nqkr0GoNo1qxZsW07u4o9tr10KeDkBIwZY/i5TBBEVFXoTBDNmjXDkSNHAACPHz/G4sWL0aZNG8UD\nU8qvvwIffwxERho3jhAUBBw8yHmZiKjy05kgli9fjmXLliE1NRXOzs5ISEjAsmXLLBGbIubOBWbM\nADw9jTu/RQvA1lbO20REVJmV2lc0Z84cLFy4ELGxsVi3bp0lY1LML7/Iv/5XrjS+jKLjEMYmGSKi\niqDUFsTOnTshhMC//vUvS8ajGCGAOXOA8HD93nkoC8chiKgqKLUF0b9/f9StWxd///03HB0di32m\nUqmQmZmpeHDmtHevfH9h/HjTywoKAv75T5l0+D4EEVVWOl+UCw0Nxfbt2y0Vj1amvuyRny8n4QsP\nB4YMMT0eIYBmzYCff2Y3ExGVX4q/KGft5GAOa9cCtWoBL7xgnvL4PgQRVQU6E8SxY8cQGBgIBwcH\n2Nvbw8bGBk5OTpaIzSyys2V30KJF5u0OYoIgospOZ4KYPn061q1bh1atWiE7OxtRUVEVaqqNr74C\n/PzkHErmxHWqiaiy0+tNak9PT6jVatja2mLs2LGIiYlROi6zyMiQ02ko8SBWy5aAjQ3fhyCiykvn\nnBkODg7IycmBn58fZs+ejcaNGyu6eI85LVgAhIYC3t7mL5vvQxBRZaezBfH9998jPz8fERERqFWr\nFm7duoXNmzfrVXhMTAy8vLzg6emJhQsXaj0mLi4OHTp0gI+PD4KCggwKviwpKcA33wDz55utyBI4\nDkFElZlBS46mp6cjJSUFfn5+Oo9Vq9Vo3bo19u/fD2dnZwQGBiI6OrrYPE4ZGRno2rUr9uzZAxcX\nF6SlpWlmjS0WpBGPao0fL5cR/eQTg04zSFIS8NxzwK1bfB+CiMofxR9z7dGjBzIzM5Geng5/f39M\nnDgRr7/+us6CT548CQ8PD7i5ucHe3h5hYWHYtm1bsWPWrVuHoUOHwsXFBQC0JgdjXLwI/PSTXBBI\nSRyHIKLKTGeCuH//PpycnLBlyxaMGjUKJ0+exP79+3UWnJqaCldXV822i4sLUlNTix1z7do1pKen\no2fPnggICMCaNWuM+BFKmjtXftWpY5biSsX3IYioMtOZINRqNf744w9s2LABAwcOBCCbLbroc0xu\nbi5Onz6NXbt2Yc+ePfjwww9xzcTl2g4dAi5cACz1JG5QEBAba5lrERFZks6nmN5//32EhISga9eu\n6NSpE5KSkuCpx2M7zs7OSElJ0WynpKRoupIKuLq6on79+qhZsyZq1qyJ5557DmfPntVa/rx58zTf\nBwUFaR3QFkJ2K334IVC9us4QzSI4GHj7bTmdh41eDw0TESkjLi4Ocebs0hAKyc3NFS1bthTJycki\nJydH+Pn5icTExGLHXLp0SQQHB4u8vDyRlZUlfHx8xMWLF0uUpW+YmzYJ0b69EGq1WX4EvXl7C3Hi\nhGWvSUSki6m3eMXWDrWzs0NERARCQkKgVqsxfvx4tGnTBpGRkQCAyZMnw8vLC/369YOvry9sbGww\nceJEeBv50kJurvxLPiLC8n/JDxgA7NoFdOpk2esSESnJoMdcrUWfR7W+/hrYtAnYt8/yj5zGxQFv\nvQWcOmXZ6xIRlUWxx1yXLFkCADh8+LDRhVvK338DH3wALFxonfcRunaVj7reuWP5axMRKaXUBPHt\nt98CAGbMmGGxYIz173/Lp4n8/a1zfXt7oHdvYPdu61yfiEgJpY5BeHt7w9PTE6mpqWjXrl2xz1Qq\nFc6dO6d4cPr4809gyRLrd+8UjEOMGWPdOIiIzKXMMYjbt2+jb9++2LFjR4l+LDc3N6Vj0yirH23G\nDDko/b8eMau5fRto00YmLHt768ZCRASYPgah1yD148ePcfXqVQBA69atYW/hO2BpP+T168AzzwCX\nLgENGlg0JK0CAoDPPgN69LB2JEREFpiLKS4uDp6enpg2bRqmTZsGT09PHDx40OgLmtO77wKvv14+\nkgMADBwou5mIiCoDnS2Ijh07Ijo6Gq1btwYAXL16FWFhYTh9+rRFAgS0Z8FTp+Qa01evAg4OFgul\nTCdOyFlkL1ywdiRERBZoQeTl5WmSAwC0atUKeXl5Rl/QHAqm1AgPLz/JAZBdTH/+Cfz6q7UjISIy\nnc4E4e/vjwkTJiAuLg6xsbGYMGECAgICLBFbqWJi5KDwuHFWDaMEW1ugXz92MxFR5aCziyk7OxvL\nli3DkSNHAADdu3fHtGnTUN1Ss+GheDNJrQY6dJAvxr3wgsVC0NsPPwBr1wI7dlg7EiKq6izyFJO1\nFf0hv/8eiIwEDh8un6u43bsHNG8uu5pq1LB2NERUlSk+BlGeZGcD//wnsGhR+UwOAFC3LuDnx0WE\niKjiq1AJIiJCdi917WrtSMrGx12JqDKoMF1M6ekCrVoBBw8CRs4IbjHnzgFDhsgX+cprS4eIKj9T\nu5h0rgdx5coVLF68GDdv3tQ83qpSqfDzzz8bfVFjLFggB6XLe3IAgHbtgMeP5TsaRZ4QJiKqUHS2\nIHx9fTF16lR07NgRtra28iSVCv4WnDpVpVKhXj2B8+eBpk0tdlmTTJ4sk8P/+3/WjoSIqirFWxD2\n9vaYOnWq0RcwlylTKk5yAOTsrl9+yQRBRBWXzhbEvHnz0KBBA7z44ovF3n2oV6+e4sEVUKlUyMgQ\nqF3bYpc02d9/A02aAL//Djg6WjsaIqqKFH8Pws3NDaonRlpVKhVu3Lhh9EUNZeoPaS39+sm5mYYN\ns3YkRFQVVbkX5SqSb74B9u8H1q+3diREVBUpniAeP36M5cuX49ChQ1CpVOjRowemTJli0TUhKmqC\nSEsD3N2BP/4AatWydjREVNUoniDGjx+PvLw8jB49GkIIrFmzBnZ2dli5cqXRFzVURU0QANCnj3yi\n6aWXrB0JEVU1iicIX1/fEutPa9unpIqcIFasAA4cYDcTEVme4nMx2dnZ4fr165rtpKQk2NnpfDqW\n/mfIEDk9+cOH1o6EiMgwOu/0n376KXr16oUWLVoAAG7evIlVq1YpHlhl0aAB0KkTsHs3MHSotaMh\nItKfXk8xZWdn48qVK1CpVGjdurVF14IAKnYXEyC7mX7+Wa4VQURkKYqNQRw4cADBwcHYvHlzsYsU\nvBPx4osvGn1Rg4Os4Ani7l3Aw0OZp5lSU4Hjx9k6IaKSFJtq49ChQwgODsaOHTtKvCgHWDZBVHQN\nGgCBgcp0M/3wA/Dpp3Iiw/9NlUVEZBY6u5hu3LiBli1b6tynpIreggDkKnixsebvZnr+eTkIfvBg\n+V8ng4gsS/HHXDt27IjTp08X2+fv74/4+HijL2qoypAg/vwTaNVKdjPVrGmeMvPygPr1gX/8Q3Zd\nLV5snnKJqHJQrIvp0qVLSExMREZGBrZs2QIhBFQqFTIzM5GdnW30Bauqhg0Bf3/ZzWSu3rmEBMDV\nFZg0SXZdffopFygiIvMpNUFcvXoVO3bswP3797Fjxw7NfkdHR3zzzTcWCa6yGTYM2LjRfAkiNhYI\nCpJrYOfnA+fPA76+5inbGHfuAMeOyfGQoo4cAc6eBaZNs05cRGQcnV1Mx44dQ5cuXSwVj1aVoYsJ\nkN1Mnp7A7dvm6Wbq3x+YOFEmnNdfB+rUAcLDTS/XEELI5GRrCyxbBnzwgZzivOiA+cyZwNatwG+/\nsYVDZEmKv0m9fPlyZGRkaLbv3buHcePGGX3BqqxoN5OpcnPlX+Y9esjtIUPkTdjS1q8vnGfqyBGZ\nBI8fL37MkSNy4sJffrF8fERkPJ0J4ty5c6hTp45mu27duiUGrUl/I0YA0dGmlxMfD7RoATz9tNzu\n2lUOgBeZFcUiYmOBXbuAzEzg8GFg5MjCRHX/PrBqFXD5slwR0BoJjIiMpzNBCCGQnp6u2U5PT4da\nrVY0qMps+HBg716gSJUaJTYW6NmzcNvWVg5Ub9hgWrmGOnoUaNRIvi2enQ289ZZMBOvXA6NHA+PG\nAR06AGFhTBBEFY3OBPHGG2+gS5cu+Oc//4n33nsPXbp0wVtvvaVX4TExMfDy8oKnpycWLlxY6nGn\nTp2CnZ0dtmzZon/kFVTdunLswNT3IeLiiicIQLZOLJkgMjKA5GRg7lzg44+Bbt2A9u0BtRp4911g\n2zZ5XLdu8kXBzEzZmiCiikFnghg1ahS2bNmChg0bonHjxti6dStGjRqls2C1Wo3p06cjJiYGiYmJ\niI6OxqVLl7QeN2fOHPTr169SDETrY8wY4LvvjD8/L08+LdStW/H93brJMYArV0yJTn8nTgABAbLl\ncv++7OZSqeR4SFKSfDfj66/l00s2NtYbJyEi4+hMEADQtm1bDB8+HIMGDcJTTz2F3377Tec5J0+e\nhIeHB9zc3GBvb4+wsDBsK/iTsogvv/wSL730Eho0aGB49BVUnz5yDqWLF407/+xZ+f5DwfhDAVtb\nOWBsqVbE0aPAs8/KLqZRo+Qa3ICMwcMDuHBBvqPRrJnczwRBVLHoTBDbt2+Hp6cnWrZsiaCgILi5\nuaF///46C05NTYWrq6tm28XFBampqSWO2bZtG6ZOnQoAWud8qoxsbYFXXgFWrzbu/CNHSrYeCowY\nYbnFiQoSBCBbRG3byu+7dgVOn5aD6EX/SZ97TrYsbt2yTHxEZBqdCeK9997DsWPH0KpVKyQnJ+PA\ngQPo3LmzzoL1udnPmjULCxYs0DyrW1W6mADZzbRmjewuMtThw6UniC5dZHfPhQsmhaeTWi27mJ55\nRvvnjo4l99nby7mjtm6VP/eQIUBWlrJxEpHxdC4YZG9vj/r16yM/Px9qtRo9e/bEa6+9prNgZ2dn\npKSkaLZTUlLg4uJS7Jj4+HiEhYUBANLS0rB7927Y29sjNDS0RHnz5s3TfB8UFISgoCCdMZRnXl6A\nm5t8omnAAP3PE0ImiNLG/G1s5NxMa9aUfoyp9uyRL/o1bSrngjLEsGHyZbqZM+X2Tz/JVg8RmS4u\nLg5xcXHmK1DoEBwcLDIzM8Wrr74qRowYIWbMmCG6dOmi6zSRm5srWrZsKZKTk0VOTo7w8/MTiYmJ\npR4/ZswYsXnzZq2f6RFmhfT110IMG2bYOUlJQjRtKkR+funHXLggj8nLMy2+0ri6CuHjI8TYsYaf\nm50tRO3aQshUJ8QLL5Q8JihIiMOHTY+TqKoz9d6ps4tp27ZtqFWrFj7//HP069cPHh4exeZmKo2d\nnR0iIiIQEhICb29vjBgxAm3atEFkZCQiIyPNkNoqvhEjDH8noqB7qawevLZtgSZNgAMHTI+xqNdf\nB5YuBVJSZBdWwfiDIapXl3M19e0rn8T6+WfZJVbg0SP5Mxo7PkNE5lPmXEx5eXno06cPYmNjLRlT\nCZVlLiZtRo4EunfXfyK7SZOAdu2AGTPKPu7LL+WUF2vXmh5jAQ8POSHfs8/KiQFjY4HWrQ0v5+5d\n2X5o2FAmixdekHNUffcdMHasTJyPHgFRUfKzvDwuhkRkDEXnYrKzs4ONjU2xuZjIvAx9J6KsAeqi\nRo4Edu6UL6eZw9278guQCe3GDeOSAyBX2GvYsDDO99+XP1NUlByTGDRIrp1RMCvsrFlyoj8isiyd\ns7mGhoYiISEBffv2Ra3/LaisUqmwdOlSiwRYcL3K2oJQq+Vg9Y4d8i3ksqSlAe7uwF9/AXY6Hy+Q\nN9jQUDndhal27gS++EJ2DYWEmG9a8awsmSwePpQD7NWrA199BVy6BCxaJLvLLl6U192zxzzXJKoq\nFFswqMDQoUM1608XXKyqvK9gCba2wOTJ8qa4YkXZxx49Kh8r1Sc5AHIupCVLzJMgjh8HOneWcy2Z\nk4ODfLKpQweZ/AYNktcZOhTo3Vu2Upo3l4sjqdXsaiKypFJvNcHBwThw4AAuXryIRYsWWTKmKmfi\nRPnY66JFck2H0hw+bNi60wMHyjGL5GT50popTp1SbsGfVavkoHturhxbad1atib69JGf5+bKcY8D\nB2RLgogso9QxiD/++ANHjx7F9u3bcfr06RJfZD6NGskJ/HSNRRw/btiTQ9WqyQHfNWtMCg9CyLUc\nAgJMK6c0BQ1Se3v5lJTNE7+VdnbyzfPvvy/cl5MDvPqqXKxIl6It7L17gb//Nj1mS1GpCr8qUtxU\nOZQ6BrFx40ZERUXhyJEjCNByZ7Dkk02VeQyiwJEj8gmey5dL3iAB+Vd03bpyDqfatfUv99QpORB8\n7Zrxq7ndvCkT0++/G3e+Ody9K590SkmR9fPvf8vB7QMHgF69Sh5/+zbw8svAunVA48Zy38qVwIQJ\nwEcfyQQTHFy44FJ5I4ScEfdf/yq+f/JkYPlyrsxH+jH53qnrRYn58+eb9KKFOegRZoWXny+En58Q\ne/Zo//z0aSHatDGuXB8fIWJjjY9t0yYhBg0y/nxzCQ0tfMEOEMLWVoiXXy55XHZ24TEDBhQ/58mv\nu3ct+zPcvl34fU6OjOGzz4SYPLlw/+XLQvTsKT976im5Lzm5+M+dlSXE/fsWDZ0qIFPvnTpflHv/\n/feNzz6kN5VKdpksW6b98xMn5OCtMeVOmSIHwY31yy9yqVRr+7//K7796qvysdgnn8IuuqTrrl2y\nJTF7thzgLlgOtWNH+d8GDWTLLT8fiIiQ9aVtPazz5+XLgevWyTIB2arTd+2sx4/lPFSNG8trbN9e\n+JjwG28AkZGFXUleXvIdE1vbwhUC3dzkgkxRUfKaDg6yJalSAQsWaL9mYmJhmQ8eFP9MCDkt/O3b\nxbvgADmhYkyMPOfxY9lSE8K8M/HeuCHjMuesEKQAMyUqRVWQME32999C1KsnxM2bJT8bM0aI5cuN\nK/f+fSHq1BEiNdW483v3FuKnn4w715wePRJiyhQhJkyQf32r1XKqkqL18tdfhX9pX78u//vHH0L8\n+qsQK1cWL8/fv/DYfv0Kv2/RQoht2wr/HZ5+umTLY/nywu979xbiwAHtMffvL8To0aW3YBYtEuLt\nt2UrrWBftWryv6VNlbJvX8ly1q4tu6UECDFypBAPH8pWjK5jdX05OsrWqVotRIMGcl/R368ff5Qt\no9279S/zP/+R5RZsr18vRLduQnTuLMTBg0Js3iyv+eQ0MwVxFKVWC5GRIf+fKk1BWXl52sutDEy9\nd1aIO29VSRBCCPHaa/KG8SQvLyESEowvd8oUIYzpLczPF6JuXXmTLY927xYiMLBw+8cf5c3l/Hn9\nzlerhQgIKLwpDRtW+H3LlkJERel/gxs3rnjZ69YV/zw6WogHD+SNq2CfOW5KpcVTv768qZ45o/3z\n557Tvv/eJu9fAAAU1UlEQVTtt4U4d06Itm3l9j/+If+7f7+ch8vU5FLwpVbL30tzlafkl7+/ENOm\nCbFkiRAeHmUfa2cnRJMmQsycWbye69aV/xYffVTynKAgIVasEMLNTYjmzeUfKR9+KMT778v5yhYv\nNvz3Qq22UII4dOiQ+Pbbb4UQQvz555/ixo0bJl3UUFUpQVy5IkTDhvIvvQL37gnh4CBEbq7x5Z49\nK4Szs+FlJCUJ4eJi/HWVlpcnf65z52QLA5CtAUPLKJhAUAh5Eyj6P2+HDnKsIj1diMRE2RoBhFiz\nRtbP9OlCuLsL0ayZjCE/X4hjxwrP79VL/hs+eU1zjX/k5wsxeLBMQAVyckoeN2eOjGf5cjmG8SRD\nfjeK1tGNGzIGN7fCffv2GV5mwV/yBQq+V6vlV3a2bGUUbe3VqyfEli2ytVew79VXZVI7c0Z7a6vg\na8oUIZ55Rt6wQ0OF+Ne/5H5vb+snJPN9KZwgwsPDxfPPPy88PT2FEELcunVLPPvssyZd1FAo7acP\nD9d+Qnh4hT5+XStlyu/aVf7PZEg869cLEd26fNVPacfv6xouAJkMDS2/WBeDmeIJR7j47bfyUz88\nvmIfn5AgxLJlQoRD+/HhkL//vXoJMX68/APG1AShc6oNPz8/JCQkwN/fHwkJCQAAX19fnDt3TtGx\nkaKqwmOuRR0+LOdounJFDlR+9JGc8fTTT00rd906+VLavn36nzN7NuDkBLz3nmnXVlJyMhAYKN8l\nadYM+Phj85X96JEcqNXn0eKhQ4EtW4rH5eZmvliIDKXoZH0AUL16ddgUeTA/i0uAKa5rVzk/UcFT\nIwXTXJhq6FDg3Dng6tXSj7l1S14/N1duK/mCnLm0aAF06iQT4MCB5i27Zk393zvZvFk+YZSUJBML\nkwNVdDoTxLBhwzB58mRkZGRgxYoVCA4OxoQJEywRW5WlUsm/3Bctkm3Hspb2NET16nJepoiI0o85\nflzO+bR5s3z08/Tp8vGIqy5Tp8q68vOzbhw2NkDLlkCNGtaNg8gcdHYxAcDevXuxd+9eAEBISAj6\nFEySYyFVrYsJkDfnNm2AuXNl905qqnnK/f13wMdHPl9fr17Jz999V86aamsrp+jo21e+SV3eqdVy\n8SEL/2oSlWum3jt1JojPPvsMYWFhcHZ2NvoipqqKCQIAvvkGePNNOSVE0b5tU40dKxf/effdkp/1\n7y8n+HvzTdldk5oqWxNEVPEoPgbx4MED9O3bF926dUNERATu3Llj9MXIMK+8IvvAzTH+UNSbb8pu\npuzskp8lJMgupZkz5THlffyBiJSjVxcTAJw9exYbNmzApk2b4OLiggPmXvC4DFW1BQHISfw8PQtX\nYDOXgQPlgkITJxbu++MP2f2UliZnDnVxATZtYrcNUUWleAuiQMOGDdG4cWM8/fTTuFuw9iQpruCJ\nJnN76y3gs8+KT5edkCDnKFKpAEdHOUDdu7f5r01EFYPOBPHVV18hKCgIwcHBSEtLw8qVKy36DgQp\no0cP4Kmn5FKnBRIS5MpuBdzdOa00UVWmc/HK3377DV988QXa61owmSoUlUo+IfXJJ3LdapVKJoih\nQ60dGRGVF6WOQWRmZsLJyQl//fWX1jWo62l7RlIhVXkMQkn5+YCvr3xDu39/2WLYuVNON01EFZ9i\nj7kOHDgQO3fuhJubm9YEkZycbPRFDcUEoZyNG4HFi+W7D66ucm0FW1trR0VE5qD4exDlAROEcgpa\nEQMHAv/9r3yLmogqB8WfYgoODtZrH1VMNjZyxbBPPy0+QE1EVOog9aNHj/Dw4UPcvXsX6enpmv2Z\nmZlINde8D1QuvPQS4O0tZ0QlIipQaoKIjIzEkiVL8Pvvv8O/yGxtjo6OmD59ukWCI8uwsZFTjDs6\nWjsSIipPdI5BLF26FDNnzrRUPFpxDIKIyHAWGaS+cOECEhMTkV1k8p5Ro0YZfVFDMUEQERlO8QQx\nb948HDx4EBcvXsTAgQOxe/dudOvWDZs2bTL6ooZigiAiMpziTzFt2rQJ+/fvR5MmTbBq1SqcPXsW\nGRkZRl+QiIgqBp0JombNmrC1tYWdnR3u37+Phg0bIiUlxRKxERGRFemciykwMBD37t3DxIkTERAQ\nAAcHBzz77LOWiI2IiKzIoDepk5OTkZmZCT8LL/zLMQgiIsMpNkgdHx+vdQ6mAh07djT6ooZigiAi\nMpxiCSIoKKjMBBEbG6vXBWJiYjBr1iyo1WpMmDABc+bMKfb52rVrsWjRIggh4OjoiOXLl8PX17d4\nkEwQREQGK9eT9anVarRu3Rr79++Hs7MzAgMDER0djTZt2miOOXbsGLy9vVG7dm3ExMRg3rx5OH78\nePEgmSCIiAxm6r1T5yD16tWrtbYk9HlR7uTJk/Dw8ICbmxsAICwsDNu2bSuWILp06aL5vnPnzrh1\n65Y+cRMRkcJ0JohTp05pEsSjR4/w888/o2PHjnoliNTUVLi6umq2XVxccOLEiVKPj4qKwoABA/SJ\nm4iIFKYzQURERBTbzsjIwIgRI/QqvKwxjCfFxsbi22+/xZEjR7R+Pm/ePM33QUFBCAoK0rtsIqKq\nIC4uDnFxcWYrT2eCeFKtWrX0Xk3O2dm52Et1KSkpcHFxKXHcuXPnMHHiRMTExKBu3bpayyqaIIiI\nqKQn/3ieP3++SeXpTBCDBg3SfJ+fn4/ExEQMHz5cr8IDAgJw7do13Lx5E02bNsX69esRHR1d7Jjf\nfvsNL774Iv7zn//Aw8PDwPCJiEgpOp9iKtpcsbOzQ/PmzYuNK+iye/duzWOu48ePx9tvv43IyEgA\nwOTJkzFhwgRs3boVzZo1AwDY29vj5MmTxYPkU0xERAaz2GOumZmZyMvL02zXq1fP6IsaigmCiMhw\nij/mGhkZifDwcFSvXh02Njaai964ccPoixIRUfmnswXh4eGB48ePo379+paKqQS2IIiIDKf4ehAt\nW7ZEzZo1jb4AERFVTDpbEKdPn8aYMWPQpUsXVKtWTZ6kUmHp0qUWCbDgemxBEBEZRvExiEmTJqF3\n795o164dbGxsIIQw6AU4IiKqmHS2IDp06ICEhARLxaMVWxBERIZTfAyif//+iIyMxB9//IH09HTN\nFxERVW46WxBubm5au5T0nW7DHNiCICIyXLleD8JcmCCIiAxXrteDICKiikvR9SCIiKjiMriLqWA9\niD179igVUwnsYiIiMpziTzE9yZD1IIiIqOJSdD0IIiKquAxeD8LNzU3rqnBKYhcTEZHhFHuK6dq1\na7hz506JtZ8PHz6MnJwcuLu7G31RIiIq/0odg5g1axacnJxK7HdycsKsWbMUDYqIiKyv1ARx584d\n+Pr6ltjv6+vLQWoioiqg1ASRkZFR6knZ2dmKBENEROVHqQkiICAAK1asKLH/m2++gb+/v6JBERGR\n9ZX6FNPt27cxZMgQVKtWTZMQ4uPjkZOTg61bt6JJkyaWC5JPMRERGUzRyfqEEIiNjcWFCxegUqnQ\ntm1b9OrVy+iLGYsJgojIcJzNlYiItLL4VBtERFQ1MEEQEZFWTBBERKQVEwQREWnFBEFERFoxQRAR\nkVZMEEREpBUTBBERacUEQUREWjFBEBGRVkwQRESkFRMEERFppWiCiImJgZeXFzw9PbFw4UKtx8yc\nOROenp7w8/NDQkKCkuEQEZEBFEsQarUa06dPR0xMDBITExEdHY1Lly4VO2bXrl24fv06rl27hhUr\nVmDq1KlKhVNpxMXFWTuEcoN1UYh1UYh1YT6KJYiTJ0/Cw8MDbm5usLe3R1hYGLZt21bsmO3bt2P0\n6NEAgM6dOyMjIwN37txRKqRKgb/8hVgXhVgXhVgX5qNYgkhNTYWrq6tm28XFBampqTqPuXXrllIh\naRj6C6Tr+LI+1/aZrn1Pfq7kL3x5qwtDt82JdWF82awL/Y+vSHWhWIJQqVR6HffkYhb6nmeK8vYP\n/uQ+/vLrv21OrAvjy2Zd6H98haoLoZBjx46JkJAQzfYnn3wiFixYUOyYyZMni+joaM1269atxe3b\nt0uU5e7uLgDwi1/84he/DPhyd3c36T5uB4UEBATg2rVruHnzJpo2bYr169cjOjq62DGhoaGIiIhA\nWFgYjh8/jjp16qBRo0Ylyrp+/bpSYRIRUSkUSxB2dnaIiIhASEgI1Go1xo8fjzZt2iAyMhIAMHny\nZAwYMAC7du2Ch4cHHBwcsGrVKqXCISIiA6mEMGFFayIiqrT4JjUREWnFBEFERFpVyASRlZWF0aNH\nY9KkSVi3bp21w7Gq5ORkTJgwAcOGDbN2KFa3bds2TJo0CWFhYdi3b5+1w7Gqy5cvY+rUqRg+fDii\noqKsHY5VZWVlITAwEDt37rR2KFYVFxeH7t27Y+rUqTh48KBe51TIBLFlyxYMHz4cK1aswPbt260d\njlW1aNECK1eutHYY5cLgwYOxYsUKfP3111i/fr21w7EqLy8vLF++HD/88AP27Nlj7XCsatGiRRgx\nYoS1w7A6GxsbODo6IicnBy4uLvqdo3BMehs3bhwaNWqEdu3aFduvbcK/om9g29raWjxWpRlSF5Wd\nMXXx0UcfYfr06ZYM0yIMrYsdO3Zg4MCBCAsLs3SoijKkHvbt2wdvb280aNDAGqEqzpC66N69O3bt\n2oUFCxYgPDxcvwuY9BaFGR06dEicPn1a+Pj4aPbl5eUJd3d3kZycLB4/fiz8/PxEYmKiWLNmjfjp\np5+EEEKEhYVZK2TFGFIXBV566SVrhKo4Q+oiPz9fzJ49W+zfv9+KESvHmN8LIYQIDQ21dKiKMqQe\n3n33XTFr1izRt29fMXjwYJGfn2/FyM3PmN+JnJwcve8Xir0HYaju3bvj5s2bxfYVnfAPgGbCv5kz\nZ2L69OnYuXMnQkNDLR+swgypi0aNGuGdd97BmTNnsHDhQsyZM8fyASvIkLrYv38/Dhw4gMzMTFy/\nfh2TJ0+2fMAKMqQu/vzzT2zZsgXZ2dno2bOn5YNVkCH18NFHHwEAVq9ejQYNGlhkKh9LMqQuLl++\njD179iAjIwMzZszQq/xykyC00TaZ34kTJ1CrVi18++23VozM8kqri3r16uHrr7+2YmSWV1pdfPnl\nl3r/4lcWpdVFjx490KNHDytGZlml1UOBglmjq4LS6mLu3LkYMmSIQWWVmzEIbSpbtjcF66IQ66IQ\n60JiPRQyZ12U6wTh7OyMlJQUzXZKSoreo++VDeuiEOuiEOtCYj0UMmddlOsEUXTCv8ePH2P9+vWV\ncsxBH6yLQqyLQqwLifVQyKx1YfZhdSOFhYWJJk2aiGrVqgkXFxfx7bffCiGE2LVrl2jVqpVwd3cX\nn3zyiZWjtAzWRSHWRSHWhcR6KKR0XXCyPiIi0qpcdzEREZH1MEEQEZFWTBBERKQVEwQREWnFBEFE\nRFoxQRARkVZMEEREpBUTBJV7NjY2ePPNNzXbixcvxvz5881S9pgxY7B582azlFWWjRs3wtvbG8HB\nwcX2//rrr4iOji71vN9//13naoE3b94ssR4AkTkwQVC5V61aNWzduhV//fUXAPNORmZKWXl5eXof\nGxUVhZUrV+LAgQPF9icnJ5e6bG5eXh6aNm2KjRs3Gh0jkSmYIKjcs7e3x6RJk/D555+X+OzJFsBT\nTz0FQK6/26NHD7zwwgtwd3fH3LlzsWbNGnTq1Am+vr64ceOG5pz9+/cjMDAQrVu31qxbrFar8dZb\nb6FTp07w8/PDihUrNOV2794dgwcPRtu2bUvEEx0dDV9fX7Rr1w5z584FAHzwwQc4cuQIxo0bh9mz\nZxc7fu7cufjvf/+LDh064IsvvsDq1asRGhqK4OBg9OnTB7/++it8fHwAyJbCc889B39/f/j7++PY\nsWMlrn/x4kV07twZHTp0gJ+fH65fv25QXRMVY54ZQYiU89RTT4nMzEzh5uYm7t+/LxYvXizmzZsn\nhBBizJgxYtOmTcWOFUKI2NhYUadOHXH79m2Rk5MjmjZtKsLDw4UQQixZskTMmjVLCCHE6NGjRf/+\n/YUQQly7dk24uLiI7OxsERkZKT766CMhhBDZ2dkiICBAJCcni9jYWOHg4CBu3rxZIs7U1FTRrFkz\nkZaWJvLy8kSvXr3Ejz/+KIQQIigoSMTHx5c4Jy4uTjz//POa7VWrVgkXFxdx7949IYQQycnJmtXC\nHj58KLKzs4UQQly9elUEBASUOGb69Oli7dq1QgghcnNzxaNHjwyrbKIiyvWCQUQFHB0dMWrUKCxd\nuhQ1a9bU65zAwEA0atQIAODh4YGQkBAAgI+PD2JjYwHILqbhw4drjmnZsiUuX76MvXv34vz589i0\naRMAaFaps7OzQ6dOndC8efMS1zt16hR69uyJp59+GgDw8ssv49ChQxg8eDAAQGiZ9uzJfSqVCn37\n9kWdOnVKHPv48WNMnz4dZ8+eha2tLa5evVrimGeffRYff/wxbt26hRdffBEeHh561RWRNuxiogpj\n1qxZiIqKQlZWlmafnZ0d8vPzAQD5+fl4/Pix5rPq1atrvrexsdFs29jYlDl+UDAuERERgYSEBCQk\nJCApKQm9e/cGADg4OJR6XtEbvhCi2BiHvuMdtWrV0rr/888/R5MmTXDu3Dn88ssvxX7WAiNHjsSO\nHTtQs2ZNDBgwQJMIiYzBBEEVRt26dTF8+HBERUVpbrZubm6Ij48HAGzfvh25ubkGlSmEwMaNGyGE\nQFJSEm7cuAEvLy+EhITgq6++0iSSq1ev4uHDh2WWFRgYiIMHD+Kvv/6CWq3GDz/8oHPZTycnJzx4\n8KBYPKXJzMxE48aNAQDff/891Gp1iWNu3LiBFi1aYMaMGRg8eDDOnz9f5vWJysIEQeVe0b+833jj\nDaSlpWm2J06ciIMHD6J9+/Y4fvy4ZpD6yfOeLK/gM5VKhWbNmqFTp04YMGAAIiMjUa1aNUyYMAHe\n3t7o2LEj2rVrh6lTpyIvL6/YuU9q0qQJFixYgJ49e6J9+/YICAjAoEGDyvzZfH19YWtri/bt2+OL\nL77QWn7B9rRp07B69Wq0b98eV65c0fqzbtiwAT4+PujQoQMuXryIUaNGlXl9orJwPQgiItKKLQgi\nItKKCYKIiLRigiAiIq2YIIiISCsmCCIi0ooJgoiItGKCICIirZggiIhIq/8PO0O0civZw/gAAAAA\nSUVORK5CYII=\n",
       "text": [
        "<matplotlib.figure.Figure at 0x9a9d90c>"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The simulation takes a while, in part because we need to generate about $1 / (0.2 * 0.2 + 0.4 * 0.2) \\approx 8.3$ trials per troll captured (can you see why?) and in part because `np.random.choice` is just slow. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit np.random.choice(bridges, p=ps)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10000 loops, best of 3: 143 \u00b5s per loop\n"
       ]
      }
     ],
     "prompt_number": 6
    }
   ],
   "metadata": {}
  }
 ]
}