% 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\#5}
\author{author} % Change this to your name!
\date{\today} % today does the right thing

\lhead{author}
\chead{Problem Set \#5}
\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 You go on a camping trip with two friends who each have a mobile phone.  Since you are out in the wilderness, mobile phone reception isn't very good.  One friend's phone will independently drop calls with 10\% probability.  Your other friend's phone will independently drop calls with 25\% probability.  Say you need to make 6 phone calls, so you randomly choose one of the two phones and you will use that \emph{same} phone to make all your calls (but you don't know which has a 10\% versus 25\% chance of dropping calls).  Of the first 3 (out of 6) calls you make, one of them is dropped.  What is the conditional expected number of dropped calls in the 6 total calls you make (conditioned on having already had one of the first three calls dropped)?

    \begin{shaded}
    \begin{answer}

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


% 2
\item You are developing medicine that sometimes has a desired effect, and sometimes does not. With FDA approval, you are allowed to test your medicine on 9 patients. You observe that 7 have the desired outcome. Your belief as to the probability of the medicine having an effect before running any experiments was $\Beta(2, 2)$.

    \begin{enumerate}[label=\alph*.]

    \item What is the distribution for your belief of the probability of the medicine being effective after the trial?
    \item Use your distribution from (a) to calculate your confidence that the probability of the drug having an effect is greater than 0.5. You may use \texttt{scipy.stats} or an online calculator.

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 3
\item \textbf{[Coding]} Let $X$ be the sum of 100 independent uniform random variables each of which are identically distributed as $\Uni(0, 1)$. Simulate 100,000 calculations of $X$.

    \begin{enumerate}[label=\alph*.]

    \item Use the simulations to calculate the probability that $X$ is in the ranges: [35 to 40], [40 to 45] as so on up until [60 to 65]. Draw a bar graph of your results.
    \item Write the probability density function for an approximation of $X$. 
    \item Use your answer to part (b) to calculate the probability that $X$ is in the range 40 to 45. Make sure that your answer aligns with the result you reported in part (a). Round your result to two decimal places.

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 4
\item A fair 6-sided die is repeatedly rolled until the total sum of all the rolls exceeds 300.  Approximate (using the Central Limit Theorem) the probability that \emph{at least} 80 rolls are necessary to reach a sum that exceeds 300.

    \begin{shaded}
    \begin{answer}

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


% 5
\item Program A will run 20 algorithms in sequence, with the running time for each algorithm being independent random variables with mean = 46 seconds and variance = 100 seconds${}^2$.  Program B will run 20 algorithms in sequence, with the running time for each algorithm being independent random variables with mean = 48 seconds and variance = 200 seconds${}^2$.

    \begin{enumerate}[label=\alph*.]

    \item What is the approximate probability that Program A completes in less than 900 seconds?

    \item What is the approximate probability that Program B completes in less than 900 seconds?

    \item What is the approximate probability that Program A completes in less time than Program B?

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 6
\item \textbf{[Coding]} Stanford's HCI class runs a massive online class that was taken by ten thousand students. The class used peer assessment to evaluate students' work. We are going to use their data to learn more about peer graders. In the class, each student has their work evaluated by 5 peers and every student is asked to evaluate 6 assignments: five peers and the ``control assignment'' (the graders were unaware of which assignment was the control). All 10,000 students evaluated the same control assignment, and the scores they gave are in the file \texttt{peerGrades.csv}. You may use simulations to solve any part of this question.

    \begin{enumerate}[label=\alph*.]

    \item What is the sample mean of the 10,000 grades to the control assignment?
    \item Students could be given a final score which is the \emph{mean} of the 5 grades given by their peers. Imagine the control experiment had only received 5 peer-grades. What is the variance of the mean grade that the control experiment would have been given? Show your work and describe any code you used to calculate your answer.
    \item Students could be given a final score which is the \emph{median} of the 5 grades given by their peers. Suppose the control experiment had only received 5 peer-grades. What is the variance of the median grade that the control experiment would have been given? Show your work and describe any code you used to calculate your answer.
    \item Is the expected median of 5 grades different than the expected mean of 5 grades? 
    \item Would you use the mean or the median of 5 peer grades to assign scores in the online version of Stanford's HCI class? Hint: it might help to visualize the scores.

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 7
\item \textbf{[Coding] }  In this problem you are going to learn how to use and misuse $p$-values for experiments that are called \emph{A/B tests}. These experiments are ubiquitous. They are a staple of both scientific experiments and user interaction design.

