\documentclass[letterpaper,11pt]{article}

\newcommand{\removefromfile}[1]{}

\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage[most]{tcolorbox}
\renewcommand{\theenumi}{\alph{enumi}}
\providecommand{\Exp}{\mathbb{E}}
\providecommand{\Var}{\text{Var}}
\providecommand{\Cov}{\text{Cov}}

\providecommand{\expect}[1]{\Exp\left[#1\right]}
\providecommand{\Variance}[1]{\Var\left[#1\right]}
\providecommand{\Covariance}[1]{\Cov\left(#1\right)}

\begin{document}
\title{{\bf Problem Set 7 Solutions}}
\author{Name: TODO}
\date{}
\maketitle

\section*{Collaborators}
\begin{tcolorbox}
List collaborators, if any.
\end{tcolorbox}

\section*{Use of 312 Learning Assistant}
\begin{tcolorbox}
List which problems you used the 312 Learning Assistant on.
\end{tcolorbox}

\newpage
\section{Gradescope Questions (15 points)}
Please do the questions on Gradescope.
\begin{tcolorbox}
Nothing to write for this question.
\end{tcolorbox}

\newpage
\section{The LeetCode Grind (25 points)}
You are grinding Leetcode to prepare for software engineering interviews for $H$ hours, where $H$ is a random variable, \textbf{equally likely} to be 1, 2 or 3. The number of \texttt{Difficult} problems $D$ that you successfully solve is random and depends on how long you practice. We are told that
\[\Pr(D = d \mid H= h) = \frac{1}{h},\quad\quad \text{ for }d=1, \ldots, h \;.\]


\begin{enumerate}
    \item (5 points) Find the joint distribution of $D$ and $H$. (Hint: use the chain rule). 
    \begin{tcolorbox}
    TODO: Your solution here.
    \end{tcolorbox}
    \item (5 points) Find the marginal distribution of $D$.
    \begin{tcolorbox}
    TODO: Your solution here.
    \end{tcolorbox}
    \item (5 points) Find the conditional distribution of $H$ given that $D=1$ (that is, $\Pr(H= h \mid D=1)$ for each possible $h$ in $\{1,2,3\}$). Use the definition of conditional probability and the results from previous parts.
    \begin{tcolorbox}
    TODO: Your solution here.
    \end{tcolorbox}
    \item (10 points) Suppose that we are told that you solved 1 or 2 \texttt{Difficult} problems. Note that these are two mutually exclusive events. Find the expected number of hours you practiced conditioned on this event, defined as follows:
    \[\expect{H \mid D=1 \cup D=2} = \sum_{h=1}^3 h \cdot \Pr(H=h \mid D=1 \cup D=2)\]
    \begin{tcolorbox}
    TODO: Your solution here.
    \end{tcolorbox}
\end{enumerate}



\newpage
\section{Joint densities I (16 points)}
\begin{enumerate}
    
\item (4 points) Let $Z$ be a uniformly random point in the unit radius disk centered at the origin of a plane in two dimensions. Let $X$ (resp. $Y$) be the $x$-coordinate (respectively $y$-coordinate) of $Z$. Give a simple argument (of at most a few sentences) to show that $X$ and $Y$ are not independent.

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\item (12 points) Suppose that $X$ and $Y$ (not the same as in the previous part of this problem) have the following joint density:
\[f_{X,Y}(x,y) = \begin{cases} 
a & \quad 0 < x \le 0.5,~ 0  <y \le 0.5 \\
b & \quad 0 < x \le 0.5,~ 0.5 < y < 1 \\
b & \quad 0.5 < x \le 1,~ 0 \le y \le 0.5\\
a & \quad 0.5 < x < 1,~ 0.5 < y < 1,\\
\end{cases}\]
where $a$ and $b$ are constants.\\
- For what values of $a$ and $b$ are the marginal distributions of $X$ and $Y$ uniform on (0,1)?\\
- For what values of $a$ and $b$ are $X$ and $Y$ independent?\\
Note that some of your answers may simply be restrictions on the values $a$ and $b$ can take on, rather than specific values. Justify your answers.

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\end{enumerate}

\newpage

\section{Joint Densities II (10 points)}
Let $X,Y,Z$ be independent and uniformly distributed over (0,1) Compute \[\Pr(X \ge YZ).\]
Your answer should be a number. Hint: You just need to integrate over the relevant region of the joint density $f_{X,Y,Z}(x,y,z)$. Carefully choose the order of integration.

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}



\newpage
\section{Sticks I (10 points)}
We are given a line segment, $[0,1]$. Two darts are each independently thrown uniformly at random within the line segment. What is the probability that the value of the first dart is at least three times the value of the other? Hint: Use the continuous law of total probability, conditioning on the value of the other dart.

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\newpage 
\section{Covariance (15 points)}
(We may or may not talk about covariance in class, but it is important for you to know about.)
Also, note that some portions of this problem are covered in \href{https://courses.cs.washington.edu/courses/cse312/22au/files/Prob_Stat_for_CS_Book.pdf}{Section 5.3} of the book. Regardless of that fact, be sure you include all details of your derivations for the following questions. For any two random variables $X,Y$ the \emph{covariance} is
  defined as
  \[\Covariance{X,Y}=\expect{(X-\expect{X})(Y-\expect{Y})}.\]
In this problem, if you prefer, you may assume that $X$ and $Y$
  are discrete random variables.    
\begin{enumerate}
    \item (3 points) Show that  \[\Covariance{X,Y}=\expect{XY} - \expect{X}\expect{Y}.\] 
    \begin{tcolorbox}
    TODO: Your solution here.
    \end{tcolorbox}
    \item (3 points) Show that for any two random variables 
    \[\text{Var}(X+Y) = \text{Var}(X) + \text{Var}(Y) + 2 \Covariance{X,Y}.\] 
    \begin{tcolorbox}
    TODO: Your solution here.
    \end{tcolorbox}
    \item (3 points)  If $\expect{Y|X=x} = x$ show that $\Covariance{X,Y} = \text{Var}(X)$.
    \begin{tcolorbox}
    TODO: Your solution here.
    \end{tcolorbox}
    \item (3 points)  If $X,Y$ are independent show that $\Covariance{X,Y}=0$.
    \begin{tcolorbox}
    TODO: Your solution here.
    \end{tcolorbox}
    \item (3 points) If $X$ and $Y$ have $\Covariance{X,Y} > 0$, we say that $X$ and $Y$ are positively correlated. If $\Covariance{X,Y} < 0$, we say that $X$ and $Y$ are negatively correlated. Suppose that $\Omega_X = \{0,1\}$, $\Omega_Y = \{0,1\}$ and
    $\Omega_{X,Y} = \{(0,0), (0,1), (1,0), (1,1)\}$. Give a valid joint probability mass function for $X$ and $Y$ for which $X$ and $Y$ are positively correlated. Then give a different joint probability mass function for $X$ and $Y$ (same ranges) for which $X$ and $Y$ are negatively correlated.
    \begin{tcolorbox}
    TODO: Your solution here.
    \end{tcolorbox}

    \newpage
    \section{Distinct Elements [Coding] (20 points)}

    See \href{https://edstem.org/us/courses/96846/lessons/162345/slides/954054}{edstem lesson}. Upload your final solution to Gradescope (see instructions above).

    Refer to \href{https://courses.cs.washington.edu/courses/cse312/22au/files/Prob_Stat_for_CS_Book.pdf}{Section 9.5} of the book for more details on the distinct elements algorithm.
    \begin{tcolorbox}
    Nothing to write for this question.
\end{tcolorbox}
\end{enumerate}


\end{document}