\documentclass{article}

%##############################################################################
% Environments
%##############################################################################

\usepackage{palatino}
\usepackage{amsmath,amssymb,amsthm,amsfonts}

\usepackage{hyperref}
\usepackage{fullpage}
\usepackage{mdframed}
\usepackage{natbib}

\usepackage{cancel}
\usepackage{centernot}
\usepackage{color,xcolor}
\usepackage{enumerate,enumitem}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{tikz}
\usepackage[a4paper,margin=1in]{geometry}

\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{COMP3314, Autumn 2023}
\rhead{Instructor: Lingpeng Kong}

\newtheorem{theorem}{Theorem}[]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{property}[theorem]{Property}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}[theorem]{Example}
\newtheorem*{remark}{Remark}
\newtheorem*{hint}{Hint}
\newtheorem{exercise}[theorem]{Exercise}

\newcommand\numberthis{\addtocounter{equation}{1}\tag{\theequation}}
% arguments adapted from https://github.com/dustinvtran/latex-templates
\newtheoremstyle{box}
                {3pt}% Space above
                {3pt}% Space below
                {}% Body font
                {}% Indent amount
                {\bfseries}% Theorem head font
                {\\*[3pt]}% Punctuation after theorem head
                {.5em}% Space after theorem head
                {}% Theorem head spec (can be left empty, meaning `normal')
\theoremstyle{box}
\newmdtheoremenv[skipabove=\topsep,skipbelow=\topsep]{problem}{Problem}
\newmdtheoremenv[backgroundcolor=black!3,skipabove=\topsep,skipbelow=\topsep]{answer}{Answer}

%##############################################################################
% Main Text Here
%##############################################################################

\title{Quiz \#1\vspace{-1.5em}}
\author{}
\date{\textbf{Due}: Oct. 11, 2023 at 10 p.m.\vspace{1.5em}}

\begin{document}
\maketitle
\thispagestyle{fancy}
In this quiz, we list some problems that help lead you to quickly review some fundamentals of probability and algebra, which could be useful for future quizzes, programming exercises and exams. To submit your assignment, please upload to moodle a pdf file containing your write-up, which can be either
\begin{itemize}
    \item \textbf{written by hand and scanned to pdf format}, or
    \item \textbf{typed via \LaTeX with the provided template file}.
\end{itemize}
For the duration of this course, each student is allocated a total of \textbf{three slip days} for assignment submissions. These slip days are designed to accommodate any personal emergencies or unforeseen circumstances. You can choose to use these days to extend the deadline for any assignment without incurring a penalty on your grade. However, the combined usage of slip days for all assignments cannot exceed three days. \textbf{If you have used up all three slip days and submit an assignment late, you will receive a score of 0 for that assignment.}
\vspace{1.5em}

% \begin{problem}[15 points, Bayes’ rule]
%     Albus Dumbledore believes that the Dark Lord somehow survived after his death spell bounced off on the historical night of October 31st 1981. While prophecies about the Dark Lord surviving that night are ambiguous, the Dark Mark on the hand of Severus Snape is a real piece of evidence. One would expect it to fade after the fall of the Dark Lord, but is this a sufficient evidence? Is it that unlikely for a magical mark to stay around after the maker dies? \\


% \noindent Suppose that, if the Dark Lord dies, the Dark Mark continues to exist with twenty percent probability. On the other hand, if the Dark Lord’s sentience lives on, the Dark Mark will stay with one hundred percent chance. Additionally, let’s stay the prior odds were a hundred-to-one against the Dark Lord surviving. Given that the Severus Snape’s Dark Mark has not faded, what is the probability of Dark Lord being alive?
    
% \end{problem}

\begin{answer} [15 points, Bayes' rule]
Box $1$ contains $1000$ light bulbs of which $10\%$ are defective. Box $2$ contains $2000$ light bulbs of which $5\%$ are defective.
    \begin{enumerate}
        \item (10 points) Suppose a box is given to you at random and you randomly select a lightbulb from the box. If that lightbulb is defective, what is the probability that you chose from Box $1$?
        \item (5 points) Suppose now that a box is given to you at random and you randomly select two lightbulbs from the box. If both lightbulbs are defective, what is the probability that you chose from Box $1$?
    \end{enumerate}
\end{answer}

\begin{answer}[35 points, Moments of a Distribution]
Prove the following results:
    \begin{enumerate}[start=1]
        \item (10 points) Assume $X$ and $Y$ are independent of each other, i.e. $P(XY)=P(X)P(Y)$. Show that $\mathbb{E}[XY] = \mathbb{E}[X]\mathbb{E}[Y]$ and  $\operatorname{var}[X + Y] = \operatorname{var}[X] + \operatorname{var}[Y]$ .
        \item (5 points) Consider two variables $X$ and $Y$, show that $\mathbb{E}[X] =\mathbb{E}_Y\left[\mathbb{E}_X[X \mid Y]\right]$.
        \item (5 points) Consider a random variable $X$, prove that $\mathbb{E}(X^2) \geq \mathbb{E}(X)^2$.

        \item  (10 points) Consider a nonnegative random variable $X$ and $a>0$ show that $P[X\geq a]\leq \frac{\mathbb{E}[X]}{a}$. 
        
        \begin{remark}
        This property implies an important theorem: \textbf{Markov's Inequality.} It gives an upper bound for the probability that a non-negative function of a random variable is greater than or equal to some positive constant, e.g. Markov's inequality shows that no more than 1/5 of the population can have more than 5 times the average income.
        \end{remark}
                    
        \item (5 points) The \emph{covariance} of two random variables $X$ and $Y$, which describes the degree to which $X$ and $Y$ are related, is defined as $\operatorname{Cov}(X,Y) = \mathbb{E}\left[\left(X - \mathbb{E}\left[X\right]\right) \left(Y - \mathbb{E}\left[Y\right]\right)\right]$.  Suppose we have two random variables $X$ and $Y$ such that $\operatorname{var}[X] = \operatorname{var}[Y]$ (i.e., they have the same variance). Let us denote $P = X + Y$ and $Q = X - Y$. Clearly $P$ and $Q$ are dependent since they both depend on the values of $X$ and $Y$. Show that $\operatorname{Cov}(P,Q) = 0$.

\begin{remark}
Although two independent random variables have 0 covariance, 0 covariance does not necessarily imply independence; this is due to that covariance can only describe a limited range of relationships between two rv's and fail to characterize much more complicated dependencies. 
\end{remark}
\end{enumerate}
\end{answer}


\begin{answer}[25 points, Maximum Likelihood Estimation]
Let $X_1, \cdots , X_n \in \mathbb{R}$ be $n$ sample points drawn independently from univariavte normal distributions such that $X_i\sim N(\mu,\sigma_i^2)$, where $\sigma_i = \sigma/\sqrt{i}$ for some parameter $\sigma$. (Every sample point comes from a distribution with a \textbf{different variance}.) Note the word "univariate; we are working in demision $d=1$ and our point are real numbers.
\begin{enumerate}
    \item (10 points) Derive the maximum likelihood estimates, denoted $\hat{\mu}$ and $\hat{\sigma}$, for the mean µ and the parameter $\sigma$. You may write an expression for $\hat{\sigma}^2$ rather than $\hat{\sigma}$ if you wish—it’s probably simpler that way. Show all your work.
    \item (5 points) Given ther true value of a statistic $\theta$ and a estimator $\hat{\theta}$ of that statistic, we define the $bias$ of the estimator to be the expected difference from the true value. That is,
    \begin{align}
        bias(\hat{\theta}) = E[\hat{\theta}]-\theta
    \end{align}
    We say that an estimator is $unbiased$ if its bias is $0$.
    Either \textbf{prove} or \textbf{disprove} the following statement: \textit{The MLE sample estimator $\hat{\mu}$ is unbiased, that is, $bias(\hat\mu)=0$.}
    
    \textit{Hint: Neither the true $\mu$ nor true $\sigma^2$ are known when estrimating sample statustics, thus we need to plug in appropiate estimators.}
    \item (10 points) Either \textbf{prove} or \textbf{disprove} the following statement: \textit{The MLE sample estimator $\hat{\sigma}^2$ is unbiased, that is, $bias(\hat\sigma^2)=0$.}
    
    \textit{Hint: Neither the true $\mu$ nor true $\sigma^2$ are known when estrimating sample statustics, thus we need to plug in appropiate estimators.}
\end{enumerate}

\end{answer}


% \begin{problem}[25 points, Maximum Likelihood Estimation]

% On interview day, my two colleagues and I asked prospective students the courses they have taken until we found someone who hadn't taken a machine learning course. We had to ask 23, 18, 46
% people respectively before finding someone who hadn't taken a machine learning course. What is the maximum
% likelihood estimate for the percentage of students that have taken a machine learning course? 

% \begin{remark}
%     You can model this problem with a geometric distribution. Let $p$ be the percentage of students that have taken a machine learning course. Then the probability of meeting $N$ students is $p^{N-1}(1-p)$. 
% \end{remark}
    
% \end{problem}


\begin{answer}[25 points, Activation Functions]
In this problem we mainly focus on properties of the sigmoid function
\begin{equation}
    \sigma(x) = \frac{1}{1 + e^{-x}}.
\end{equation}
\begin{enumerate}[start=1]
    \item (5 points) Show that $\sigma(x) + \sigma(-x) = 1$.
    \item (5 points) Show that $\frac{d}{d x}\sigma(x) = \sigma(x) (1 - \sigma(x))$.
    \item (5 points) Calculate $\frac{\partial \sigma(kx+b)}{\partial x}, \frac{\partial \sigma(kx+b)}{\partial k}, \text{ and } \frac{\partial \sigma(kx+b)}{\partial b}$
    \item (10 points) The sigmoid function is often used to constrain the input into the range $(0,1)$. There are other constraining functions, one of which is the \emph{tanh} function
\begin{equation}
    \operatorname{tanh}(x) = \frac{e^{x} - e^{-x}}{e^{x} + e^{-x}}.
\end{equation}
    Tanh function squashes the input $x \in \mathbb{R}$ into $(-1, 1)$, which is more suitable if we want the output range to be symmetric around 0.
    Show that $\operatorname{tanh}(x) = 2\sigma(2x) -1$.
\end{enumerate}
\end{answer}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% you can un-comment the following code and input your answer. If you are new to LaTeX, a good starting point is to use Overleaf, which is a website running in your browser and helps you set up LaTeX. There is a good tutorial (https://www.overleaf.com/learn/latex/Learn_LaTeX_in_30_minutes) on Overleaf, which guides you to have a good knowledge of LaTeX basics. 
% For your answer, most math symbols can be found in the problem text or googled :)

% \begin{answer}
% \end{answer}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{document}