Created
July 28, 2016 03:56
-
-
Save dannygoldstein/93e8cf4a5658eda70004d2da02e23fcd to your computer and use it in GitHub Desktop.
cs70 4a 2.4 solution
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
{ | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"### CS70 Worksheet 4A Problem 2.4" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"You have $k$ balls and $n$ bins labelled 1,2,...,$n$ where $n \\geq 2$. You drop each ball uniformly at random into the bins.\n", | |
"\n", | |
"What is the probability that bin 1 is empty and bin $n$ is non empty?" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"Solution: \n", | |
"\n", | |
"Define the random variable $B_i$ to be 1 when bin $i$ is not empty and 0 when bin $i$ is empty. Using the definition of the law of total probability:\n", | |
"\n", | |
"$$\n", | |
"\\mathrm{Pr}[B_1] = \\sum_{B_n} \\mathrm{Pr}[B_1|B_n]\\mathrm{Pr}[B_n]\n", | |
"$$\n", | |
"\n", | |
"Now we'll use the definition of conditional probability $\\mathrm{Pr}[B_1|B_n]\\mathrm{Pr}[B_n] = \\mathrm{Pr}[B_1\\cap B_n]$ to rewrite the summand:\n", | |
"\n", | |
"$$\n", | |
"\\mathrm{Pr}[B_1] = \\sum_{B_n} \\mathrm{Pr}[B_1\\cap B_n]\n", | |
"$$\n", | |
"\n", | |
"The sum can be expanded as:\n", | |
"\n", | |
"$$\n", | |
"\\mathrm{Pr}[B_1] = \\mathrm{Pr}[B_1\\cap (B_n=1)] + \\mathrm{Pr}[B_1\\cap (B_n=0)]\n", | |
"$$\n", | |
"\n", | |
"We're interested in an event in which $B_1=0$ so we will substitute that in for $B_1$:\n", | |
"\n", | |
"$$\n", | |
"\\mathrm{Pr}[B_1=0] = \\mathrm{Pr}[(B_1=0)\\cap (B_n=1)] + \\mathrm{Pr}[(B_1=0)\\cap (B_n=0)]\n", | |
"$$\n", | |
"\n", | |
"Rearranging the above equation we get:\n", | |
"\n", | |
"$$\n", | |
"\\mathrm{Pr}[(B_1=0)\\cap (B_n=1)] =\\mathrm{Pr}[B_1=0] - \\mathrm{Pr}[(B_1=0)\\cap (B_n=0)]\n", | |
"$$\n", | |
"\n", | |
"From the previous parts of this problem we know\n", | |
"\n", | |
"$$\n", | |
"\\mathrm{Pr}[(B_1=0)\\cap (B_n=0)] = \\left(\\frac{n-2}{n}\\right)^k\n", | |
"$$\n", | |
"\n", | |
"and\n", | |
"\n", | |
"$$\n", | |
"\\mathrm{Pr}[(B_1=0)] = \\left(\\frac{n-1}{n}\\right)^k\n", | |
"$$\n", | |
"\n", | |
"so\n", | |
"\n", | |
"$$\n", | |
"\\mathrm{Pr}[(B_1=0)\\cap (B_n=1)] =\\left(\\frac{n-1}{n}\\right)^k - \\left(\\frac{n-2}{n}\\right)^k\n", | |
"$$" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": null, | |
"metadata": { | |
"collapsed": true | |
}, | |
"outputs": [], | |
"source": [] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 2", | |
"language": "python", | |
"name": "python2" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 2 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython2", | |
"version": "2.7.12" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 0 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment