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

\lhead{author}
\chead{Problem Set \#4}
\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}}

\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 A company owns two online social networking sites, Lookbook and Quickgram. On average, 7.5 users sign up for Lookbook each minute, while on average 5.5 users sign up for Quickgram each minute. The number of users signing up for Lookbook and for Quickgram each minute are independent. A new user is defined as a new account, i.e., the same person signing up for both social networking sites will count as two new users.

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

    \item What is the probability that more than 10 new users will sign up for the Lookbook social networking site in the next minute?

    \item What is the probability that more than 13 new users will sign up for the Quickgram social networking site in the next 2 minutes?

    \item What is the probability that the company will get a combined total of 40 new users across both websites in the next 2 minutes?

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 2
\item The \textbf{median} of a continuous random variable having cumulative distribution function $F$ is the value $m$ such that $F(m) = 0.5$.  That is, a random variable is just as likely to be larger than its median as it is to be smaller.  Find the median of $X$ (in terms of the respective distribution parameters) in each case below.

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

    \item $X \sim \Uni(a, b)$

    \item $X \sim \N(\mu, \sigma^2)$

    \item $X \sim \Exp(\lambda)$

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 3
\item  Let $X$, $Y$, and $Z$ be independent random variables, where $X \sim \N(\mu_1, {\sigma_1}^2)$, $Y \sim \N(\mu_2, {\sigma_2}^2)$, and $Z \sim \N(\mu_3, {\sigma_3}^2)$.  
    \begin{enumerate}[label=\alph*.]

    \item Let $A = X + Y$. What is the distribution (along with parameter values) for A?
    \item Let $B = 4X + 3$. What is the distribution (along with parameter values) for B?
    \item Let $C = aX - b^2Y + cZ$, where $a$, $b$, and $c$ are real-valued constants.  What is the distribution (along with parameter values) for $C$?  Show how you derived your answer.

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 4
\item You roll 6 six-sided dice. How much more likely is a roll with [1 one, 1 two, 1 three, 1 four, 1 five, 1 six] than a roll with 6 sixes? Think of your dice roll as a multinomial.

    \begin{shaded}
    \begin{answer}

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


% 5
\item Let $X_i = {}$the number of weekly visitors to a web site in week $i$, where $X_i \sim \N(2200, 44100)$ for all $i$.  Assume that all $X_i$ are independent of each other.

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

    \item What is the probability that the total number of visitors to the web site in the next two weeks exceeds 5000?

    \item What is the probability that the weekly number of visitors exceeds 2000 in at least 2 of the next 3 weeks?

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 6
\item The joint probability density function of continuous random variables X and Y is given by: \[f_{X,Y}(x,y) = c \frac{y}{x} \qquad\text{where $0 < y < x < 1$}\]
    \begin{enumerate}[label=\alph*.]

    \item What is the value of $c$ in order for $f_{X,Y}(x,y)$ to be a valid probability density function?

    \item Are $X$ and $Y$ independent?  Explain why or why not.

    \item What is the marginal density function of $X$?

    \item What is the marginal density function of $Y$?

    \item What is $E[X]$?

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 7
\item Recall the example of zero sum games for teams with ELO scores $S_1$ (Team 1) and $S_2$ (Team 2). When a game is played between the two teams, they each sample an ability ($A_1$ and $A_2$ for Teams 1 and 2, respectively) from a normal distribution with mean equal to the team's ELO score and constant variance. The variance is different for different types of games; for this problem, we will use the GO rating variance of $\sigma^2 = (2000/7)^2$. In lecture, we talked about how to calculate the probability that a team wins via sampling. In this problem, we will work out a closed form calculation.

\begin{enumerate}
\item What is the probability distribution for the difference between $A_1$ and $A_2$, defined as $A_1 - A_2$?

\item A team wins if their sampled ability on game day is larger. Come up with a closed form expression for the probability that Team 1 wins.

\item The best humnan GO player in the world is Ke Jie, with an ELO score of 3670. Alpha GO is a computer with an ELO score of 5200. How many independent games would they have to play before the expected number of games that Ke wins is $\geq 1$?

\end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 8
\item A robot is located at the \emph{center} of a square world that is 10 kilometers on each side.  A package is dropped off in the robot's world at a point $(x, y)$ that is uniformly (continuously) distributed in the square.  If the robot's starting location is designated to be $(0, 0)$ and the robot can only move up/down/left/right parallel to the sides of the square, the distance the robot must travel to get to the package at point $(x, y)$ is $|x| + |y|$.  Let $D = {}$the distance the robot travels to get to the package.  Compute $E[D]$.

    \begin{shaded}
    \begin{answer}

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


% 9
\item Let $X_1, X_2, \dots$ be a series of independent random variables which all have the same mean $\mu$ and the same variance $\sigma^2$.  Let $Y_n = X_n + X_{n+1}$.  For $j = {}$0, 1, and 2, determine $\Cov(Y_n, Y_{n+j})$.  Note that you may have different cases for your answer depending on the value of $j$.

    \begin{shaded}
    \begin{answer}

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


