%&pdflatex
\documentclass[a4paper,11pt]{article}
\usepackage{amsmath,amsfonts}
\DeclareMathOperator{\Tr}{Tr}
\usepackage[margin=2.5cm]{geometry}




\begin{document}

%+Title
\title{Statistical Inference and Learning- Ex-5}
\author{Yiqing Wang and Boaz Nadler}
\date{Due by Thursday Feb. 4, 2016}
\maketitle
%-Title

\begin{description}
\item{Q1.} Let $X$ be a $\mathbb{R}^p$-valued random column vector. Let us denote its mean $\mu = \mathbb{E}[X]$ and its covariance matrix $\Sigma = \mathbb{E} [(X-\mu)(X-\mu)^T]$. We assume for simplicity that the covariance matrix's eigenvalues $(\lambda_i)_{1\leq i\leq p}$ are distinct, that is,  $\lambda_i \neq \lambda_j$ for all $i\neq j$. Their associated column eigenvectors are denoted by $(v_i)_{1\leq i\leq p}$. In the following questions, we assume $\mu = 0$ until stated otherwise.


1. Show that the covariance matrix is positive semidefinite, that is, $\forall y \in \mathbb{R}^p$, $y^t \Sigma y \geq 0$.

2. Show that for all $1 \leq i, j \leq p$, $\mathbb{E} [(X^T v_i) (X^T v_j)] = \lambda_i 1_{i=j}$.

3. Show that $\mathbb{E} \|X\|^2 = \Tr (\Sigma)$ where $\|X\|^2 = \sum_{i=1}^p X_i^2$ and $\Tr(\Sigma) = \sum_{i=1}^p \Sigma_{i,i}$ (Hint: Show that $\Tr(\Sigma)=\sum \lambda_i$). 

4. Show that for all $1\leq k \leq p-1$, $\mathbb{E} \|X - \sum_{i=1}^k (X^T v_i)v_i\|^2 = \sum_{i=k+1}^p \lambda_i$.

5. Let \(\hat\Sigma_n=\frac1n \sum_{i=1}^n x_i x_i^T\) be an estimate of $\Sigma$ from $n$ samples $x_1,\ldots,x_n\in\mathbb{R}^p$. Suppose that $\Sigma$ is invertible with smallest eigenvalue $\lambda_p>0$. Suppose that $n<p$ (namely we have fewer observations that the dimension). Show that $\hat\Sigma_n$ is not invertible and that $\|\hat\Sigma_n-\Sigma\|\geq \lambda_p$, namely when $n<p$, $\hat\Sigma_n$ is in general far from $\Sigma$ (Hint: what is the rank of $\hat\Sigma_n$ ?).   

6. We now drop the assumption $\mu = 0$ and seek to estimate the covariance matrix from its $n$ i.i.d. samples $(x_1, \ldots, x_n) \in \mathbb{R}^{p \times n}$. Show that with their sample mean defined as $\hat{\mu}_{n} = \frac{1}{n}\sum_{i=1}^n x_i$, the following estimator
\begin{align*}
\hat{\Sigma}_n = \frac{1}{n-1}\sum_{i=1}^n(x_i - \hat{\mu}_{n}) (x_i - \hat{\mu}_{n})^t
\end{align*}
is unbiased, namely,
\begin{align*}
\mathbb{E} [\hat{\Sigma}_n] = \Sigma. 
\end{align*}
\end{description}

\begin{description}
\item{Q2.} In this exercise you will apply principal component analysis on actual data. The file \texttt{stock\_data.mat} contains, in matlab format, the following matrices: \texttt{A} of size $1258\times 31$, with the daily stock prices of 31 different companies traded in the United States. The list of stocks appears in the variable \texttt{stock\_list}. The matrix \texttt{B} of size $31\times 1257$ where $B_{i,t}=100\times (A_{t+1,i}-A_{t,i})/A_{t,i}$. Namely, it contains the daily returns of the 31 different stocks. The matrix \texttt{B\_mc} is the mean-centered version of \texttt{B}. 

To load the data into the matlab workspace simply type \texttt{load stock\_data.mat}.

The files A.txt, B.txt and stock\_list.txt are text files with the same data (in case you are using some other software to analyze it). 

(a) Compute the sample covariance matrix $S_n$ of the 31 companies, and the sample correlation matrix $R_n$ of the 31 companies. The latter can be computed as $D S_n D$ where $D=diag(1./sqrt(S_n))$. 

Plot the two matrices, in matlab this can be done via \texttt{figure(1); imagesc(S\_n)} and similarly for $R_n$. Can you see interesting structure in one or both of these matrices ?\ Is there structure apparent in one that is less apparent in the other ?\ Explain your answer. 

(b) Let us first look at only 2 specific companies, indices 4 and 5 in the stock list. These are \texttt{DUK} and \texttt{ED}. \texttt{DUK} is the ticker symbol of Duke company -  operates as an energy company in the United States and Latin America. \texttt{ED} stands for Consolidated Edison.
It engages in regulated electric, gas, and steam delivery businesses in the United States. It offers electric services to approximately 3.4 million customers in New York City and Westchester County. 

Plot the daily return prices of these two companies one against the other, namely\\
 \texttt{plot(B(4,:),B(5,:),'bo')}. What do you see ? How correlated are these two different companies ?\  

(c) Compute the eigenvalues and eigenvectors of $S_n$, namely the principal components of the data matrix $B$ containing all 31 stocks. Note that in matlab this can be directly computed from $B$ via

\centerline{\texttt{[coeff, score, latent] = pca(B);}} 
where \texttt{latent} are the eigenvalues, and \texttt{coeff} is a $31\times 31$ matrix whose columns are the principal components. 

Plot the eigenvalues. What do you see? How much of the overall variability is explained by the first principal component ?

(c) Typically in PCA, people look at the top principal components. However, sometimes one may find interesting things in the smallest ones instead. Plot the eigenvector that corresponds to the {\em smallest} eigenvalue. What do you see? Look at the corresponding companies where the entries of this eigenvector are significantly different from zero. Which are they and how does it explain the structure of this eigenvector?  
\end{description}

\begin{description}
\item{Q3.} Let \(f=(f_{1},f_2,\ldots,f_m)\) be a vector whose entries are all strictly positive. Consider the following Markov chain $(X_n)_{n\geq 1}$ on the finite states $\{1, \cdots, m\}$ whose transition matrix is
\begin{align*}
p(i, j) = 
\begin{cases}
\frac{1}{m} \min\left(1, \frac{f_j}{f_i}\right), \quad &i \neq j \\
1- \frac{1}{m}\sum_{j\neq i} \min\left(1, \frac{f_j}{f_i}\right), &i = j.
\end{cases}
\end{align*}

1. Show that the Markov chain that corresponds to the matrix \(P\) is irreducible and aperiodic.

2. Show that its stationary distribution $\pi$ is proportional to $f$. Hint: prove that the condition $\pi(i)p(i, j) = \pi(j)p(j, i)$ holds.

3. Let $m = 50$ and $f_j = 2+ \sin(\pi j/100)$. Simulate the Markov chain for  $10, 000$ consecutive steps and plot the histogram of the observed chain in the \(m\) states. 

\end{description}


\end{document}


