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

\makeatletter
\let\runauthor\@author
\lhead{\runauthor}
\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}}

\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

%%%% Cite any collaboration here %%%
Cited collaboration: N/A
  
\begin{enumerate}
% 1
\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


% 2
\item Users independently sign up for 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 more than 40 new users across both websites in the next 2 minutes?

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

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


% 3
\item Say that of all the students who will attend Stanford, each will buy at most one laptop computer when they first arrive at school. 40\% of students will purchase a PC, 30\% will purchase a Mac, 10\% will purchase a Linux machine and the remaining 20\% will not buy any laptop at all.  If 15 students are asked which, if any, laptop they purchased, what is the probability that exactly 6 students will have purchased a PC, 4 will have purchased a Mac, 2 will have purchased a Linux machine, and the remaining 3 students will have not purchased any laptop?

    \begin{shaded}
    \begin{answer}

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


% 4
\item Say we have two independent variables $X$ and $Y$, such that $X \sim \Geo(p)$ and $Y \sim \Geo(p)$.  Mathematically derive an expression for $P(X = k | X + Y = n)$, where $k$ and $n$ are non-negative integers.

    \begin{shaded}
    \begin{answer}

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


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


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


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


% 8
\item In class, we considered the following recursive function:

\begin{minted}[frame=single]{python}
def recurse():
    x = np.random.choice([1,2,3])   # equally likely values 1,2,3
    if (x == 1): return 3
    elif (x == 2): return (5 + recurse())
    else: return (7 + recurse())

\end{minted}

Let $Y=$ the value returned by \texttt{recurse()}. We previously computed $E[Y] = 15$. What is $\text{Var}(Y)$?

    \begin{shaded}
    \begin{answer}

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


% 9
\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 20\% probability.  Your other friend's phone will independently drop calls with 30\% 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 20\% versus 30\% 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


% 10
\item See Problem Set \#4 for a full write-up of this problem. You will submits part (a) and (b) as code in Gradescope. If you do not get a code solution to part (b), explain what is hard in a write up in this document.

    \begin{shaded}
    \begin{answer}

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



% 11
\item \textbf{[Written, Extra Credit]} Consider a bit string of length $n$, where each bit is independently generated and has probability $p$ of being a 1.  We say that a \emph{bit switch} occurs whenever a bit differs from the one preceding it in the string (if there is a preceding bit).  For example, if $n = 5$ and we have the bit string 11010, then there are 3 bit switches.  Find the expected number of bit switches in a string of length $n$. (Hint: You might find it helpful to use a set of indicator (Bernoulli) variables that are defined in terms of whether a bit switch occurred in each \emph{position} of the string.  And in case you're wondering why we care about bit switches, the number of bit switches in a string can be one indicator of how compressible that string might be---for example, if the bit string represented a file that we were trying to ZIP.)

    \begin{shaded}
    \begin{answer}

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



\end{enumerate}


\end{document}
  