{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Peter Norvig, 12 Feb 2016. Original notebook: http://norvig.com/ipython/Probability.ipynb Modifications by Byron Wallace for DS4420 (Sp 2020).
\n",
"\n",
"# A Concrete Introduction to Probability (using Python)\n",
"\n",
"\n",
"This notebook covers the basics of probability theory, with Python 3 implementations. (You should have some background in [probability](http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/pdf.html) and [Python](https://www.python.org/about/gettingstarted/).) \n",
"\n",
"\n",
"\n",
"In 1814, Pierre-Simon Laplace [wrote](https://en.wikipedia.org/wiki/Classical_definition_of_probability):\n",
"\n",
">*Probability ... is thus simply a fraction whose numerator is the number of favorable cases and whose denominator is the number of all the cases possible ... when nothing leads us to expect that any one of these cases should occur more than any other.*\n",
"\n",
"\n",
"Pierre-Simon Laplace
1814\n",
"\n",
"\n",
"Laplace really nailed it, way back then! If you want to untangle a probability problem, all you have to do is be methodical about defining exactly what the cases are, and then careful in counting the number of favorable and total cases. We'll start being methodical by defining some vocabulary:\n",
"\n",
"- **Experiment**:\n",
" An occurrence with an uncertain outcome that we can observe.\n",
"
*For example, rolling a die.*\n",
"- **Outcome:**\n",
" The result of an experiment; one particular state of the world. What Laplace calls a \"case.\"\n",
"
*For example:* `4`.\n",
"- **Sample Space**\n",
" The set of all possible outcomes for the experiment. \n",
"
*For example,* `{1, 2, 3, 4, 5, 6}`.\n",
"- **Event**\n",
" A subset of possible outcomes that together have some property we are interested in.\n",
"
*For example, the event \"even die roll\" is the set of outcomes* `{2, 4, 6}`. \n",
"- **Probability**\n",
" As Laplace said, the probability of an event with respect to a sample space is the number of favorable cases (outcomes from the sample space that are in the event) divided by the total number of cases in the sample space. (This assumes that all outcomes in the sample space are equally likely.) Since it is a ratio, probability will always be a number between 0 (representing an impossible event) and 1 (representing a certain event).\n",
"
*For example, the probability of an even die roll is 3/6 = 1/2.*\n",
"\n",
"This notebook will develop all these concepts; I also have a [second part](http://nbviewer.jupyter.org/url/norvig.com/ipython/ProbabilityParadox.ipynb) that covers paradoxes in Probability Theory."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"# Code for `P` \n",
"\n",
"`P` is the traditional name for the Probability function:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [],
"source": [
"from fractions import Fraction\n",
"\n",
"def P(event, space): \n",
" \"The probability of an event, given a sample space of equiprobable outcomes.\"\n",
" return Fraction(len(event & space), \n",
" len(space))"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Read this as implementing Laplace's quote directly: *\"Probability is thus simply a fraction whose numerator is the number of favorable cases and whose denominator is the number of all the cases possible.\"* \n",
" \n",
"\n",
"# Warm-up Problem: Die Roll"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"What's the probability of rolling an even number with a single six-sided fair die? \n",
"\n",
"We can define the sample space `D` and the event `even`, and compute the probability:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(1, 2)"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"D = {1, 2, 3, 4, 5, 6}\n",
"even = { 2, 4, 6}\n",
"\n",
"P(even, D)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"It is good to confirm what we already knew.\n",
"\n",
"You may ask: Why does the definition of `P` use `len(event & space)` rather than `len(event)`? Because I don't want to count outcomes that were specified in `event` but aren't actually in the sample space. Consider:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(1, 2)"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"even = {2, 4, 6, 8, 10, 12}\n",
"\n",
"P(even, D)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Here, `len(event)` and `len(space)` are both 6, so if just divided, then `P` would be 1, which is not right.\n",
"The favorable cases are the *intersection* of the event and the space, which in Python is `(event & space)`.\n",
"Also note that I use `Fraction` rather than regular division because I want exact answers like 1/3, not 0.3333333333333333."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"\n",
"\n",
"# Urn Problems\n",
"\n",
"Around 1700, Jacob Bernoulli wrote about removing colored balls from an urn in his landmark treatise *[Ars Conjectandi](https://en.wikipedia.org/wiki/Ars_Conjectandi)*, and ever since then, explanations of probability have relied on [urn problems](https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=probability%20ball%20urn). (You'd think the urns would be empty by now.) \n",
"\n",
"\n",
"Jacob Bernoulli
1700\n",
"\n",
"For example, here is a three-part problem [adapted](http://mathforum.org/library/drmath/view/69151.html) from mathforum.org:\n",
"\n",
"> An urn contains 23 balls: 8 white, 6 blue, and 9 red. We select six balls at random (each possible selection is equally likely). What is the probability of each of these possible outcomes:\n",
"\n",
"> 1. all balls are red\n",
"2. 3 are blue, 2 are white, and 1 is red\n",
"3. exactly 4 balls are white\n",
"\n",
"So, an outcome is a set of 6 balls, and the sample space is the set of all possible 6 ball combinations. We'll solve each of the 3 parts using our `P` function, and also using basic arithmetic; that is, *counting*. Counting is a bit tricky because:\n",
"- We have multiple balls of the same color. \n",
"- An outcome is a *set* of balls, where order doesn't matter, not a *sequence*, where order matters.\n",
"\n",
"To account for the first issue, I'll have 8 different white balls labelled `'W1'` through `'W8'`, rather than having eight balls all labelled `'W'`. That makes it clear that selecting `'W1'` is different from selecting `'W2'`.\n",
"\n",
"The second issue is handled automatically by the `P` function, but if I want to do calculations by hand, I will sometimes first count the number of *permutations* of balls, then get the number of *combinations* by dividing the number of permutations by *c*!, where *c* is the number of balls in a combination. For example, if I want to choose 2 white balls from the 8 available, there are 8 ways to choose a first white ball and 7 ways to choose a second, and therefore 8 × 7 = 56 permutations of two white balls. But there are only 56 / 2 = 28 combinations, because `(W1, W2)` is the same combination as `(W2, W1)`.\n",
"\n",
"We'll start by defining the contents of the urn:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"{'B1',\n",
" 'B2',\n",
" 'B3',\n",
" 'B4',\n",
" 'B5',\n",
" 'B6',\n",
" 'R1',\n",
" 'R2',\n",
" 'R3',\n",
" 'R4',\n",
" 'R5',\n",
" 'R6',\n",
" 'R7',\n",
" 'R8',\n",
" 'R9',\n",
" 'W1',\n",
" 'W2',\n",
" 'W3',\n",
" 'W4',\n",
" 'W5',\n",
" 'W6',\n",
" 'W7',\n",
" 'W8'}"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def cross(A, B):\n",
" \"The set of ways of concatenating one item from collection A with one from B.\"\n",
" return {a + b \n",
" for a in A for b in B}\n",
"\n",
"urn = cross('W', '12345678') | cross('B', '123456') | cross('R', '123456789') \n",
"\n",
"urn"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"23"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(urn)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Now we can define the sample space, `U6`, as the set of all 6-ball combinations. We use `itertools.combinations` to generate the combinations, and then join each combination into a string:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"100947"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import itertools\n",
"\n",
"def combos(items, n):\n",
" \"All combinations of n items; each combo as a concatenated str.\"\n",
" return {' '.join(combo) \n",
" for combo in itertools.combinations(items, n)}\n",
"\n",
"U6 = combos(urn, 6)\n",
"\n",
"len(U6)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"I don't want to print all 100,947 members of the sample space; let's just peek at a random sample of them:"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"['W6 B1 B5 W7 R4 R6',\n",
" 'W3 R9 W5 R8 B3 B2',\n",
" 'R5 B6 W3 R4 R6 R2',\n",
" 'R5 W3 B1 W2 B3 B2',\n",
" 'R9 B4 R6 R1 B2 W8',\n",
" 'W6 B1 R8 W2 W4 R6',\n",
" 'B5 R3 W2 R2 R1 B2',\n",
" 'W3 W6 R7 W7 R4 W2',\n",
" 'R5 B6 W5 W2 W4 R2',\n",
" 'R5 B6 W7 R3 B4 W8']"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import random\n",
"\n",
"random.sample(U6, 10)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Is 100,947 really the right number of ways of choosing 6 out of 23 items, or \"23 choose 6\", as mathematicians [call it](https://en.wikipedia.org/wiki/Combination)? Well, we can choose any of 23 for the first item, any of 22 for the second, and so on down to 18 for the sixth. But we don't care about the ordering of the six items, so we divide the product by 6! (the number of permutations of 6 things) giving us:\n",
"\n",
"$$23 ~\\mbox{choose}~ 6 = \\frac{23 \\cdot 22 \\cdot 21 \\cdot 20 \\cdot 19 \\cdot 18}{6!} = 100947$$\n",
"\n",
"Note that $23 \\cdot 22 \\cdot 21 \\cdot 20 \\cdot 19 \\cdot 18 = 23! \\;/\\; 17!$, so, generalizing, we can write:\n",
"\n",
"$$n ~\\mbox{choose}~ c = \\frac{n!}{(n - c)! \\cdot c!}$$\n",
"\n",
"And we can translate that to code and verify that 23 choose 6 is 100,947:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [],
"source": [
"from math import factorial\n",
"\n",
"def choose(n, c):\n",
" \"Number of ways to choose c items from a list of n items.\"\n",
" return factorial(n) // (factorial(n - c) * factorial(c))"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"100947"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"choose(23, 6)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Now we're ready to answer the 4 problems: \n",
"\n",
"### Urn Problem 1: what's the probability of selecting 6 red balls? "
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(4, 4807)"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"red6 = {s for s in U6 if s.count('R') == 6}\n",
"\n",
"P(red6, U6)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Let's investigate a bit more. How many ways of getting 6 red balls are there?"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"84"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(red6)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Why are there 84 ways? Because there are 9 red balls in the urn, and we are asking how many ways we can choose 6 of them:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"84"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"choose(9, 6)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"So the probabilty of 6 red balls is then just 9 choose 6 divided by the size of the sample space:"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P(red6, U6) == Fraction(choose(9, 6), \n",
" len(U6))"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"### Urn Problem 2: what is the probability of 3 blue, 2 white, and 1 red?"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(240, 4807)"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"b3w2r1 = {s for s in U6 if\n",
" s.count('B') == 3 and s.count('W') == 2 and s.count('R') == 1}\n",
"\n",
"P(b3w2r1, U6)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"We can get the same answer by counting how many ways we can choose 3 out of 6 blues, 2 out of 8 whites, and 1 out of 9 reds, and dividing by the number of possible selections:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P(b3w2r1, U6) == Fraction(choose(6, 3) * choose(8, 2) * choose(9, 1), \n",
" len(U6))"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Here we don't need to divide by any factorials, because `choose` has already accounted for that. \n",
"\n",
"We can get the same answer by figuring: \"there are 6 ways to pick the first blue, 5 ways to pick the second blue, and 4 ways to pick the third; then 8 ways to pick the first white and 7 to pick the second; then 9 ways to pick a red. But the order `'B1, B2, B3'` should count as the same as `'B2, B3, B1'` and all the other orderings; so divide by 3! to account for the permutations of blues, by 2! to account for the permutations of whites, and by 100947 to get a probability:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
" P(b3w2r1, U6) == Fraction((6 * 5 * 4) * (8 * 7) * 9, \n",
" factorial(3) * factorial(2) * len(U6))"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"### Urn Problem 3: What is the probability of exactly 4 white balls?\n",
"\n",
"We can interpret this as choosing 4 out of the 8 white balls, and 2 out of the 15 non-white balls. Then we can solve it the same three ways:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(350, 4807)"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"w4 = {s for s in U6 if\n",
" s.count('W') == 4}\n",
"\n",
"P(w4, U6)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P(w4, U6) == Fraction(choose(8, 4) * choose(15, 2),\n",
" len(U6))"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P(w4, U6) == Fraction((8 * 7 * 6 * 5) * (15 * 14),\n",
" factorial(4) * factorial(2) * len(U6))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Bonus: Let's revisit our strangely colored fruit example."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['ra', 'ra', 'ro', 'ro', 'ro', 'ro', 'ro', 'ro', 'bo', 'ba', 'ba', 'ba']"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# r=red bin; b=blue bin; o=orange; a=apple.\n",
"urn = ['ra']*2 + ['ro']*6 + ['bo'] + ['ba']*3\n",
"urn"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [],
"source": [
"def make_k(item, k):\n",
" \"Create a set of k instances of item, numbered accordingly.\"\n",
" return {item + i for i in k}\n",
" #return {a + b \n",
" # for a in A for b in B}"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'ra1', 'ra2'}"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"make_k('ra', '12')"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [],
"source": [
"urn = make_k('ra', '12') | make_k('ro', '123456') | make_k('bo', '1') | make_k('ba', '123')"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'ba1',\n",
" 'ba2',\n",
" 'ba3',\n",
" 'bo1',\n",
" 'ra1',\n",
" 'ra2',\n",
" 'ro1',\n",
" 'ro2',\n",
" 'ro3',\n",
" 'ro4',\n",
" 'ro5',\n",
" 'ro6'}"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"urn"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"p(fruit=apple, bin=red) = ?"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a_and_r = {f for f in urn if 'ra' in f}\n",
"len(a_and_r)"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(1, 6)"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P(a_and_r, urn)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"# Revised Version of P, with more general events\n",
"To calculate the probability of an even die roll, I originally said\n",
"\n",
"even = {2, 4, 6}\n",
"\n",
"But that's inelegant—I had to explicitly enumerate all the even numbers from one to six. If I ever wanted to deal with a twelve or twenty-sided die, I would have to go back and change even. I would prefer to define even once and for all like this:"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [],
"source": [
"def even(n): return n % 2 == 0"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Now in order to make `P(even, D)` work, I'll have to modify `P` to accept an event as either\n",
"a *set* of outcomes (as before), or a *predicate* over outcomes—a function that returns true for an outcome that is in the event:"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [],
"source": [
"def P(event, space): \n",
" \"\"\"The probability of an event, given a sample space of equiprobable outcomes.\n",
" event can be either a set of outcomes, or a predicate (true for outcomes in the event).\"\"\"\n",
" if is_predicate(event):\n",
" event = such_that(event, space)\n",
" return Fraction(len(event & space), len(space))\n",
"\n",
"is_predicate = callable\n",
"\n",
"def such_that(predicate, collection): \n",
" \"The subset of elements in the collection for which the predicate is true.\"\n",
" return {e for e in collection if predicate(e)}"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Here we see how `such_that`, the new `even` predicate, and the new `P` work:"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"{2, 4, 6}"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"such_that(even, D)"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(1, 2)"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P(even, D)"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"{2, 4, 6, 8, 10, 12}"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"D12 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}\n",
"\n",
"such_that(even, D12)"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(1, 2)"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P(even, D12)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Note: `such_that` is just like the built-in function `filter`, except `such_that` returns a set.\n",
"\n",
"We can now define more interesting events using predicates; for example we can determine the probability that the sum of a three-dice roll is prime (using a definition of `is_prime` that is efficient enough for small `n`):"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(73, 216)"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"D3 = {(d1, d2, d3) for d1 in D for d2 in D for d3 in D}\n",
"\n",
"def prime_sum(outcome): return is_prime(sum(outcome))\n",
"\n",
"def is_prime(n): return n > 1 and not any(n % i == 0 for i in range(2, n))\n",
"\n",
"P(prime_sum, D3)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"# Birthday Paradox\n",
"\n",
"How many people do you think it takes before it is more likely than not that someone shares a birthday?\n",
"\n",
"How to work this out? Turns out it's easier (as it is often is!) to figure out the complement; i.e., that no two people share the same birthday, and then subtract this from 1.\n",
"\n",
"$p$ that person one has unique birthday is $\\frac{365}{365} = 1$\n",
"\n",
"Second person is $\\frac{364}{365}$ (can pick any of the other 364 days). This is a conditional probability; we can simply multiply: $\\frac{365}{365} \\cdot \\frac{364}{365}$. Then the third person? If we multiply these out (up to some $n$ number of people), we have the probability that no one shares a birthday. "
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [],
"source": [
"def shared_birthday_p(n):\n",
" cond_p = 1\n",
" for i in range(n-1):\n",
" cond_p = cond_p * (365-(i+1))/365\n",
" return 1-cond_p"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.5072972343239855"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"shared_birthday_p(23)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"# Conclusion\n",
"\n",
"\n",
"The Count
1972—\n",
"\n",
"The conclusion is: be explicit about what the problem says, and then methodical about defining the sample space, and finally be careful in counting the number of outcomes in the numerator and denominator. Easy as 1-2-3. "
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 1
}