% No 'submit' option for the problems by themselves.
\documentclass{cos302}
% Use the 'submit' option when you submit your solutions.
%\documentclass[submit]{cos302}
% Put in your full name and email address.
\name{Your Name}
\email{email@princeton.edu}
\discussants{Marie Curie \\ Leonhard Euler}
% You don't need to change these.
\course{COS302-F22}
\assignment{Assignment \#7}
\duedate{6:00pm Wednesday 9 November 2022}
\dropboxurl{FIXME}
\usepackage{bm} % for bold math
\usepackage{mathtools} % colon-equals
\usepackage{multirow}
\begin{document}
% IMPORTANT: Uncomment the \documentclass command above with the [submit] option and put your name where it says ``your name''.
\begin{center}
Assignments in COS 302 should be done individually. See the \href{https://www.cs.princeton.edu/courses/archive/spring20/cos302/files/syllabus.pdf}{course syllabus} for the collaboration policy.
\vspace{\baselineskip}
\textcolor{red}{%
Remember to append your Colab PDF as explained in the first homework, with all outputs visible.\\
When you print to PDF it may be helpful to scale at 95\% or so to get everything on the page.}
\end{center}
\begin{problem}[20pts]
Consider the following cumulative distribution function for a random variable~$X$ that takes values in~$\mathbb{R}$:
\begin{align*}
F(x) &= P(X \leq x) = \frac{1}{1 + e^{-x}}
\end{align*}
\begin{enumerate}[(A)]
\item What is the probability density function for this random variable?
\item Find the inverse distribution (quantile) function~$F^{-1}(u)$ that maps from~$(0,1)$ to~$\mathbb{R}$.
\item In a Colab notebook, implement inversion sampling and draw 1000 samples from this distribution.
Make a histogram of your results.
\end{enumerate}
\end{problem}
\newpage
\begin{problem}[15pts]
Consider two random variables~$X$ and~$Y$ with a joint probability density function~$p(x,y)$.
Show that
\begin{align*}
\mathbb{E}_X[x] &= \mathbb{E}_Y[\mathbb{E}_X[x\,|\,Y=y]]
\end{align*}
where the notation~$\mathbb{E}_X[x\,|\,Y=y]$ denotes the expectation of~$X$ under the conditional distribution~$P(X \,|\, Y=y)$.
\end{problem}
\newpage
\begin{problem}[20pts]
The covariance between two random variables \(X\) and \(Y\) can be computed as:
\[
\text{cov}(X,Y) = \mathbb{E}[XY] - \mathbb{E}[X]\mathbb{E}[Y].
\]
If \(X\) and \(Y\) are independent, then \(\mathbb{E}[XY] = \mathbb{E}[X]\mathbb{E}[Y]\) which implies that
\(\text{cov}(X,Y) = 0\). However, the converse is not true: if the covariance between two random variables is zero,
this \textit{does not} imply that these variables are independent.
Let's construct a counterexample to show this is the case in a Colab notebook.
Be sure to append your PDF and insert your link as usual.
\begin{enumerate}[(A)]
\item Let $X$ be a random variable that can take on only the values -1 and 1 and $P(X = -1) = 0.5 = P(X = 1)$.
Generate 1,000,000 samples of $X$.
\item Let \(Y\) be random variable such that \(Y = 0\) if \(X = -1\), and \(Y\) is randomly either -1 or 1 with probability 0.5 if \(X = 1\). Construct 1,000,000 samples of \(Y\) based on the samples of \(X\) you generated in part (A).
\item Use numpy to numerically compute the covariance between \(X\) and \(Y\).
\end{enumerate}
\end{problem}
\newpage
\begin{problem}[23pts]
You're playing a game at a carnival in which there are three cups face down and if you choose the one with a ball under it, you win a prize.
This is sometimes called a \emph{shell game}.
At this carnival, there is a twist to the game: after you pick a cup, but before you're shown what is beneath it, the game operator reveals to you that one of the other cups (one of the two you did not choose) is empty.
The operator now gives you the opportunity to switch your selection to the other unrevealed cup.
To clarify with an example: imagine there are cups $A$, $B$, and $C$.
It is equally probable that the ball is beneath any of the three.
You choose $B$. Before you see what is under $B$, the operator lifts $A$ and shows you there is nothing under it.
You are now presented with the option to keep your selection of $B$, or switch to the still-unrevealed cup~$C$.
\begin{enumerate}[(A)]
\item Is it better, worse, or the same to switch to the other cup? Explain your reasoning in terms of probabilities.
\item In a Colab notebook, simulate this game.
Run 1,000 games with the \emph{stay} strategy and 1,000 games with the \emph{switch} strategy.
Report the win rate of each strategy and explain which one empirically seems better.
\item Now imagine that there are $N > 3$ cups face down and one has a ball under it. As a function of~$N$, what are the win probabilities for the \emph{stay} and \emph{switch} strategies? You can assume that under the \emph{switch} strategy you choose uniformly from the other cups.
\item Verify your answers empirically by simulating these strategies for $N=5$, $N=10$, and $N=25$ as in part (B) above.
\end{enumerate}
\end{problem}
\newpage
% Independence vs Conditional Indepdence
\begin{problem}[20pts]
Recall that two random variables \(X\) and \(Y\) are independent if and only if \(P(X,Y) = P(X)P(Y)\).
Two random variables \(X\) and \(Y\) are \textbf{conditionally} independent given a third event \(Z\)
if \(P(X,Y | Z) = P(X|Z)P(Y|Z)\).
The following problem explores the relationship between independence and conditional independence, specifically
whether independence implies conditional independence or vice versa.
\begin{enumerate}[(A)]
\item
Imagine that you have two coins: one regular fair coin ($P(\text{heads}) = 0.5$) and one fake two-headed coin ($P(\text{heads})=1$).
Consider the following experiment: choose a coin at random and toss it twice. Define the following events:
\begin{itemize}
\item $A$ is the event that the first coin toss results in a heads.
\item $B$ is the event that the second coin toss results in a heads.
\item $C$ is the event that the regular fair coin has been selected.
\end{itemize}
Are the events $A$ and $B$ independent? Give a qualitative answer, i.e., either yes because... or no because...
Are they conditionally independent given $C$? Show your work, i.e., explicitly show the definition holds as given in the problem statem
ent.
\item
Roll a single six-sided die and consider the following events:
\begin{itemize}
\item \(X\) is that you roll 1 or 2, i.e., \(X = \{1,2\}\).
\item \(Y\) is that you roll an even number, i.e., \(Y = \{2,4,6\}\).
\item \(Z\) is that you roll 1 or 4, i.e., \(Z = \{1,4\}\).
\end{itemize}
Are the events \(X\) and \(Y\) independent? Are they conditionally independent given \(Z\)? For both of these
questions show the definitions hold as in the problem statement.
\end{enumerate}
\end{problem}
\newpage
\begin{problem}[2pts]
Approximately how many hours did this assignment take you to complete?
\end{problem}
My notebook URL:
{\small \url{https://colab.research.google.com/XXXXXXXXXXXXXXXXXXXXXXX}}
\subsection*{Changelog}
\begin{itemize}
\item 30 Oct 2022 -- Initial F22 version
\end{itemize}
% \includepdf[pages=-]{mynotebook.pdf}
\end{document}