% 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 \#9}
\duedate{6:00pm April 16, 2021}
\dropboxurl{https://www.gradescope.com/courses/214271/assignments/1156197}
\usepackage{bm} % for bold math
\usepackage{mathtools} % colon-equals
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{underscore}
\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]
A coin is weighted so that its probability of landing on heads is 0.2, suppose the coin is flipped 20 times.
\begin{enumerate}[(A)]
\item Compute the probability that the coin lands on heads at least 16 times.
\item Use Markov's inequality to bound the event that the coin lands on heads at least 16 times.
\item Use Chebyshev's inequality to bound the event that the coin lands on heads at least 16 times.
\end{enumerate}
\end{problem}
\newpage
\begin{problem}[28pts]
The moment generating function (MGF) for a random variable $X$ is:
\begin{align*}
M_X(t) &= \mathbb{E}[e^{tX}]\,.
\end{align*}
One useful property of moment generating functions is that they make it relatively easy to compute weighted sums of independent random variables:
\begin{align*}
Z &= \alpha X + \beta Y & M_Z(t) &= M_X(\alpha t)M_Y(\beta t)\,.
\end{align*}
\begin{enumerate}[(A)]
\item Derive the MGF for a Poisson random variable $X$ with parameter $\lambda$. (Hint: Note that $e^{tX}=(e^t)^X$ and apply the ``pattern matching normalization constant'' trick from the previous homework.)
\item Let $X$ be a Poisson random variable with parameter $\lambda$, as above, and let $Y$ be a Poisson random variable with parameter $\gamma$. $X$ and $Y$ are independent. Use the MGF to show that their sum is also Poisson. What is the parameter of the resulting distribution?
\item Derive the MGF for an exponential random variable~$X$ with parameter $\lambda$.
For what values of~$t$ does the MGF $M_X(t)$ exist?
\item Let $X$ be an exponential random variable with parameter $\lambda$, and let $\alpha>0$ be a constant. Show that the random variable $\alpha X$ is also exponentially distributed. What is its parameter?
\end{enumerate}
\end{problem}
\newpage
\begin{problem}[30pts]
In this problem, you will use the entire 50k-digit MNIST data set.
To remind you, the data are $28\times 28$ greyscale images of the digits 0 through 9.
Download the \href{https://www.cs.princeton.edu/courses/archive/spring21/cos302/files/mnist_full.pkl.gz}{\texttt{mnist\_full.pkl.gz}} file and load it with something like this:
\begin{lstlisting}[style=python]
import pickle as pkl
import numpy as np
import gzip
with gzip.open('mnist_full.pkl.gz, 'rb') as fh:
mnist = pkl.load(fh)
\end{lstlisting}
This will give you a \href{https://docs.python.org/3.3/library/functions.html#func-dict}{dictionary} \texttt{mnist} with keys and values that should be self-explanatory.
It is possible that when you run the code to solve the problems below, that you run into issues in which the covariance matrix is not positive definite. To solve this, add a little bit of diagonal to it, i.e., add $\alpha\mathbb{I}$, for $\alpha\approx 10^{-6}$.
\begin{enumerate}[(A)]
\item Compute the empirical mean~$\bm{\mu}$ and covariance~$\bm{\Sigma}$ of the training images.
\item Reshape and render the mean as an image using \href{https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.imshow.html}{\texttt{imshow}}.
\item Generate 5 samples from the multivariate Gaussian with parameters~$\bm{\mu}$ and~$\bm{\Sigma}$ from (A). Do this only using \href{https://numpy.org/doc/stable/reference/random/generated/numpy.random.randn.html#numpy.random.randn}{\texttt{numpy.random.randn}} and linear algebra operations.
Reshape and render these samples using \href{https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.imshow.html}{\texttt{imshow}}.
\item Now iterate over each of the possible labels from 0 to 9. Compute the mean and covariance of the training data that have that label. Here's a sketch of some code for getting the correct images:
\begin{lstlisting}[style=python]
for label in range(10):
indices = train_labels == label
images = train_images[indices,:]
\end{lstlisting}
Render the mean of each as an image, and generate 5 samples from the Gaussian distribution with the label-specific mean and covariance. Render these samples.
\end{enumerate}
\end{problem}
\newpage
\begin{problem}[25pts]
Consider the following joint distribution over random variables $X$ and $Y$:
\begin{center}
\begin{tabular}{c c | l | l | l | l | l |}
\cline{3-7}
\multirow{4}{*}{$Y$} & $y_1$ & 0.01 & 0.02 & 0.03 & 0.1 & 0.1 \\ \cline{3-7}
& $y_2$ & 0.05 & 0.1 & 0.05 & 0.07 & 0.2 \\\cline{3-7}
& $y_3$ & 0.1 & 0.05 & 0.03 & 0.05 & 0.04\\\cline{3-7}
& \multicolumn{1}{c}{}& \multicolumn{1}{c}{$x_1$} & \multicolumn{1}{c}{$x_2$} & \multicolumn{1}{c}{$x_3$} & \multicolumn{1}{c}{$x_4$} & \multicolumn{1}{c}{$x_5$}\\
& \multicolumn{1}{c}{}& \multicolumn{5}{ c }{$X$}
\end{tabular}
\end{center}
Use Colab to compute the following quantities.
Remember to compute these in \textbf{bits} which means using base 2 for logarithms.
Here's the PMF in Python to make life a bit easier:
\begin{lstlisting}[style=python]
PXY = np.array([[0.01, 0.02, 0.03, 0.1, 0.1],
[0.05, 0.1, 0.05, 0.07, 0.2],
[0.1, 0.05, 0.03, 0.05, 0.04]])
\end{lstlisting}
\begin{enumerate}[(A)]
\item What is the \href{https://en.wikipedia.org/wiki/Entropy_(information_theory)}{entropy}~$H(X)$?
\item What is the \href{https://en.wikipedia.org/wiki/Entropy_(information_theory)}{entropy}~$H(Y)$?
\item What is the \href{https://en.wikipedia.org/wiki/Conditional_entropy}{conditional entropy}~$H(X \,|\, Y)$?
\item What is the \href{https://en.wikipedia.org/wiki/Conditional_entropy}{conditional entropy}~$H(Y \,|\, X)$?
\item What is the \href{https://en.wikipedia.org/wiki/Joint_entropy}{joint entropy}~$H(X, Y)$?
\item What is the \href{https://en.wikipedia.org/wiki/Mutual_information}{mutual information}~$I(X\,;\,Y)$? Compute it once using the PMF and then once using relationships between the quantities you used in (A)-(E) to verify your answer.
\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 6 April 2021 -- S21 Initial version
\end{itemize}
% \includepdf[pages=-]{mynotebook.pdf}
\end{document}