% 10
\item Choose a number $X$ at random from the set of numbers $\{1, 2, 3, 4, 5\}$.  Now choose a number at random from the subset no larger than $X$, that is from $\{1, \dotsc, X\}$.  Let $Y$ denote the second number chosen.

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

    \item Determine the joint probability mass function of $X$ and $Y$.

    \item Determine the conditional mass function of $X$ given $Y = i$.  Do this for $i = 1, 2, 3, 4, 5$.

    \item Are $X$ and $Y$ independent?  Justify your answer.

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 11
\item You are tracking the distance of a satellite from Earth by reading values from a distance measurement instrument. Before you observe the instrument reading, your belief of the distance $D$ of the satellite was a Gaussian distribution $D \sim N(\mu = 98, \sigma^2 = 16)$. The instrument gives a reading that is true distance plus Gaussian noise $G$, where  $G\sim N(0,4)$. Suppose the instrument reports that the satellite is 100 a.u.\ from Earth. 

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

    \item What is the PDF of your prior belief of the true distance of the satellite?
    \item What is the probability density of seeing an observation of 100 a.u.\ from your instrument, given that the true distance of the satellite is equal to $t$?
    \item What is the PDF of your posterior belief (after observing the instrument reading) of the true distance of the satellite? You may leave a constant in your PDF and you do not need to simplify the PDF.

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 12
\item Consider a series of strings that independently get hashed into a hash table.  Each such string can be sent to any one of $k + 1$ buckets (numbered from 0 to $k$).  Let index i denote the $i$-th bucket.  A string will independently get hashed to bucket $i$ with probability $p_i$, where $\sum_{i=0}^k p_i = 1$.  Let $N$ denote the number of strings that are hashed until one is hashed to any bucket other than bucket 0.  Let $X$ be the number of that bucket (i.e. the bucket not numbered 0 that receives a string).

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

    \item Find $P(N = n), n \geq 1$.

    \item Find $P(X = j)$, $j = 1, 2, \dotsc, k$.

    \item Show that $N$ and $X$ are independent.

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 13
\item Consider the following function, which simulates repeatedly rolling a 6-sided die (where each integer value from 1 to 6 is equally likely to be ``rolled'') until a value${}\geq 3$ is ``rolled''.

\begin{minted}[frame=single]{python}
def roll():
  total = 0
  while(True):
    # randomInteger is equally likely to return 1, ..., 6
    roll = randomInteger(1, 6)
    total += roll
    
    # exit condition:
    if (roll >= 3):
      break
  return total
\end{minted}

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

    \item Let $X = {}$the value returned by the function \texttt{roll()}.  What is $E[X]$?

    \item Let $Y = {}$the number of times that the die is "rolled" (i.e., the number of times that \texttt{randomInteger(1, 6)} is called) in the function \texttt{roll()}.  What is $E[Y]$?

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 14
\item Our ability to fight contagious diseases depends on our ability to model them. One person is exposed to llama-flu. The method below models the number of individuals who will get infected.

\begin{minted}[frame=single]{python}
from scipy import stats
"""
Return number of people infected by one individual.
"""
def num_infected():
  # most people are immune to llama flu.
  # stats.bernoulli(p).rvs() returns 1 w.p. p (0 otherwise)
  immune = stats.bernoulli(p = 0.99).rvs() 
  if immune: return 0

  # people who are not immune spread the disease far by
  # making contact with k people (up to 100).
  spread = 0
  # returns random # of successes in n trials w.p. p of success
  k = stats.binom(n = 100, p = 0.25).rvs() 
  for i in range(k):
    spread += num_infected()
   
   # total infections will include this individual
   return spread + 1
\end{minted}

What is the expected return value of \texttt{numInfected()}?

    \begin{shaded}
    \begin{answer}

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


% 15
\item \textbf{[Coding]} Did you know that computers can identify you not only by what you write, but also by how you write? Coursera uses Biometric Keystroke signatures for plagiarism detection. If you cannot write a sentence with the same statistical distribution of key press timings as in your previous work, they assume that you are not the person sitting behind the computer. In this problem we provide you with three files: 

\begin{itemize}
\item \texttt{personKeyTimingA.txt} has keystroke timing information for a user A writing a passage. The first column is the time in milliseconds (since the start of writing) when the user hit each key. The second column is the key that the user hit.

\item \texttt{personKeyTimingB.txt} has keystroke timing information for a second user (user B) writing the same passage as the user A. Even though the content of the passage is the same the timing of how the second user wrote the passage is different.

\item \texttt{email.txt} has keystroke timing information for an unknown user. We would like to know if the author of the email was user A or user B.
\end{itemize}

Let X and Y be random variables for the duration of time, in milliseconds, for users A and B (respectively) to type a key. Assume that each keystroke from a user has a duration that is an independent random variable with the same distribution. 


    \begin{enumerate}[label=\alph*.]
	\item Estimate $E[X]$ and $E[Y]$ and report your values.
	\item Estimate $E[X^2]$ and $E[Y^2]$ and report your values.
	\item Use your answers to part (a) and (b) and approximate $X$ and $Y$ as Normal random variables with mean and variance that match their biometric data. Report both distributions.
	\item Calculate the ratio of the probability that user A wrote the email over the probability that user B wrote the email. You do not need to submit code, but you should include the formula that you attempted to calculate and a short description (a few sentences) of how your code works.

	\end{enumerate}

    \begin{shaded}
    \begin{answer}

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



\end{enumerate}


\end{document}
  