% This template was designed by Victor Lin (victorlin@cs.stanford.edu) with edits by Lisa Yan. % You should compile this with PDFLaTeX (default), not XeLaTeX. % This is a comment! % This is the document declaration \documentclass[12pt]{article} % these are some useful packages. these add functionality to your document \usepackage{newtxtext} % sets font \usepackage{amssymb} \usepackage{amsthm} \usepackage{amssymb} \usepackage{mathdots} \usepackage[pdftex]{graphicx} \usepackage{fancyhdr} %\usepackage[margin=1in]{geometry} \usepackage{multicol} \usepackage{bm} \usepackage{listings} \PassOptionsToPackage{usenames,dvipsnames}{color} %% Allow color names \usepackage{pdfpages} \usepackage{algpseudocode} \usepackage{tikz} \usepackage{enumitem} \usepackage[T1]{fontenc} \usepackage{inconsolata} \usepackage{framed} \usepackage[thinlines]{easytable} \usepackage{minted} \def\code#1{\texttt{#1}} % add some code in-line \usepackage{mdframed} \usepackage{colortbl} \usepackage{makecell} \usepackage{amsmath} % math symbols \usepackage{wrapfig} % in case you want to use a figure \usepackage{hyperref} % add hyper links % This package controls the margins of the page. \usepackage[top=1in, bottom=1in, left=0.8in, right=1in]{geometry} \usepackage{multicol} % in case you want to use multiple columns \setlength{\columnsep}{0.1pc} % document headers! \title{CS 109: Probability for Computer Scientists\\Problem Set\#3} \author{author} % Change this to your name! \date{\today} % today does the right thing \lhead{author} \chead{Problem Set \#3} \rhead{\today} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\absfit}[1]{\left\lvert #1 \right\rvert} \newcommand{\norm}[1]{\left\lVert #1 \right\rVert} \newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}} \renewcommand{\(}{\left(} \renewcommand{\)}{\right)} \newcommand{\floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{\ceil}[1]{\left\lceil#1\right\rceil} \newcommand{\pd}[1]{\frac{\partial}{\partial #1}} \newcommand{\inner}[1]{\langle#1\rangle} \newcommand{\cond}{\bigg|} \newcommand{\rank}[1]{\mathbf{rank}(#1)} \newcommand{\range}[1]{\mathbf{range}(#1)} \newcommand{\nullsp}[1]{\mathbf{null}(#1)} \newcommand{\repr}[1]{\left\langle#1\right\rangle} \DeclareMathOperator{\Var}{Var} \newcommand{\SD}{\operatorname{SD}} \newcommand{\Cov}{\operatorname{Cov}} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\Tr}{\mathbf{Tr}} \DeclareMathOperator{\diag}{\mathbf{diag}} \DeclareMathOperator{\dist}{\mathbf{dist}} \DeclareMathOperator{\prob}{\mathbf{prob}} \DeclareMathOperator{\dom}{\mathbf{dom}} \DeclareMathOperator{\E}{\mathbf{E}} \DeclareMathOperator{\R}{\mathbb{R}} \DeclareMathOperator{\var}{\mathbf{var}} \DeclareMathOperator{\quartile}{\mathbf{quartile}} \DeclareMathOperator{\conv}{\mathbf{conv}} \DeclareMathOperator{\VC}{VC} \DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \newcommand{\Uni}{\operatorname{Uni}} \newcommand{\Ber}{\operatorname{Ber}} \newcommand{\Bin}{\operatorname{Bin}} \newcommand{\Geo}{\operatorname{Geo}} \newcommand{\NegBin}{\operatorname{NegBin}} \newcommand{\Zipf}{\operatorname{Zipf}} \newcommand{\HypG}{\operatorname{HypG}} \newcommand{\Poi}{\operatorname{Poi}} \newcommand{\Beta}{\operatorname{Beta}} \newcommand{\Normal}{\operatorname{\mathcal{N}}} \newcommand{\N}{\operatorname{\mathcal{N}}} \newcommand{\Exp}{\operatorname{Exp}} \DeclareMathOperator{\NP}{\mathbf{NP}} \DeclareMathOperator{\coNP}{\mathbf{coNP}} \DeclareMathOperator{\TIME}{\mathsf{TIME}} \DeclareMathOperator{\polytime}{\mathbf{P}} \DeclareMathOperator{\PH}{\mathbf{PH}} \DeclareMathOperator{\SIZE}{\mathbf{SIZE}} \DeclareMathOperator{\ATIME}{\mathbf{ATIME}} \DeclareMathOperator{\SPACE}{\mathbf{SPACE}} \DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}} \DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}} \DeclareMathOperator{\Z}{\mathbb{Z}} \DeclareMathOperator{\EXP}{\mathbf{EXP}} \DeclareMathOperator{\NEXP}{\mathbf{NEXP}} \DeclareMathOperator{\NTIME}{\mathbf{NTIME}} \DeclareMathOperator{\DTIME}{\mathbf{DTIME}} \DeclareMathOperator{\poly}{poly} \DeclareMathOperator{\BPP}{\mathbf{BPP}} \DeclareMathOperator{\ZPP}{\mathbf{ZPP}} \DeclareMathOperator{\RP}{\mathbf{RP}} \DeclareMathOperator{\coRP}{\mathbf{coRP}} \DeclareMathOperator{\BPL}{\mathbf{BPL}} \DeclareMathOperator{\IP}{\mathbf{IP}} \DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}} \DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}} \DeclareMathOperator{\SAT}{\mathsf{SAT}} \DeclareMathOperator{\NL}{\mathbf{NL}} \DeclareMathOperator{\PCP}{\mathbf{PCP}} \DeclareMathOperator{\PP}{\mathbf{PP}} \DeclareMathOperator{\cost}{cost} \let\Pr\relax \DeclareMathOperator*{\Pr}{\mathbf{Pr}} \usepackage{booktabs} \usepackage{diagbox} % configure display of tables \newcommand{\ra}[1]{\renewcommand{\arraystretch}{#1}} \newcommand\tab[1][1cm]{\hspace*{#1}} \newcommand\tabhead[1]{\small\textbf{#1}} \theoremstyle{definition} \newtheorem*{answer}{Answer} \definecolor{shadecolor}{gray}{0.95} \setlength{\parindent}{0pt} \pagestyle{fancy} \setlength{\headheight}{15pt} \renewcommand{\thefootnote}{\fnsymbol{footnote}} % begin the document \begin{document} % actually insert the title. \maketitle \begin{enumerate} % 1 \item Do not paste your code here. Submit your completed .py file on Gradescope under ``PSet 3 - Coding''. % 2 \item Lyft line gets 2 requests every 5 minutes, on average, for a particular route. A user requests the route and Lyft commits a car to take her. All users who request the route in the next five minutes will be added to the car as long as the car has space. The car can fit up to three users. Lyft will make \$6 for each user in the car (the revenue) minus \$7 (the operating cost). \begin{enumerate}[label=\alph*.] \item How much does Lyft expect to make from this trip? \item Lyft has one space left in the car and wants to wait to get another user. What is the probability that another user will make a request in the next 30 seconds? \end{enumerate} \begin{shaded} \begin{answer} \end{answer} \end{shaded} \newpage % 3 \item Suppose it takes at least 9 votes from a 12-member jury to convict a defendant. Suppose also that the probability that a juror votes that an actually guilty person is innocent is 0.25, whereas the probability that the juror votes that an actually innocent person is guilty is 0.15. If each juror acts independently and if 70\% of defendants are actually guilty, find the probability that the jury renders a correct decision. Also determine the percentage of defendants found guilty by the jury. \begin{shaded} \begin{answer} \end{answer} \end{shaded} \newpage % 4 \item To determine whether they have measles, 60 people have their blood tested. However, rather than testing each individual separately, it is decided to first place the people into groups of 6. The blood samples of the 6 people in each group will be pooled and analyzed together. If the test is negative, one test will suffice for the 6 people, whereas if the test is positive, each of the 6 people will also be individually tested and, in all, 7 tests will be made on this group. Note that we assume that the pooled test will be positive if at least one person in the pool has measles. Assume that the probability that a person has measles is 5\% for all people, independently of each other, and compute the expected number of tests necessary for each group of 6 people. \begin{shaded} \begin{answer} \end{answer} \end{shaded} \newpage % 5 \item An urn contains 4 white balls and 4 black balls. Two balls are drawn randomly (without replacement) from the urn. If they are the same color, you win \$2.00. If they are different colors, you lose \$1.00 (i.e., you win -\$1.00). Let $X$ = the amount you win. \begin{enumerate}[label=\alph*.] \item What is $E[X]$? \item What is $\Var(X)$? \end{enumerate} \begin{shaded} \begin{answer} \end{answer} \end{shaded} \newpage % 6 \item Let $X$ be a continuous random variable with probability density function: \[f(x) = \left\{ \begin{matrix} c(2 - 2x^2) & -1 < x < 1 \\ 0 & \text{otherwise} \end{matrix}\right.\] \begin{enumerate}[label=\alph*.] \item What is the value of $c$? \item What is the cumulative distribution function (CDF) of $X$? \item What is $E[X]$? \end{enumerate} \begin{shaded} \begin{answer} \end{answer} \end{shaded} \newpage % 7 \item Scores on the SAT math (out of 800) are normally distributed with a mean of 500 and a standard deviation of 100. \begin{enumerate}[label=\alph*.] \item What fraction of students receive a score within 1.5 standard deviations of the mean? \item Irina scores 750. What percent of students scored lower than 750? (Irina's percentile) \end{enumerate} \begin{shaded} \begin{answer} \end{answer} \end{shaded} \newpage % 8 \item The number of times a person's computer crashes in a month is a Poisson random variable with $\lambda = 7$. Suppose that a new operating system patch is released that reduces the Poisson parameter to $\lambda = 2$ for 80\% of computers, and for the other 20\% of computers the patch has no effect on the rate of crashes. If a person installs the patch, and has their computer crash 4 times in the month thereafter, how likely is it that the patch has had an effect on the user's computer (i.e., it is one of the 80\% of computers that the patch reduces crashes on)? \begin{shaded} \begin{answer} \end{answer} \end{shaded} \newpage % 9 \item Consider a hash table with $n$ buckets. Now, $m$ strings are hashed into the table (with equal probability of being hashed into any bucket). \begin{enumerate}[label=\alph*.] \item Let $n = {}$2,000 and $m = {}$10,000. What is the (Poisson approximated) probability that the first bucket has 0 strings hashed to it? \item Let $n = {}$2,000 and $m = {}$10,000. What is the (Poisson approximated) probability that the first bucket has 8 or fewer strings hashed to it? \item Let $m = {}$10,000. What is largest integer value $n$ such the Poisson approximated probability that an arbitrary bucket in the hash table will have no strings hashed to it is less than 0.5 (= 50\%)? \item Let X be a Poisson random variable with parameter $\lambda$, that is: $X \sim \Poi(\lambda)$. What value of $\lambda$ maximizes $P(X = 3)$? Show formally (mathematically) how you derived this result. (Hint: at some point in your derivation you should be differentiating with respect to $\lambda$.) \end{enumerate} (Questions such as this allow us to compute appropriate sizes for hash tables in order to get good performance with high probability in applications where we have a ballpark idea of the number of elements that will be hashed into the table.) \begin{shaded} \begin{answer} \end{answer} \end{shaded} \newpage % 10 \item Say there are $k$ buckets in a hash table. Each new string added to the table is hashed to bucket $i$ with probability $p_i$, where $\sum_{i=1}^k p_i = 1$. If $n$ strings are hashed into the table, find the expected number of buckets that have at least one string hashed to them. (Hint: Let $X_i$ be a binary variable that has the value 1 when there is at least one string hashed to bucket $i$ after the $n$ strings are added to the table (and 0 otherwise). Compute $E\left[\sum_{i=1}^k X_i\right]$.) \begin{shaded} \begin{answer} \end{answer} \end{shaded} \newpage % 11 \item A Bloom filter is a probabilistic implementation of the \emph{set} data structure, an unordered collection of unique objects. In this problem we are going to look at it theoretically. Our Bloom filter uses 3 different independent hash functions $H_1$, $H_2$, $H_3$ that each take any string as input and each return an index into a bit-array of length n. Each index is equally likely for each hash function. To add a string into the set, feed it to each of the 3 hash functions to get 3 array positions. Set the bits at all these positions to 1. For example, initially all values in the bit-array are zero. In this example $n = 10$: \begin{center} \begin{tabular}{l cccccccccc} Index: & \multicolumn{10}{l}{\begin{tabular}{cccccccccc} \ 0 \ & \ 1 \ & \ \ 2 \ & \ 3 \ & \ 4 \ & \ 5 \ & \ 6 \ & \ 7 \ & \ 8 \ & \ 9 \ \end{tabular}} \\ Value: & \multicolumn{10}{l}{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|} \hline \ 0 \ & \ 0 \ & \ 0 \ & \ 0 \ & \ 0 \ & \ 0 \ & \ 0 \ & \ 0 \ & \ 0 \ & \ 0 \ \\ \hline \end{tabular}} \end{tabular} \end{center} After adding a string ``pie'', where $H_1$(``pie'') = 4, $H_2$(``pie'') = 7, and $H_3$(``pie'') = 8: \begin{center} \begin{tabular}{l cccccccccc} Index: & \multicolumn{10}{l}{\begin{tabular}{cccccccccc} \ 0 \ & \ 1 \ & \ \ 2 \ & \ 3 \ & \ 4 \ & \ 5 \ & \ 6 \ & \ 7 \ & \ 8 \ & \ 9 \ \end{tabular}} \\ Value: & \multicolumn{10}{l}{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|} \hline \ 0 \ & \ 0 \ & \ 0 \ & \ 0 \ & \ \textbf{1} \ & \ 0 \ & \ 0 \ & \ \textbf{1} \ & \ \textbf{1} \ & \ 0 \ \\ \hline \end{tabular}} \end{tabular} \end{center} Bits are never switched back to 0. Consider a Bloom filter with $n = 9,000$ buckets. You have added $m = {}$1,000 strings to the Bloom filter. Provide a \textbf{numerical answer} for all questions. \begin{enumerate}[label=\alph*.] \item What is the (approximated) probability that the first bucket has 0 strings hashed to it? \end{enumerate} To \emph{check} whether a string is in the set, feed it to each of the 3 hash functions to get 3 array positions. If any of the bits at these positions is 0, the element is not in the set. If all bits at these positions are 1, the string \emph{may} be in the set; but it could be that those bits are 1 because some of the other strings hashed to the same values. You may assume that the value of one bucket is independent of the value of all others. \begin{enumerate}[label=\alph*.] \setcounter{enumii}{1} \item What is the probability that a string which has \emph{not} previously been added to the set will be misidentified as in the set? That is, what is the probability that the bits at all of its hash positions are already 1? Use approximations where appropriate. \item Our Bloom filter uses three hash functions. Was that necessary? Repeat your calculation in (b) assuming that we only use a single hash function (not 3). \end{enumerate} (Chrome uses a Bloom filter to keep track of malicious URLs. Questions such as this allow us to compute appropriate sizes for hash tables in order to get good performance with high probability in applications where we have a ballpark idea of the number of elements that will be hashed into the table.) \begin{shaded} \begin{answer} \end{answer} \end{shaded} \newpage % 12 \item Last summer (May 2019) the concentration of CO$_2$ in the atmosphere was 414 parts per million (ppm) which is substantially higher than the pre-industrial concentration: 275 ppm. CO$_2$ is a greenhouse gas and as such increased CO$_2$ corresponds to a warmer planet. Absent some pretty significant policy changes, we will reach a point within the next 50 years (i.e., well within your lifetime) where the CO$_2$ in the atmosphere will be double the pre-industrial level. In this problem we are going to explore the following question: What will happen to the global temperature if atmospheric CO$_2$ doubles? The measure, in degrees Celsius, of how much the global average surface temperature will change (at the point of equilibrium) after a doubling of atmospheric CO$_2$ is called ``Climate Sensitivity.'' Since the earth is a complicated ecosystem climate scientists model Climate Sensitivity as a random variable, $S$. The IPPC Fourth Assessment Report had a summary of 10 scientific studies that estimated the PDF of $S$: % to include this image with your submission: % 1) download the website image: http://web.stanford.edu/class/cs109/img/psets/pset3b.png % 2) save the image to the same folder as this file (e.g., upload to overleaf) % 3) in the below \includegraphics command, % replace climateSensitivity.png with pset3b.png % otherwise just comment out everything from \begin{figure} to \end{figure}. \begin{figure}[h] \centering \includegraphics[width=0.8\textwidth]{images/climateSensitivity.png} \end{figure} In this problem we are going to treat $S$ as part-discrete and part-continuous. For values of $S$ less than 7.5, we are going to model sensitivity as a discrete random variable with PMF based on the average of estimates from the studies in the IPCC report. Here is the PMF for $S$ in the range 0 through 7.5: \begin{center} \begin{tabular}{l cccccccccc} Sensitivity, $S$ (degrees C) & \ 0 \ & \ 1 \ & \ \ 2 \ & \ 3 \ & \ 4 \ & \ 5 \ & \ 6 \ & \ 7 \\ Expert Probability & \ 0.00 \ & \ 0.11 \ & \ \ 0.26 \ & \ 0.22 \ & \ 0.16 \ & \ 0.09 \ & \ 0.06 \ & \ 0.04 \\ \end{tabular} \end{center} The IPCC fifth assessment report notes that there is a non-negligible chance of S being greater than 7.5 degrees but didn't go into detail about probabilities. In the paper ``Fat-Tailed Uncertainty in the Economics of Catastrophic Climate Change" Martin Weitzman discusses how different models for the PDF of Climate Sensitivity (S) for large values of S have wildly different policy implications. For values of S greater than or equal to 7.5 degrees Celsius, we are going to model S as a continuous random variable. Consider two different assumptions for S when it is at least 7.5 degrees Celsius: a fat tailed distribution ($f_1$) and a thin tailed distribution ($f_2$): \begin{equation*} f_1(x) = \frac{K}{x} \text{ s.t. } 7.5 \leq x < 30 \end{equation*} \begin{equation*} f_2(x) = \frac{K}{x^3} \text{ s.t. } 7.5 \leq x < 30 \end{equation*} For this problem assume that the probability that $S$ is greater than 30 degrees Celsius is 0. \begin{enumerate}[label=\alph*.] \item Compute the probability that Climate Sensitivity is at least 7.5 degrees Celsius. \item Calculate the value of $K$ for both $f_1$ and $f_2$. \item It is estimated that if temperatures rise more than 10 degrees Celsius, all the ice on Greenland will melt. Estimate the probability that S is greater than 10 under both the $f_1$ and $f_2$ assumptions. \item Calculate the expectation of S under both the $f_1$ and $f_2$ assumptions. \item Let $R = S^2$ be a crude approximation of the cost to society that results from $S$. Calculate $E[R]$ under both the $f_1$ and $f_2$ assumptions. \end{enumerate} Notes: (1) Both $f_1$ and $f_2$ are ``power law distributions''. (2) Calculating expectations for a variable that is part discrete and part continuous is as simple as: use the discrete formula for the discrete part and the continuous formula for the continuous part. \begin{shaded} \begin{answer} \end{answer} \end{shaded} \newpage \end{enumerate} \end{document}