\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{\expect}[1]{\Exp\left[#1\right]}


\begin{document}
\title{{\bf Problem Set 8 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 (20 points)}
Please do the questions on Gradescope.
\begin{tcolorbox}
Nothing to write for this question.
\end{tcolorbox}

\newpage
\section{Collisions (15 points)}
A total of $m$ items are to be sequentially inserted into a hash table of size $n$, where each item is mapped independently, but the items are not mapped uniformly into the table. Instead, an item is mapped to cell $j$ of the table with probability $p_j$, for $j = 1, \ldots, n$ (where $\sum_{j=1}^n p_j =1$). We say that a collision occurs whenever an item is mapped into a nonempty cell. Find $\expect{X}$, where $X$ is the number of collisions that occur during this process. You can leave your answer as an unsimplified sum.

    Hint: Write $X= X_1+ X_2 + \ldots + X_m$ where $X_i$ is an indicator random variable that is 1 if there is a collision when the $i$-th item is put into a cell and 0 otherwise; then use linearity of expectation. To compute $\expect{X_i}$, use the law of total expectation, conditioning on which cell it is placed into.

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

\newpage
\section{Lazy Grader (12 points)}
Prof.\ Lazy decides to assign final grades in CSE 312 by
ignoring all the work the students have done and instead using the
following probabilistic method: each student independently will be
assigned an A with probability $\theta$, a B with probability
$3\theta$, a C with probability $\frac{2}{3}$, and an F with
probability $\frac{1}{3} - 4\theta$. When the quarter is over, you
discover that only 10 students got an A, 35 got a B, 40 got a C, and 15
got an F.

\medskip

\noindent Find the maximum likelihood estimate for the parameter
$\theta$ that Prof.\ Lazy used. Give an exact answer as a simplified
fraction. You do not need to check second order conditions.

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


\newpage
\section{The Place That's Best (12 points)}
Let $y_1, y_2, ... y_n$ be i.i.d. samples of a random variable from the family of distributions $Y(\theta)$ with densities \[f(y; \theta) = \frac{1}{2\theta}\exp\left(-\frac{|y|}{\theta}\right) \;,\]
where $\theta > 0$. Find the MLE for $\theta$ in terms of the $|y_i|$ values and $n$. You do not need to check second order conditions.

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

\newpage
\section{(Un)biased Estimation (10 points)}
\begin{enumerate}
\item  Let $X_1=x_1, \ldots, X_n=x_n$ be independent samples from the Poisson distribution with parameter $\theta$. In the section 9 worksheet, we have seen that the MLE estimator for $\theta$ is $\hat{\theta}(X_1=x_1, \ldots,X_n= x_n) = \frac{1}{n} \sum_{i=1}^n x_i$. Thus, viewed as  a random variable, the estimator is 
 \[\hat{\theta}(X_1,\ldots, X_n) = \frac{1}{n} \sum_{i=1}^n X_i\]Is this estimator unbiased?

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

\item 
Let $X_1=x_1, \ldots, X_n=x_n$  be independent samples from Unif$(0,\theta)$, the continuous uniform distribution on $[0, \theta]$. Consider the estimator \[\hat{\theta}_{\mathrm{first}} (X_1=x_1, \ldots, X_n=x_n)= 2x_1,\] i.e., our estimator ignores the samples $x_2, \ldots, x_{n}$ and just outputs twice the value of the first sample. Is 
\[\hat{\theta}_{\mathrm{first}} (X_1,\ldots, X_n)= 2X_1\]unbiased? 

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

\end{document}