% 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{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}
\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}{\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{\N}{\mathbb{N}}
\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}}

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\definecolor{shadecolor}{gray}{0.95}

\setlength{\parindent}{0pt}

\pagestyle{fancy}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

% begin the document
\begin{document}

% actually insert the title.
\maketitle
  
\begin{enumerate}
% 1
\item Understanding the \emph{process} that leads to different random variables is a great way to gain familiarity for what they mean. For each random variable, write a function that simulates its generation process. Your function should return a number. The only probability function that you may use when coding your solution is \code{random()}: a function that returns a uniform random in the range [0, 1]. Submit your code (either Python or psuedocode). We include a solution to (a):
\begin{enumerate}[label=\alph*.]

    \item $X \sim \Ber(p = 0.4)$ \\
    1 or 0 to indicate whether or not an underlying event was ``successful."
    
\begin{framed}
\begin{minted}[breaklines]{python}
def simulateBernoulli(p = 0.4):
   if random() < p: 
      return 1
   return 0
\end{minted}
\end{framed}

    \item $X \sim \Bin(n = 20, p = 0.4)$ \\
    The number of successes after 20 independent experiments.

    \item $X \sim \Geo(p = 0.03)$ \\
    The number of trials until the first success.

    \item $X \sim \NegBin(r = 5, p = 0.03)$ \\
    The number of trials until $5$ successes.
    
    \item $X \sim \Poi(\lambda = 3.1)$ \emph{  approximate} \\  The number of events in a minute, where the historical rate is 3.1 events per min.\\ \emph{Hint: } Break the minute down into 60,000 ms events like we did in lecture. 
    
    \item  $X \sim \Exp(\lambda = 3.1)$ \emph{  approximate}\\ The amount of time until the next event, where the historical rate is 3.1 events per min. \emph{Hint: } Like part (e), think of an event for each millisecond.

    \end{enumerate}
    
If you are trying to understand probability mass functions, you may optionally try to visualize one via your simulations. For extra credit, run one of your simulations 100,000 times and plot a histogram of return values.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    \newpage


% 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 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


% 5
\item Scores on the SAT maths (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


% 6
\item You are testing software and discover that your program has a non-deterministic bug that causes catastrophic failure (aka a ``hindenbug"). Your program was tested for 400 hours and the bug occurred \textbf{twice}.

\begin{enumerate}[label=\alph*.]
\item Each user uses your program to complete a three hour long task. If the hindenbug manifests they will immediately stop their work. What is the probability that the bug manifests for a given user?

\item Your program is used by one million users. Use a normal approximation to estimate the probability that more than 10,000 users experience the bug. Use your answer from part (a).
\end{enumerate}

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    \newpage


% 7
\item Say we have a cable of length $n$.  We select a point (chosen uniformly randomly) along the cable, at which we cut the cable into two pieces.  What is the probability that the shorter of the two pieces of the cable is less than 1/3 the size of the longer of the two pieces?  Explain formally how you derived your answer.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    \newpage


% 8
\item \textbf{[Coding]} Below are two sequences of 300 ``coin flips'' (H for heads, T for tails). One of these is a true sequence of 300 independent flips of a fair coin. The other was generated by a person typing out H's and T's and trying to \emph{seem} random. Which sequence is truly composed of coin flips?

We'll save you a bit of time by telling you that both sequences have 148 heads, two less than the expected number for a 0.5 probability of heads. It won't be as simple as finding out which one is closer to half heads! Make an argument that is justified with probabilities calculated on the sequences. This problem is solvable without code, but it would require some tedious counting. You're encouraged to put your computer to good use by looking at these sequences in the accompanying \texttt{pset3.zip}.


Sequence 1:
\begin{verbatim}
TTHHTHTTHTTTHTTTHTTTHTTHTHHTHHTHTHHTTTHHTHTHTTHTHH
TTHTHHTHTTTHHTTHHTTHHHTHHTHTTHTHTTHHTHHHTTHTHTTTHH
TTHTHTHTHTHTTHTHTHHHTTHTHTHHTHHHTHTHTTHTTHHTHTHTHT
THHTTHTHTTHHHTHTHTHTTHTTHHTTHTHHTHHHTTHHTHTTHTHTHT
HTHTHTHHHTHTHTHTHHTHHTHTHTTHTTTHHTHTTTHTHHTHHHHTTT
HHTHTHTHTHHHTTHHTHTTTHTHHTHTHTHHTHTTHTTHTHHTHTHTTT
\end{verbatim}

Sequence 2:
\begin{verbatim}
HTHHHTHTTHHTTTTTTTTHHHTTTHHTTTTHHTTHHHTTHTHTTTTTTH
THTTTTHHHHTHTHTTHTTTHTTHTTTTHTHHTHHHHTTTTTHHHHTHHH
TTTTHTHTTHHHHTHHHHHHHHTTHHTHHTHHHHHHHTTHTHTTTHHTTT
THTHHTTHTTHTHTHTTHHHHHTTHTTTHTHTHHTTTTHTTTTTHHTHTH
HHHTTTTHTHHHTHHTHTHTHTHHHTHTTHHHTHHHHHHTHHHTHTTTHH
HTTTHHTHTTHHTHHHTHTTHTTHTTTHHTHTHTTTTHTHTHTTHTHTHT
\end{verbatim}

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    \newpage


% 9
\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


% 10
\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


% 11
\item This 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 code:
% 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


% 12
\item \textbf{[Coding]} Let's say you operate a helicopter commuting business with once-a-day flights each way between Oakland and Palo Alto. You notice that not all of your paid-up passengers show up for their flights. So you may be able to get away with selling more tickets than there are seats. In this problem, you will determine how much you should overbook your flights to maximize your revenue.

Your helicopter has 6 passenger seats and you sell tickets for \$195 each. Your data tell you that the demand for tickets for each flight is a Poisson random variable with expectation of 7.5. You also assume that each paid-up passenger will show up on time independently with probability 65\%. If a passenger does not show up on time, you get to keep the \$195 fare. On the other hand, if more than 6 passengers show up for a flight, you compensate the ones who don't get to fly with \$950 each (which includes a refund of the fare).

Write a program to determine the number of tickets $n$ you should offer for sale for each flight in order to maximize your expected revenue, where revenue is ticket sales minus compensation for overbooking. (Notice that if you offer $n$ tickets for sale but the demand turns out to be less than $n$, then you are left with unsold tickets. If the demand turns out to be greater than $n$, some potential customers do not get to purchase tickets.)


Your program should simulate the value of revenue for at least 100,000 trials for each value of $n$. Plot expected revenue vs. $n$ (for $6 \leq n \leq 15$) and report the optimal $n$.

This problem was inspired by \url{https://blade.flyblade.com/p/san-francisco-bay-area}.

\textbf{Python tips: }We recommend that you use NumPy library functions such as \texttt{numpy.minimum()}, \texttt{numpy.random.poisson()} (or SciPy's \texttt{scipy.stats.poisson()}, etc.

If your Python code uses nested loops (one for $n$ and one for the trials), your simulation may take minutes to complete. If you have a loop for $n$ and use vectorized operations instead of the other loop, your simulation may finish in seconds (or even less than a second). In this problem, a vectorized solution means that most lines of code will operate on arrays of size 100,000. That is, for each value of $n$ the program processes all 100,000 trials together. 

We will accept vectorized or non-vectorized programs for full credit. While the speed-up may not make a difference here, vectorization will be more important when you train ML models later in the semester. More info: \url{https://realpython.com/numpy-array-programming}

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    \newpage



\end{enumerate}


\end{document}
  