CSE891 2012 week4 solutions

solutions-week4-fitting.ipynb

solutions-week4-monty-hall.ipynb

{
 "metadata": {
  "name": "solutions-week4-monty-hall"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "## The Monty Hall problem\n\nYou, lucky contestant, are on a game show!  You stand a chance to win a car (with a trade-in value of $50k)!\n\nThe host, one Monty Hall, describes the game to you as follows:\n\n   1. Here before you, you see three doors -- A, B, and C!  Behind one of them is the car.\n\n   2. We will start by having you pick one door, but **do not open it**.\n\n   3. Then, I will reveal what is behind one of the two doors you did not choose (needless to say, it will not be the car!)\n\n   4. At that point, you may either keep your first choice, OR you may switch your choice to another door.\n\nIf you can identify which door has the car behind it, you get to keep the car (or the money).\n\nThe question for you is this: as a winning strategy, should you (a) always stay with your original door choice, (b) always switch, or (c) it doesn't matter?"
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "### Monty Hall Monte Carlo\n\nYou, being an accomplished computational scientist, decide that rather than thinking hard about this, you're just going to simulate it using the Monte Carlo method (http://en.wikipedia.org/wiki/Monte_Carlo_method).\n\nLet's start by setting up the problem."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# grab the pseudo-random # generator module in Python: http://blog.doughellmann.com/2010/10/pymotw-random-pseudorandom-number.html\nimport random\n\n# now, build a function to create 3 doors, with one car behind them.\n# this function will return a dictionary with keys A, B, and C, containing associated values 'empty' or 'car'.\ndef create_doors():\n    doors = {}\n    doors['A'] = 'empty'\n    doors['B'] = 'empty'\n    doors['C'] = 'empty'\n    \n    # randomly choose *one* of the three doors\n    car_is_behind = random.choice(doors.keys())\n    doors[car_is_behind] = 'car'\n    \n    return doors\n",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "Next, here are two functions, one which simulates choice (a) and one which simulates choice (b).  If the function returns true, you've won! If the function returns false, you've lost."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "def always_switch():\n    # set up the problem\n    doors_d = create_doors()\n    \n    # pick a door\n    doors = ['A', 'B', 'C']\n    my_choice = random.choice(doors)\n    doors.remove(my_choice)\n    assert len(doors) == 2, \"you should only have two doors left...\"\n    \n    # now Monty Hall picks a door:\n    while 1:\n        monty_choice = random.choice(doors)\n        if doors_d[monty_choice] != 'car': # he'll never reveal the car!\n            break\n    \n    doors.remove(monty_choice)\n    \n    # now, because you always switch, you're left with monty's non-choice:\n    assert len(doors) == 1, \"you should only have one door left...\"\n    \n    my_choice = doors[0]\n    \n    if doors_d[my_choice] == 'car':\n        return True                    # you win!\n    return False                       # you lose :(\n\ndef never_switch():\n    # set up the problem\n    doors_d = create_doors()\n    \n    # pick a door\n    doors = ['A', 'B', 'C']\n    my_choice = random.choice(doors)\n    doors.remove(my_choice)\n    assert len(doors) == 2, \"you should only have two doors left...\"\n    \n    # now Monty Hall picks a door:\n    while 1:\n        monty_choice = random.choice(doors)\n        if doors_d[monty_choice] != 'car': # he'll never reveal the car!\n            break\n    \n    doors.remove(monty_choice)\n    \n    # now, because you always switch, you're left with monty's non-choice:\n    assert len(doors) == 1, \"you should only have one door left...\"\n    \n    # you stick with your original choice:\n    if doors_d[my_choice] == 'car':\n        return True                    # you win!\n    return False                       # you lose :(",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# ok, let's try this out!\nprint always_switch()\nprint always_switch()\nprint always_switch()\n\nprint never_switch()\nprint never_switch()\nprint never_switch()\n",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "True\nTrue\nTrue\nFalse\nFalse\nFalse\n"
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "OK, a couple of notes here.\n\nFirst, this *is* a true implementation of the Monty Hall scenario, right?  Even though you're randomly choosing doors, it's no different from what you'd normally be doing, right -- guessing?\n\nSecond, every time you run this, you will get a different set of answers -- because we're using a random number generator."
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "## Question A: is it better to always switch or to never switch, or is it the same?\n\nWrite a loop that runs always_switch() many, many times, and counts up the number of times you win vs the number of times you lose.\n\nDo the same for never_switch().\n\nWhat is your conclusion?  Should you always switch, never switch, or does it not matter?  How much more likely are you to win in one case over another? Please answer in comments in the code."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "N = 100000\n\nalways_switch_won = 0\nfor i in range(N):\n    if always_switch():\n        always_switch_won += 1\n\nnever_switch_won = 0\nfor i in range(N):\n    if never_switch():\n        never_switch_won += 1\n\nprint 'if I always switch, I win', always_switch_won / float(N) * 100, '% of the time'\nprint 'if I never switch, I win', never_switch_won / float(N) * 100, '% of the time'\n\n## obviously it is better to always switch -- 2/3 of the time I win!",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "if I always switch, I win 66.771 % of the time\nif I never switch, I win 33.519 % of the time\n"
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "## Question B: combine the functions\n\nWrite a new function, 'monty_hall(do_switch)' where 'do_switch' is either True or False, that combines the functionality of 'always_switch' and 'never_switch', and returns True if you've won and False if you've lost.  For example, 'monty_hall(False)' will return random results from the same decision making process as 'never_switch', and 'monty_hall(True)' will return random results from the same process as 'always_switch'.\n\nThen, re-write the loops in the first question to use *only* this new function.  Your loop should no longer contain direct calls to 'always_switch' and 'never_switch', but you should get the same qualitative results."
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "### two ways to do this -- write an encapsulating function, OR modify always_switch\n"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# way 1 -- write an encapsulating function\n\ndef monty_hall(do_switch):\n    if do_switch:\n        return always_switch()\n    return never_switch()\n\nprint monty_hall(True)\nprint monty_hall(False)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "False\nFalse\n"
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# rewrite answer to Q A\nN = 100000\n\nalways_switch_won = 0\nfor i in range(N):\n    if monty_hall(True):\n        always_switch_won += 1\n\nnever_switch_won = 0\nfor i in range(N):\n    if monty_hall(False):\n        never_switch_won += 1\n\nprint 'if I always switch, I win', always_switch_won / float(N) * 100, '% of the time'\nprint 'if I never switch, I win', never_switch_won / float(N) * 100, '% of the time'\n\n## obviously it is better to always switch -- 2/3 of the time I win!",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "if I always switch, I win 66.578 % of the time\nif I never switch, I win 33.135 % of the time\n"
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# way 2 -- rewrite always_switch\n\ndef monty_hall_b(do_switch):\n    # set up the problem\n    doors_d = create_doors()\n    \n    # pick a door\n    doors = ['A', 'B', 'C']\n    my_choice = random.choice(doors)\n    doors.remove(my_choice)\n    assert len(doors) == 2, \"you should only have two doors left...\"\n    \n    # now Monty Hall picks a door:\n    while 1:\n        monty_choice = random.choice(doors)\n        if doors_d[monty_choice] != 'car': # he'll never reveal the car!\n            break\n    \n    doors.remove(monty_choice)\n    \n    # now, because you always switch, you're left with monty's non-choice:\n    assert len(doors) == 1, \"you should only have one door left...\"\n    \n    if do_switch:\n        my_choice = doors[0]\n    \n    if doors_d[my_choice] == 'car':\n        return True                    # you win!\n    return False                       # you lose :(\n\nprint monty_hall_b(True)\nprint monty_hall_b(False)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "True\nTrue\n"
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# rewrite answer to Q A\nN = 100000\n\nalways_switch_won = 0\nfor i in range(N):\n    if monty_hall_b(True):\n        always_switch_won += 1\n\nnever_switch_won = 0\nfor i in range(N):\n    if monty_hall_b(False):\n        never_switch_won += 1\n\nprint 'if I always switch, I win', always_switch_won / float(N) * 100, '% of the time'\nprint 'if I never switch, I win', never_switch_won / float(N) * 100, '% of the time'\n\n## obviously it is better to always switch -- 2/3 of the time I win!",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "if I always switch, I win 66.735 % of the time\nif I never switch, I win 33.416 % of the time\n"
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "## Question C: simplify create_doors.\n    \nCopy 'create_doors' to 'create_doors2' and change the function so that it returns a dictionary where the car is *always* behind door A.  Then create a copy of the functions in A or B that use this new create_doors2.  Do your results change?  Please answer in comments in the code."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# change create_doors so that the car is always behind door A.\ndef create_doors_2():\n    doors = {}\n    doors['A'] = 'car'\n    doors['B'] = 'empty'\n    doors['C'] = 'empty'\n    \n    return doors\n\n\ndef monty_hall_c(do_switch):\n    # set up the problem\n    doors_d = create_doors_2()\n    \n    # pick a door\n    doors = ['A', 'B', 'C']\n    my_choice = random.choice(doors)\n    doors.remove(my_choice)\n    assert len(doors) == 2, \"you should only have two doors left...\"\n    \n    # now Monty Hall picks a door:\n    while 1:\n        monty_choice = random.choice(doors)\n        if doors_d[monty_choice] != 'car': # he'll never reveal the car!\n            break\n    \n    doors.remove(monty_choice)\n    \n    # now, because you always switch, you're left with monty's non-choice:\n    assert len(doors) == 1, \"you should only have one door left...\"\n    \n    if do_switch:\n        my_choice = doors[0]\n    \n    if doors_d[my_choice] == 'car':\n        return True                    # you win!\n    return False                       # you lose :(\n\nprint monty_hall_c(True)\nprint monty_hall_c(False)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "True\nTrue\n"
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "N = 100000\n\nalways_switch_won = 0\nfor i in range(N):\n    if monty_hall_c(True):\n        always_switch_won += 1\n\nnever_switch_won = 0\nfor i in range(N):\n    if monty_hall_c(False):\n        never_switch_won += 1\n\nprint 'if I always switch, I win', always_switch_won / float(N) * 100, '% of the time'\nprint 'if I never switch, I win', never_switch_won / float(N) * 100, '% of the time'\n\n## same results!",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "if I always switch, I win 66.804 % of the time\nif I never switch, I win 33.595 % of the time\n"
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "## Question D: what happens if you increase the number of doors?\n\nCopy 'create_doors2' to 'create_doors3' and change the function so that it returns a dictionary with 10 doors, and make a new Monty Hall (monty_hall3?) function that uses  this new 'create_doors3', in which Monty opens 8 doors for you. Note, you'll need to alter (not remove!) the assert statements.\n\nHow does the probability of winning change with 10 doors instead of 3?  (Just estimate based on the numbers you generate.)  Please answer in a Markdown cell (Cell... Markdown on the menus above)\n\nExtra pixie dust credit if you can give a general formula -- note that you can use LaTeX math formatting like so (double click on this cell to see the underlying formatting):\n\n$p_{winning} = 1/2$\n\nPrepare arguments for class next Monday!"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "# change create_doors so that the car is always behind door A.\ndef create_doors_3():\n    doors = {}\n    doors['A'] = 'car'\n    doors['B'] = 'empty'\n    doors['C'] = 'empty'\n    doors['D'] = 'empty'\n    doors['E'] = 'empty'\n    doors['F'] = 'empty'\n    doors['G'] = 'empty'\n    doors['H'] = 'empty'\n    doors['I'] = 'empty'\n    doors['J'] = 'empty'\n    \n    return doors\n\n\ndef monty_hall_d(do_switch):\n    # set up the problem\n    doors_d = create_doors_3()\n    \n    # pick a door - here, pick randomly from the keys available!\n    doors = doors_d.keys()\n    my_choice = random.choice(doors)\n    doors.remove(my_choice)\n    assert len(doors) == 9, \"you should only have two doors left...\"\n    \n    # now Monty Hall picks 8 doors:\n    n_removed = 0\n    while n_removed < 8:\n        monty_choice = random.choice(doors)\n        if doors_d[monty_choice] != 'car': # he'll never reveal the car!\n            doors.remove(monty_choice)\n            n_removed += 1\n    \n    # now, because you always switch, you're left with monty's non-choice:\n    assert len(doors) == 1, \"you should only have one door left...\"\n    \n    if do_switch:\n        my_choice = doors[0]\n    \n    if doors_d[my_choice] == 'car':\n        return True                    # you win!\n    return False                       # you lose :(\n\nprint monty_hall_c(True)\nprint monty_hall_c(False)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "True\nFalse\n"
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "N = 100000\n\nalways_switch_won = 0\nfor i in range(N):\n    if monty_hall_d(True):\n        always_switch_won += 1\n\nnever_switch_won = 0\nfor i in range(N):\n    if monty_hall_d(False):\n        never_switch_won += 1\n\nprint 'if I always switch, I win', always_switch_won / float(N) * 100, '% of the time'\nprint 'if I never switch, I win', never_switch_won / float(N) * 100, '% of the time'\n\n## WAY better to switch!",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "if I always switch, I win 90.131 % of the time\nif I never switch, I win 9.937 % of the time\n"
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "The probability of winning by switching is simple: it's $(N-1) / N$ where $N$ is the number of doors."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "",
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}

solutions-week4-penny.ipynb