% 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-S21}
\assignment{Assignment \#7}
\duedate{6:00pm April 2, 2021}
\dropboxurl{https://www.gradescope.com/courses/214271/assignments/1118516}
\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/spring21/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}[15pts]
You enter a chess tournament where your probability of winning a game is 0.3 against half of the
players (call them type 1), 0.4 against a quarter of the players (call them type 2), and 0.5 against
the remaining quarter of the players (call them type 3).
\begin{enumerate}[(A)]
\item What is the probability of winning against a randomly chosen opponent?
\item Suppose that you win. What is the probability that you had an opponent of type 1?
\end{enumerate}
\end{problem}
\newpage
\begin{problem}[18pts]
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}[25pts]
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}[40pts]
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
\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 22 March 2021 -- S21 initial version
\end{itemize}
% \includepdf[pages=-]{mynotebook.pdf}
\end{document}