CSE 546 hw template

homework.sty

\usepackage{fancyhdr}
\usepackage{extramarks}
\usepackage{amsmath}
%\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{tikz}
\usepackage[plain]{algorithm}
\usepackage{algpseudocode}
\usepackage{physics}
\usepackage{xargs}
\usepackage[thmmarks, amsmath, thref]{ntheorem}

\usetikzlibrary{automata,positioning}

%
% Basic Document Settings
%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass: \hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}

\setlength\parindent{0pt}

\newcommand{\enterProblemHeader}[2]{
    \nobreak\extramarks{}{Problem \Alph{#1}.\arabic{#2} continued on next page\ldots}\nobreak{}
    \nobreak\extramarks{Problem \Alph{#1}.\arabic{#2} (continued)}{Problem \Alph{#1}.\arabic{#2} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitProblemHeader}[2]{
    \nobreak\extramarks{Problem \Alph{#1}.\arabic{#2} (continued)}{Problem \Alph{#1}.\arabic{#2} continued on next page\ldots}\nobreak{}
    \stepcounter{#2}
    \nobreak\extramarks{Problem \Alph{#1}.\arabic{#2}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\newcounter{homeworkSectionCounter}
\setcounter{homeworkSectionCounter}{1}

\nobreak\extramarks{Problem \arabic{homeworkProblemCounter}}{}\nobreak{}

\newenvironmentx{homeworkProblem}[2][1=-1,2=-1]{
    \ifnum#1>0
        \setcounter{homeworkSectionCounter}{#1}
    \fi
    \ifnum#2>0
        \setcounter{homeworkProblemCounter}{#2}
    \fi
    \section{Problem \Alph{homeworkSectionCounter}.\arabic{homeworkProblemCounter}}
    \setcounter{partCounter}{1}
    \enterProblemHeader{homeworkSectionCounter}{homeworkProblemCounter}
}{
    \exitProblemHeader{homeworkSectionCounter}{homeworkProblemCounter}
}

%
% Homework Details
%   - Title
%   - Due date
%   - Class
%   - Section/Time
%   - Instructor
%   - Author
%

\newcommand{\hmwkDueTime}{11:59pm}
\newcommand{\hmwkClass}{CSE 546}
\newcommand{\hmwkClassInstructor}{Prof. Kevin Jamieson and Prof. Jamie Morgenstern}
\newcommand{\hmwkAuthorName}{\textbf{Sam Tay}}

%
% Title Page
%

\title{
    \vspace{2in}
    \textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
    \normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate\ at \hmwkDueTime}\\
    \vspace{0.1in}\large{\textit{\hmwkClassInstructor}}
    \vspace{3in}
}

\author{\hmwkAuthorName}
\date{}

\renewcommand{\part}[1]{
  \vspace{0.1in}
  \textbf{(\alph{partCounter})}
  \stepcounter{partCounter}
}

%
% Various Helper Commands
%
\newcommand\numberthis{\addtocounter{equation}{1}\tag{\theequation}}

% Useful for algorithms
\newcommand{\alg}[1]{\textsc{\bfseries \footnotesize #1}}

% Solution environments
\theoremstyle{nonumberplain} % or nonumberbreak to skip line
%\theoremheaderfont{\itshape} % uncomment for bold
\theoremseparator{.}
\theorembodyfont{\upshape}
\theoremsymbol{\ensuremath{\blacksquare}} % or \square for hollow
\newtheorem{solution}{Solution}

% Probability commands: Expectation, Variance, Covariance, Bias
\newcommand{\E}{\mathop{{}\mathbb{E}}}
\renewcommand{\P}{\mathop{{}\mathbb{P}}}
\newcommand{\Var}{\operatorname{Var}}
\newcommand{\Cov}{\operatorname{Cov}}
\newcommand{\Bias}{\operatorname{Bias}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\1}{\mathbf{1}}
\newcommand{\mat}[1]{\boldsymbol{#1}} % matrix

solutions.tex

\documentclass{article}
\usepackage{../homework}

\newcommand{\hmwkTitle}{Homework\ \#0}
\newcommand{\hmwkDueDate}{April 8, 2020}

\begin{document}

\maketitle
\pagebreak

\begin{homeworkProblem}[1][1]
After your yearly checkup, the doctor has bad news and good news. The bad news
is that you tested positive for a serious disease, and that the test is 99\%
accurate (i.e., the probability of testing positive given that you have the
disease is 0.99, as is the probability of testing negative given that you dont
have the disease). The good news is that this is a rare disease, striking only
one in 10,000 people. What are the chances that you actually have the disease?
(Show your calculations as well as giving the final result.)

\begin{solution}
\end{solution}
\end{homeworkProblem}

\begin{homeworkProblem}
For any two random variables $X,Y$ the \emph{covariance} is defined as
$\text{Cov}(X,Y)=\E[(X-\E[X])(Y-\E[Y])]$. You may assume $X$ and $Y$ take on a
discrete values if you find that is easier to work with.

\part

If $\E[Y|X=x] = x$ show that $\text{Cov}(X,Y) = \E[(X-\E[X])^2]$.

\part

If $X,Y$ are independent show that $\text{Cov}(X,Y)=0$.

\end{homeworkProblem}

\begin{homeworkProblem}
Let $X$ and $Y$ be independent random variables with PDFs given by $f$ and $g$,
respectively. Let $h$ be the PDF of the random variable $Z = X+Y$.

\part

Show that $h(z) = \int_{-\infty}^\infty f(x) g( z - x ) d x $.

\part

If $X$ and $Y$ are both independent and uniformly distributed on $[0,1]$ (i.e.
$f(x)=g(x)=1$ for $x \in [0,1]$ and $0$ otherwise) what is $h$, the PDF of
$Z=X+Y$?

\end{homeworkProblem}

\begin{homeworkProblem}
A random variable $X \sim \mathcal{N}(\mu, \sigma^2)$ is Gaussian distributed
with mean $\mu$ and variance $\sigma^2$. Given that for any $a,b \in \R$, we
have that $Y = aX + b$ is also Gaussian, find $a,b$ such that $Y \sim
\mathcal{N}(0,1)$.
\end{homeworkProblem}

\begin{homeworkProblem}
For a random variable $Z$, its mean and variance are defined as $\E[Z]$ and
$\E[(Z-\E[Z])^2]$, respectively. Let $X_1,\dots,X_n$ be independent and
identically distributed random variables, each with mean $\mu$ and variance
$\sigma^2$.  If we define $\widehat{\mu}_n = \frac{1}{n} \sum_{i=1}^n X_i$, what
is the mean and variance of $\sqrt{n}(\widehat{\mu}_n - \mu)$?
\end{homeworkProblem}

\begin{homeworkProblem}
If $f(x)$ is a PDF, the cumulative distribution function (CDF) is  defined as
$F(x) = \int_{-\infty}^x f(y) dy$.  For any function $g : \R \rightarrow \R$
and random variable $X$ with PDF $f(x)$, recall that the expected value of
$g(X)$ is defined as $\E[g(X)] = \int_{-\infty}^\infty g(y) f(y) dy$. For a
boolean event $A$, define $\1\{ A \}$ as $1$ if $A$ is true, and $0$
otherwise. Thus, $\1\{ x \leq a \}$ is $1$ whenever $x \leq a$ and $0$
whenever $x > a$.  Note that $F(x) = \E[\1\{X \leq x\}]$.  Let $X_1,\dots,X_n$
be \emph{independent and identically distributed} random variables with CDF
$F(x)$.  Define $\widehat{F}_n(x) = \frac{1}{n} \sum_{i=1}^n \1\{X_i \leq
  x\}$. Note, for every $x$, that $\widehat{F}_n(x)$ is an \emph{empirical
estimate} of  $F(x)$. You may use your answers to the previous problem.

\part

For any $x$, what is $\E[ \widehat{F}_n(x) ]$?

\part

For any $x$, the variance of $\widehat{F}_n(x)$ is $\E[ ( \widehat{F}_n(x) -
F(x) )^2 ]$.  Show that $\textrm{Variance}(\widehat{F}_n(x)) =
\frac{F(x)(1-F(x))}{n}$.
% (Hint: Consider what independence implies.)

\part

Using your answer to b, show that for all $x\in \R$, we have
$\displaystyle \E[ ( \widehat{F}_n(x) - F(x) )^2 ] \leq \tfrac{1}{4n}$.

\end{homeworkProblem}

\begin{homeworkProblem}[2][1]
Let $X_1,\dots,X_n$ be $n$ independent and identically distributed random
variables drawn unfiromly at random from $[0,1]$. If $Y = \max\{X_1,\dots,X_n\}$
then find $\E[Y]$.
\end{homeworkProblem}

\begin{homeworkProblem}[1][7]
Let $A = \begin{bmatrix} 1 & 2 & 1 \\ 1 & 0 & 3 \\ 1 & 1 & 2 \end{bmatrix}$ and
$B = \begin{bmatrix} 1 & 2 & 3 \\ 1 & 0 & 1 \\ 1 & 1 & 2 \end{bmatrix}$.
For each matrix $A$ and $B$,

\part

what is its rank?

\part

what is a (minimal size) basis for its column span?

\end{homeworkProblem}

\begin{homeworkProblem}
Let $A = \begin{bmatrix} 0 & 2 & 4 \\ 2 & 4 & 2 \\ 3 & 3 & 1 \end{bmatrix}$,
$b = \begin{bmatrix} -2 & -2 & -4 \end{bmatrix}^T$,
and $c=\begin{bmatrix} 1 & 1 & 1 \end{bmatrix}^T$.

\part

What is $Ac$?

\part

What is the solution to the linear system $Ax = b$? (Show your work).

\end{homeworkProblem}

\begin{homeworkProblem}
Assume $w$ is an $n$-dimensional vector and $b$ is a scalar. A hyperplane in
$\R^n$ is the set $\{x : x\in \R^n,\text{ s.t. } w^T x + b = 0\}$.

\part

Draw the hyperplane for $w=[-1,2]^T$, $b=2$? Label your axes.

\part

Draw the hyperplane for $w=[1,1,1]^T$, $b=0$? Label your axes.

\part

Given some $x_0 \in \R^n$, find the \emph{squared distance} to the hyperplane
defined by $w^T x + b=0$.
In other words, solve the following optimization problem:
\begin{align*}
  \min_x& \|x_0 - x \|^2\\
  \text{s.t. }&w^Tx +b = 0
\end{align*}
% Hint: if $\widetilde{x}_0$ is the minimizer of the above problem, note that $\|
% x_0 - \widetilde{x}_0 \| = | \frac{w^T(x_0 - \widetilde{x}_0)}{\|w\|} |$. What
% is $w^T \widetilde{x}_0$?

\end{homeworkProblem}

\begin{homeworkProblem}
For possibly non-symmetric $\mat{A}, \mat{B} \in \R^{n \times n}$ and
$c \in \R$, let $f(x, y) = x^T \mat{A} x + y^T \mat{B} x + c$.
Define $\nabla_z f(x,y) =
\begin{bmatrix}
      \frac{\partial f(x,y)}{\partial z_1}
    & \frac{\partial f(x,y)}{\partial z_2}
    & \dots
    & \frac{\partial f(x,y)}{\partial z_n}
\end{bmatrix}^T$.

\part

Explicitly write out the function $f(x, y)$ in terms of the components $A_{i,j}$
and $B_{i,j}$ using appropriate summations over the indices.

\part

What is $\nabla_x f(x,y)$ in terms of the summations over indices \emph{and}
vector notation?

\part

What is $\nabla_y f(x,y)$ in terms of the summations over indices \emph{and}
vector notation?

\end{homeworkProblem}

\begin{homeworkProblem}[2][2]
The \textit{trace} of a matrix is the sum of the diagonal entries;
$Tr(A) = \sum_i A_{ii}$. If $A\in\mathbb{R}^{n\times m}$ and
$B\in\mathbb{R}^{m\times n}$, show that $Tr(AB) = Tr(BA)$.
\end{homeworkProblem}

\begin{homeworkProblem}
Let $v_1,\dots,v_n$ be a set of non-zero vectors in $\mathbb{R}^d$. Let $V =
[v_1,\dots,v_n]$ be the vectors concatenated.

\part

What is the minimum and maximum rank of $\sum_{i=1}^n v_i v_i^T$?

\part

What is the minimum and maximum rank of $V$?

\part

Let $A \in \mathbb{R}^{D \times d}$ for $D > d$. What is the minimum and maximum
rank of $\sum_{i=1}^n (A v_i) (A v_i)^T$?

\part

What is the minimum and maximum rank of $AV$? What if $V$ is rank $d$?

\end{homeworkProblem}

\begin{homeworkProblem}[1][11]
For the $A, b, c$ as defined in Problem 8, use NumPy to compute (take a screen
shot of your answer):

\part

What is $A^{-1}$?

\part

What is $A^{-1}b$? What is $Ac$?

\end{homeworkProblem}

\begin{homeworkProblem}
Two random variables $X$ and $Y$ have equal distributions if their CDFs, $F_X$
and $F_Y$, respectively, are equal, i.e. for all $x$, $ |F_X(x) - F_Y(x)| =
0$.  The central limit theorem says that the sum of $k$ independent,
zero-mean, variance-$1/k$ random variables converges to a (standard) Normal
distribution as $k$ goes off to infinity.    We will study this phenomenon
empirically (you will use the Python packages Numpy and Matplotlib).  Define
$Y^{(k)} = \frac{1}{\sqrt{k}} \sum_{i=1}^k B_i$ where each $B_i$ is equal to
$-1$ and $1$ with equal probability. From your solution to problem 5, we know
that $\frac{1}{\sqrt{k}} B_i$ is zero-mean and has variance $1/k$.

\part

For $i=1,\dots,n$ let $Z_i \sim \mathcal{N}(0,1)$. If $F(x)$ is the true CDF
from which each $Z_i$ is drawn (i.e., Gaussian) and
$\widehat{F}_n(x) = \frac{1}{n} \sum_{i=1}^n \1\{ Z_i \leq x)$,
use the answer to problem 1.5  above to choose
$n$ large enough such that, for all $x \in \R$,
$\sqrt{\E[ (\widehat{F}_n(x)-F(x))^2 ]} \leq 0.0025$,
and plot $\widehat{F}_n(x)$ from $-3$ to $3$.
% Hint: use
% \texttt{Z=numpy.random.randn(n)}
% to generate the random variables, and
% \texttt{import matplotlib.pyplot as plt};
% \texttt{plt.step(sorted(Z), np.arange(1,n+1)/float(n))} to plot.

\part

For each $k \in \{1, 8, 64, 512\}$ generate $n$
independent copies $Y^{(k)}$ and plot their empirical CDF on
the same plot as part a.
% Hint:
% $\texttt{np.sum(np.sign(np.random.randn(n, k))*np.sqrt(1./k), axis=1)}$
% generates $n$ of the $Y^{(k)}$ random variables.

% Always label axes
% Tip: seaborn package for plots
\end{homeworkProblem}

\end{document}