\documentclass[11pt]{article}
\usepackage{fullpage,url}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
%\usepackage{latexsym}
%\usepackage{bbm}

\usepackage[letterpaper,top=1in,bottom=1in,left=1in,right=1in,nohead]{geometry}

\setlength{\parindent}{0in}
\setlength{\parskip}{6pt}



\newcommand{\s}[1]{\textsf{#1}}
\renewcommand{\c}[1]{\ensuremath{\EuScript{#1}}}
\renewcommand{\b}[1]{\ensuremath{\mathbb{#1}}}
\renewcommand{\Pr}{\textbf{\s{Pr}}}
\newcommand{\E}{\textbf{\s{E}}}
\newcommand{\Var}{\textbf{\s{Var}}}
\newcommand{\rank}{\ensuremath{\mathsf{rank}}}
\renewcommand{\span}{\ensuremath{\mathsf{span}}}
\newcommand{\diag}{\ensuremath{\mathsf{diag}}}




\begin{document}
\thispagestyle{empty}
{\large{\bf CS 3190: Foundations of Data Analysis \hfill Due: Tuesday 9.27 at 11:50pm}}\\

{\LARGE{\bf Homework 2: Convergence and Linear Algebra}}

\noindent\rule[0.5ex]{\linewidth}{1pt}

{\bf Instructions:} Your answers are due {\color{red} at 11:50pm} submitted on canvas. 
You {\color{red} must turn in a pdf through} canvas.  I recommend using latex (\url{http://www.cs.utah.edu/~jeffp/teaching/latex/}, see also \url{http://overleaf.com}) for producing the assignment answers.  If the answers are too hard to read you will lose points, entire questions may be given a $0$
(e.g. \textbf{sloppy pictures with your phone's camera are not ok, but very careful ones are}) 

Please make sure your name appears at the top of the page. 

You may discuss the concepts with your classmates, but write up the answers entirely on your own.   {\bf Be sure to show all the work involved in deriving your answers! If you just give a final answer without explanation, you may not receive credit for that question.}


\noindent\rule[0.5ex]{\linewidth}{1pt}


\begin{enumerate}


\item \textbf{[35 points]}
Consider a pdf $f$ so that a random variable $X \sim f$ has expected value $\E(X) = 10$ and variance $\Var(X) = 1.5$. Now consider $n = 10$ iid random variables $X_1,X_2,\dots,X_{10}$ drawn from $f$. Let $\bar{X} = \frac{1}{10} \sum_{i=1}^{10} X_i$
\begin{enumerate}
\item What is $\E(\bar{X})$?
\item What is $\Var(\bar{X})$?
\item Given the information we have so far, which of the Concentration of Measure inequalities (Markov, Chebyshev, Chernoff-Hoeffding) can be applied?  \emph{Explain why.}

Assume we know $X$ is never smaller than $3$ and never larger than $17$
\item Use Markov inequality to upper bound $\Pr(\bar{X} > 15)$
\item Use Chebyshev inequality to upper bound $\Pr(\bar{X} > 15)$
\item Use Chernoff-Hoeffding inequality to upper bound $\Pr(\bar{X} > 15)$
\item Now suppose $n = 100$. Calculate the 3 bounds again. For this part, also make sure to report the \textit{name} of the inequality that gives the tightest bound, the second tightest bound, and the third tightest bound respectively.
\end{enumerate}


\item \textbf{[15 points]}
Let $X$ be a random variable that you know is in the range $[-2,3]$ and you know has expected value of $\E(X) = .5$ and $\Var(X) = .02$.  \emph{(Hint:  This question is about how to apply concentration of measure inequalities under change of variables)}
\begin{enumerate}
	\item Use the Markov Inequality to upper bound $\Pr(X > 1)$ 
	\item Let $Y = 2X-1$. Use Chebyshev's inequality to bound $\Pr(Y > 2)$
\end{enumerate}




\item \textbf{[25 points]}
Consider the following $2$ vectors in $\mathbb{R}^3$:
\begin{eqnarray*}
p &=& (1,  2, \texttt{x})
\\
q &=&(\texttt{y}, 4, \texttt{2x})
\end{eqnarray*}
Report the following:
\begin{enumerate}
\item Choose the value $\texttt{y}$ so that regardless of the value of $\texttt{x}$, $p$ and $q$ are linearly dependent
\item Choose the value $\texttt{y}$ as a function of $\texttt{x}$ so that $p$ and $q$ are orthogonal
\item if $\texttt{x} = 1$, then choose a single value of $\texttt{y}$ so that $p$ and $q$ are neither linearly dependent nor orthogonal
\item Calculate $\|p\|_1$ if $\texttt{x} = 1$
\item Calculate $\|p\|_2^2$ if $\texttt{x} = 1$
\end{enumerate}



\item \textbf{[25 points]}
Consider the following $3$ matrices:
\[
A = \left[\begin{array}{ccc} 1 & -2 & -1 \\ -2 & 3 & 1\end{array}\right]
\;\;\;
B = \left[\begin{array}{ccc} 3 & 5 & 2 \\ 3 & 2 & -3 \\  3& 3 & 5 \end{array}\right]
\;\;\;
C = \left[\begin{array}{ccc} 0 & 2 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 4 \end{array}\right]
\]
Report the following (it is intended that you use Python for this question):
\begin{enumerate}
\item $AB$
\item $B+C^T$
\item Which matrices are full rank?  
\item $\|C\|_F$
\item $C^{-1}$
\end{enumerate}




\end{enumerate}

\end{document}