Suppose you are working at Coursera on new ways of teaching a concept in probability. You have two different learning activities \texttt{activity1} and \texttt{activity2} and you want to figure out which activity leads to better learning outcomes.

Over a two-week period, you randomly assign each student to be given either \texttt{activity1} or \texttt{activity2}. You then evaluate each student's learning outcomes by asking them to solve a set of problems. The data (the activity shown to each student and their measured learning outcomes) are found in the file \texttt{learningOutcomes.csv}.

    \begin{enumerate}[label=\alph*.]

    \item What is the difference in sample means of learning outcomes between students who were given \texttt{activity1} and students who were given \texttt{activity2}?
    \item Write a program to estimate the $p$-value (using the bootstrap method) for the observed difference in means reported in part (a). In other words: assuming that the learning outcomes for students who had been given \texttt{activity1} and \texttt{activity2} were identically distributed, what is the probability that you could have sampled two groups of students such that you could have observed a difference of means as extreme, or more extreme, than the one calculated from your data in part (a)? Provide any code you used to calculate your answer.

    \end{enumerate}

Scientific journals have traditionally accepted an experiment's result as ``statistically significant'' if the $p$-value is below 0.05. By definition, this standard means that 5\% of findings published in these journals are in fact not true, but just false positives. The scientific community is beginning to move away from using arbitrary $p$-value thresholds to determine whether a result is publishable. For example, see this 2019 editorial in the journal \emph{Nature}:  \url{https://www.nature.com/articles/d41586-019-00874-8}.

You are now troubled by the $p$-value you obtained in part (b), so you decide to delve deeper. You investigate whether learning outcomes differed based on the background experience of students. The file \texttt{background.csv} stores the background of each student as one of three labels: more experience, average experience, less experience.

    \begin{enumerate}[label=\alph*., start=3]

    \item For each of the three backgrounds, calculate a difference in means in learning outcome between \texttt{activity1} and \texttt{activity2}, and the $p$-value of that difference.

    \item Your manager at Coursera is concerned that you have been ``$p$-hacking,'' which is also known as data dredging: \url{https://en.wikipedia.org/wiki/Data_dredging}. In one sentence, explain why your results in part (c) are not the result of $p$-hacking.

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 8
\item You are designing a randomized algorithm that delivers one of two new drugs to patients who come to your clinic---each patient can only receive one of the drugs. Initially you know nothing about the effectiveness of the two drugs. You are simultaneously trying to learn which drug is the best and, at the same time, cure the maximum number of people. To do so we will use the Thompson Sampling Algorithm.

\begin{mdframed}
\textbf{Thompson Sampling Algorithm: }  For \emph{each} drug we maintain a Beta distribution to represent the drug's probability of being successful. Initially we assume that drug $i$ has a probability of success:  $\theta_i \sim \Beta(1, 1)$. 

When choosing which drug to give to the next patient we \textbf{sample} a value from each Beta and select the drug with the largest \textbf{sampled} value. We administer the drug, observe if the patient was cured, and update the Beta that represents our belief about the probability of the drug being successful. Repeat for the next patient.
\end{mdframed}

\begin{enumerate}[label=\alph*.,leftmargin=5mm]
\item Say you try the first drug on 7 patients. It cures 5 patients and has no effect on 2. What is your  belief about the drug's probability of success, $\theta_1$? Your answer should be a Beta.

\begin{table}[H]
  \centering
  \ra{1.3}
  \begin{tabular}{ll}
    \toprule
    
    \tabhead{Method} & \tabhead{Description}\\
    \midrule
    \arrayrulecolor{black!10}
    \texttt{V = sampleBeta(a, b)} & \makecell[l]{Returns a real number value in the range [0, 1] with probability \\defined by a PDF of a Beta with parameters $a$ and $b$.}\\
     \midrule
    \texttt{R = giveDrug(i)} & \makecell[l]{Gives drug $i$ to the next patient. Returns a True if the drug was \\ successful in curing the patient or False if it was not. Throws an \\error if $i \notin \{1, 2\}$.}\\
     \midrule
    \texttt{I = argmax(list)} & Returns the index of the largest value in the list.\\
    \arrayrulecolor{black}
    \bottomrule
  \end{tabular}
  \label{tab:dataTable}
\end{table}

\item Write pseudocode to administer either of the two drugs to 100 patients  using Thompson's Sampling Algorithm. Use functions from the table above. Your code should execute \texttt{giveDrug} 100 times.


\item  After running Thompson Sampling Algorithm 100 times, you end up with the following Beta distributions:\\
\hspace*{.2in}$  \theta_1 \sim \text{Beta}(11, 11)$,\\
\hspace*{.2in}$  \theta_2 \sim \text{Beta}(76, 6)$.\\
What is the expected probability of success for each drug?

\end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 9
\item We are writing a WebMD program that is slightly larger than the one we worked through in class. In this program we  predict whether a user has a flu ($F=1$) or cold ($C = 1$) based on knowing any subset of 10 potential binary symptoms (e.g., headache, sniffles, fatigue, cough, etc) and a subset of binary risk factors (exposure, stress). 

\vspace{-3mm}
% to include this image with your code:
% 1) download the website image: http://web.stanford.edu/class/cs109/img/psets/pset5_webmd.png
% 2) save the image to the same folder as this file (e.g., upload to overleaf)
% otherwise just comment out everything from \begin{figure} to \end{figure}.
\begin{figure}[h]
\centering
\includegraphics[width=0.75\textwidth]{pset5_webmd.png}
\end{figure}

