ProbabilityBirthdaySurprise.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "This notebook illustrates the use of tables in conveying the combination of inferential and computational thinking through studying concepts of probability theory.  It the Birthday Surprise as a running example, based on a lecture by Ani Adhikari in http://data8.org/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# HIDDEN\n",
    "from datascience import *\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plots\n",
    "plots.style.use('fivethirtyeight')\n",
    "import numpy as np\n",
    "# datascience version number of last run of this notebook\n",
    "version.__version__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Inferential thinking.  I sit down next to a random person in class, what is the chance that I have the same birthday as that person?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# what is the chance that we have different birthdays?\n",
    "364/365"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# what is the chance that we have the same birdthday?\n",
    "1 - 364/365"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# what is the chance that my birthday is different from both my neighbors?\n",
    "(364/365) * (363/365)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# the same as one of them?\n",
    "1 - (364/365) * (363/365)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# the same as one of my four neighbors?\n",
    "1 - (364/365) * (363/365) * (362/365) * (361/365)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Wow, nearly 3%?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Computational thinking?  For a group of N people, what is the probability that at least two of them have the same birthday?  An algorithmic question.  Given K people with different birthdays, what is the probability that the next random person will have a different birthday than any of them?  If we can answer this single step, we have a way to answer the general question?  Yes, it is like induction.  But it is constructive too.  That's an algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Let's create a little table, kind of like what might think of as a spreadsheet, to collect all of our computational and inferential thoughts about solving this problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "bday = Table()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# lets start with numbering the days in the year (we'll start with zero).  We don't care if they are\n",
    "# in calendar order, backwars, sideways or the ways that we encounter them in meeting random people\n",
    "bday[\"day\"] = range(365)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "bday"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Cool, we have a column of the days, but its pretty long and we can see them all on the page, but a graph is a great way to summarize things, so let's look at what we have."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "bday.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Yep, as easy as pi.  The days in a year.  But we really need those diminishing fractions of the days left in the year.  OK, that's easy, lets build a new column of the days that are left after we've seen some.  And let's look at what we've got"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "bday['left']= 364-bday['day']\n",
    "bday"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#of course, we could plot these\n",
    "bday.plot()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# or on top of each other\n",
    "bday.plot(overlay=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "After we have k people with different birthdays, we have 365-k possible days left.  But what we really want is the fraction of days in the year left.  Obviously, divide by the number of days in the year.  Let's do that and see where we are."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "bday['frac']=bday['left']/365\n",
    "bday"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "OK, that looks like its going from 1 to 0 just as we'd expect.  And we can see how things are working together, just as we might in a spread sheet.  We can focus on the data that comes out of the computation.  In a spreadsheet this would be all spread around in the cells.  Here the computation is clearly laid out and we can see how it progresses from one step to the next by building up the table. \n",
    "\n",
    "We might want to select just 'fraction left' to look at."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "bday.select('frac').plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Ah, but remember the inferential part.  Given k people, what is the probability they all have different birthdays.  That's the product of these diminishing fractions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# each column in our table is really a sequence of values\n",
    "bday[\"frac\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Phew that's a lot of numbers... tables gives us a little peek, but we can always look into it for more.  Sure beats scrolling through 365 rows in excel!\n",
    "\n",
    "So we need something to take the running product of a bunch of numbers.  These things you'll learn to just build.  But lots of folks built useful ones already.  That's a beautiful thing about computing - you can naturally build on the work of others. Here we'll use the 'cumulative product' tool from the 'numpy' library.  Don't worry you'll see that later.  The important thing it that it does what we did for 2, 3 or 4 neighbors - but for all of them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "bday[\"different\"] = np.cumprod(bday[\"frac\"])\n",
    "bday"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# finally the probably that at least two people have the same birthday\n",
    "bday['some same bday'] = 1-bday['different']\n",
    "bday"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# so 14% with just ten people.  How about the whole story\n",
    "# Table.select produces a table containing only the selected columns\n",
    "bday.select('some same bday').plot()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# wow, let's look at the start of that\n",
    "# Table.take produces a table containing the rows taken from a Table.\n",
    "bday.take(range(50))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Table methods generally produce new tables so they compose naturally.\n",
    "# Here to convey the essence of the Birthday Surprise\n",
    "bday.take(range(50)).select('some same bday').plot()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Since indexing a column by its name gives an array, it can be indexed.\n",
    "bday['some same bday'][20]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Now that we understanding this by building it up step by step, could we put it all into one place that we might call a program for answering this question?  Sure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# altogether now like a real program\n",
    "bd = Table()\n",
    "bd[\"day\"] = range(365)\n",
    "bd['left']= 364-bd['day']\n",
    "bd['frac']=bd['left']/365\n",
    "bd[\"different\"] = np.cumprod(bd[\"frac\"])\n",
    "bd['some same bday'] = 1-bd['different']\n",
    "bd.select('some same bday').take(range(50)).plot()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "bd"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}