\vspace{-5mm}
\begin{itemize}
\item We know the prior probability for Stress is 0.5 and Exposure is 0.1. 
 
\item The functions \code{probCold(s, e)} and \code{probFlu(s, e)}  return the probability that a patient has a cold or flu, given the state of the risk factors stress (\code{s}) and exposure (\code{e}).
 
\item The function \code{probSymptom(i, f, c)} which returns the probability that the \code{i}th symptom ($X_i$) takes on value 1, given the state of cold (\code{c}) and flu (\code{f}): $P(X_i = 1 | F = f, C = c)$.
\end{itemize}

We would like to write pseudocode to calculate the probability of flu \emph{conditioned on observing} that the patient has had exposure to a sick friend and that they are experiencing Symptom 2 (sore throat). In terms of random variables $P$(Flu = 1 | Exposure = 1, X$_2$ = 1):
\begin{mdframed}
\code{def inferProbFlu()   \#}  $P$(Flu = 1 | Exposure = 1 and $X_2$ = 1)
\end{mdframed}

\begin{enumerate}[label=\alph*.,leftmargin=5mm]
\item Write pseudocode that calculates \code{inferProbFlu()} using \textbf{Rejection Sampling}.

\item (Reach) Write pseudocode that calculates \code{inferProbFlu()} without using sampling.
\begin{mdframed}
Note: Causality implies the following: (1) risk factors are independent; (2) all diseases are independent of one another conditioned on risk factors; and (3) all symptoms are independent of one another conditioned on knowing the state of diseases.
\begin{gather}
    P(S = s, E = e) = P(S = s)P(E = e)\\
    P(C = c, F = f | S = s, E = e) = P(C = c | S = s, E = e) \cdot P(F = f | S = s, E = e)\\
    P(\text{symptoms} | F = f, C = c) = \prod_j P(X_j = k_j | F = f, C = c) 
\end{gather}
\end{mdframed}
"Reach" means I don't \emph{expect} CS109 students to be able to solve the problem. But thinking about it will be useful. Show your work. If you get stuck ($>$ 15 mins), explain what is hard.
\end{enumerate}

    \begin{shaded}
    \begin{answer}

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



\end{enumerate}


\end{document}
  