This page is meant to give you quick access to problems and their solutions. Refer to the original exam PDF, linked above, for test-taking instructions and formatting. Note that we’ve kept the problem text identical, which is why you may see things like “write your answer in the box below” despite there not being a box on this page.
Suppose we’d like to find the optimal constant prediction, \(w^{\ast}\), for the constant model \(h(x_i) = w\), given the following dataset of \(n = 4\) values.
$$ \begin{array}{l@{\hspace{1.75cm}}l} A = 3 & E = 7 \\\\[1.5ex] B = \dfrac{4}{\frac{1}{3} + \frac{1}{6} + \frac{1}{6} + \frac{1}{13}} \approx 5.37 & F = \sqrt{\dfrac{3^2 + 6^2 + 6^2 + 13^2}{4}} \approx 7.90 \\\\[3ex] C = 6 & G = 8 \\\\[1.5ex] D = \left( 3 \cdot 6 \cdot 6 \cdot 13 \right)^{1/4} \approx 6.12 & H = 13 \\\\ \end{array} $$
(3 pts) What value of \(w^{\ast}\) minimizes \(R(w) = \displaystyle \frac{1}{4} \sum_{i=1}^4 (y_i - w)^2\)?
\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
Solution
\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
For (i), the minimizer of mean squared error is the mean, so
$$ w^* = \frac{3+6+6+13}{4} = \boxed{7} $$
(3 pts) What value of \(w^{\ast}\) minimizes \(R(w) = \displaystyle \lim_{p \to \infty} \displaystyle \frac{1}{4} \sum_{i=1}^4 |y_i - w|^p\)?
\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
Solution
\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
For (ii), as \(p \to \infty\), the largest value of \(|y_i-w|\) dominates. So we should put \(w\) halfway between the smallest and largest data values, as discussed in Chapter 1.4.
$$ w^* = \frac{3+13}{2} = \boxed{8} $$
(3 pts) What value of \(w^{\ast}\) minimizes \(R(w) = \displaystyle \frac{1}{4} \sum_{i=1}^4 (\log(y_i) - \log(w))^2\)?
\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
Solution
\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
For (iii), let \(u=\log(w)\). The problem is now asking for the best constant prediction for the transformed values \(\log(y_i)\), so
(3 pts) The slope of the graph of \(R(w) = \displaystyle\frac{1}{4} \sum_{i = 1}^4 |y_i - w|\) at \(w = \alpha\) is \(-1/2\). Among the options above, which could be \(\alpha\)?
\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
Solution
\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
For (iv), the slope of mean absolute error at any \(w\) that is not a data point is
$$ \frac{\text{\# left of } w - \text{\# right of } w}{n} $$
Here, in order to achieve a slope of \(-1/2\), we need to have 1 data point to the left of \(w\) and 3 to the right, since \(\frac{1-3}{4} = -1/2\). This means we need \(w\) to be between \(3\) and \(6\), exclusive. The only value in this interval is \(B\),
Suppose a dataset of \(n\) points, \((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\), has the following properties:
$$ \text{mean of }y\text{-values} = \bar y = 11, \qquad \text{standard deviation of }x\text{-values} = \sigma_x = 2, \qquad \sigma_y = 6 $$
The simple linear regression line that minimizes mean squared error for predicting \(y_i\) from \(x_i\) is
$$ h(x_i) = 15 - x_i $$
a)
3 pts What is \(\bar x\), the mean of the \(x\)-values? Give your answer as a number with no variables.
\(\bar x = \_\_\_\_\_\_\)
Solution
The regression line must pass through \((\bar x, \bar y)\), so
$$ 11 = 15 - \bar x $$
This gives
$$ \bar x = \boxed{4} $$
Now, consider a new dataset, \((t_1, z_1), (t_2, z_2), \ldots, (t_n, z_n)\), defined by \(t_i = 5 - x_i\) and \(z_i = 2y_i - 1\).
Let \(g(t_i) = \beta_0^{\ast} + \beta_1^{\ast} t_i\) be the best simple linear regression line for predicting \(z_i\) from \(t_i\).
b)
6 pts Find \(\beta_0^{\ast}\), the intercept of the best simple linear regression line for predicting \(z_i\) from \(t_i\). Show your work, and write your final answer in the box provided. Your answer should be a number with no variables.
$$ \beta_0^* = \_\_\_\_\_\_ $$
Solution
First, use the original regression line to find the original correlation, which we’ll call \(r_{xy}\). The slope is \(-1\), so
Now, what is \(r_{tz}\)? Replacing \(x_i\) with \(t_i=5-x_i\) flips the sign of the correlation, while replacing \(y_i\) with \(z_i=2y_i-1\) keeps the sign the same. So the correlation between \(t_i\) and \(z_i\) is
$$ r_{tz} = \frac{1}{3} $$
Also,
$$ \bar t = 5-\bar x = 5 - 4 = 1, \qquad \bar z = 2\bar y - 1 = 2 \cdot 11 - 1 = 21 $$
Where did these facts come from? In general, if \(x_1, x_2, …, x_n\) have a mean of \(\bar x\) and a standard deviation of \(\sigma_x\), then \(a x_1 + b, a x_2 + b, …, a x_n + b\) have a mean of \(a \bar x + b\) and a standard deviation of \(|a| \sigma_x\). This was discussed in an early homework problem.
4 pts Let \(M\) be the mean squared error of the model \(h(x_i) = 15 - x_i\)’s predictions on the dataset \((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\), and \(M’\) be the mean squared error of the model \(g(t_i) = \beta_0^{\ast} + \beta_1^{\ast} t_i\)’s predictions on the dataset \((t_1, z_1), (t_2, z_2), \ldots, (t_n, z_n)\).
What is the value of the fraction \(\frac{M}{M’}\)? If it’s not clear, \(M’\) is on the denominator.
\(1/5\)\(1/4\)\(1/2\)\(1\)\(2\)\(4\)\(5\) Impossible to tell
Solution
\(1/5\)\(1/4\)\(1/2\)\(1\)\(2\)\(4\)\(5\) Impossible to tell
The intuitive answer is that since we’ve stretched out the \(y\)-values by a factor of \(2\), the mean squared error is multiplied by a factor of \(4\), so the fraction \(\frac{M}{M’}\) is \(\frac{1}{4}\).
Let’s show this a bit more formally. First, note that
5 pts Suppose \(\vec a = \begin{bmatrix} 0 \\ 3 \\ 6 \end{bmatrix}\) and that \(\vec b\) is another vector in \(\mathbb{R}^3\) such that:
\(\vec a\) and \(\vec b\) are orthogonal, and
the plane spanned by \(\vec a\) and \(\vec b\) is
$$ 4x - 2y + z = 0 $$
There are infinitely many possible vectors \(\vec b\) that satisfy the given conditions. State one of them. Show your work, and write your final answer in the box provided. Your answer should be a vector with no variables.
$$ \text{one possible }\vec b = \_\_\_\_\_\_ $$
Solution
Let \(\vec b = \begin{bmatrix} x \\ y \\ z \end{bmatrix}\).
Since \(\vec b\) lies in the given plane,
$$ 4x-2y+z=0 $$
Since \(\vec a\) and \(\vec b\) are orthogonal,
$$ \vec a \cdot \vec b = 3y+6z=0 $$
The second equation gives \(y=-2z\). Plugging this into the first equation gives
$$ 4x+4z+z=0 \implies x=-\frac{5}{4}z $$
There are infinitely many solutions for \(x\), \(y\), and \(z\); they all lie on a line. To state one, let’s just fix a value of \(z\). Arbitrarily choosing \(z = 4\) gives
$$ \vec b = \boxed{\begin{bmatrix}-5\\\\-8\\\\4\end{bmatrix}} $$
Here’s another solution: really, the question is asking for a vector that is orthogonal to both \(\vec a\) and \(\begin{bmatrix} 4 \\ -2 \\ 1 \end{bmatrix}\). Such a vector would be orthogonal to \(\vec a\) and would lie in the plane \(4x-2y+z=0\). So, all we need to do is take the cross product of \(\vec a\) and \(\begin{bmatrix} 4 \\ -2 \\ 1 \end{bmatrix}\).
Note that this is just \(-3\) times the vector we found above. Indeed, any scalar multiple of \(\begin{bmatrix} -5 \\ -8 \\ 4 \end{bmatrix}\) is also a solution.
b)
4 pts This part is unrelated to the previous part. Suppose \(\vec u, \vec v \in \mathbb{R}^n\), and that:
\(\vec u\) is a unit vector,
\(\cos(\theta) = 2/3\), where \(\theta\) is the angle between \(\vec u\) and \(\vec v\),
the projection of \(\vec v\) onto \(\vec u\) is \(6 \vec u\).
What is the value of \(\lVert \vec v \rVert\)?
\(1\)\(3\)\(4\)\(6\)\(9\)
Solution
\(1\)\(3\)\(4\)\(6\)\(9\)
Since \(\vec u\) is a unit vector,
$$ \vec p = \frac{\vec v \cdot \vec u}{\vec u \cdot \vec u} \vec u = (\vec v \cdot \vec u)\vec u $$
But this projection is also \(6 \vec u\), so
$$ \vec u \cdot \vec v = 6 $$
Now, let’s use the fact that \(\cos(\theta) = 2/3\), where \(\theta\) is the angle between \(\vec u\) and \(\vec v\), and plug in the values we know.
$$ \begin{align*} \cos \theta &= \frac{\vec u \cdot \vec v}{\lVert \vec u \rVert \lVert \vec v \rVert} \\\\ \frac{2}{3} &= \frac{6}{1 \cdot \lVert \vec v \rVert} \\\\ \lVert \vec v \rVert &= 9 \end{align*} $$
So, \(\boxed{\lVert \vec v \rVert = 9}\).
Problem 4 4 ptsMT1 Redemption
Let
$$ S = \left\{ \begin{bmatrix} x_1\\\\x_2\\\\x_3\\\\x_4\\\\x_5\\\\x_6 \end{bmatrix} \in \mathbb{R}^6 : x_1+x_2+x_3=0 \text{ and } x_4=x_5 \right\} $$
Find \(\dim(S)\). Give your answer as an integer with no variables.
\(\dim(S)=\_\_\_\_\_\_\)
Solution
There are \(6\) variables total. The condition
$$ x_1+x_2+x_3=0 $$
removes one degree of flexibility, and the condition
$$ x_4=x_5 $$
removes one flexibility. So
$$ \dim(S) = 6-2 = \boxed{4} $$
Another way to think about it is to think of what a basis for \(S\) looks like. Every vector in \(S\) is of the form
$$ \begin{bmatrix} a \\\\ b \\\\ -a-b \\\\ c \\\\ c \\\\ d \end{bmatrix} $$
where \(a, b, c, d\) are real numbers. \(a\) and \(b\) (components 1 and 2) can both be anything, but component 3 is automatically determined once \(a\) and \(b\) are chosen. Similarly, \(c\) and \(d\) (components 4 and 6) can both be anything, but once component 4 is chosen, component 5 is automatically determined.
\(S\) is the set of all vectors that fit the template above. But
$$ \begin{bmatrix} a \\\\ b \\\\ -a-b \\\\ c \\\\ c \\\\ d \end{bmatrix} = a \begin{bmatrix} 1 \\\\ 0 \\\\ -1 \\\\ 0 \\\\ 0 \\\\ 0 \end{bmatrix} + b \begin{bmatrix} 0 \\\\ 1 \\\\ -1 \\\\ 0 \\\\ 0 \\\\ 0 \end{bmatrix} + c \begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\\\ 1 \\\\ 0 \end{bmatrix} + d \begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 1 \end{bmatrix} $$
A key fact is that the row space and null space of a matrix are orthogonal complements, as discussed in Chapter 5.4 (and the linked video). What this means is that every row of \(A\) is orthogonal to every vector in \(\text{nullsp}(A)\).
So a row
$$ \begin{bmatrix} a & b & c & d & e \end{bmatrix} $$
must satisfy
$$ a+c = 0, \qquad b+c = 0, \qquad d+e = 0 $$
Equivalently, every row of \(A\) must have the form
$$ \begin{bmatrix} a & a & -a & d & -d \end{bmatrix} $$
The first, second, and fourth options all have this form. The third option,
So the correct answer is the third option, \(\boxed{\begin{bmatrix} 2 & 0 & -2 & 5 & -5 \end{bmatrix}}\).
c)
4 pts Let \(\vec a^{(1)}, \vec a^{(2)}, \vec a^{(3)}, \vec a^{(4)}, \vec a^{(5)} \in \mathbb{R}^6\) be the columns of \(A\).
Below, select one possible set of columns of \(A\) that form a basis for \(\text{colsp}(A)\). You should select the fewest possible number of columns needed to span \(\text{colsp}(A)\).
Since \(\text{rank}(A)=2\), the column space is 2-dimensional. A basis for the column space comes from picking one of \(\lbrace \vec a^{(1)}, \vec a^{(2)}, \vec a^{(3)} \rbrace\) and one of \(\lbrace \vec a^{(4)}, \vec a^{(5)} \rbrace\). There are therefore 6 possible options; one of them is
$$ \boxed{\{\vec a^{(1)}, \vec a^{(4)}\}} $$
Problem 6 12 ptsMT2 Redemption
Suppose \(X\) is an \(n \times 3\) matrix, where \(n > 2\), with columns \(\vec x^{(1)}\), \(\vec x^{(2)}\), and \(\vec x^{(3)}\). Furthermore, suppose that \(X = QR\), where
Lastly, suppose \(\vec y \in \mathbb{R}^n\) and \(Q^T \vec y = \begin{bmatrix} -2 \\ 10 \end{bmatrix}\).
a)
6 pts Let \(\vec p\) be the projection of \(\vec y\) onto \(\text{colsp}(X)\). Write \(\vec p\) as a linear combination of the columns of \(X\). Fill in each box with a number with no variables. If there are multiple correct answers, you only need to provide one.
The columns of \(Q\) are a basis for \(\text{colsp}(X)\) (since \(X = QR\) writes every column of \(X\) as a linear combination of the columns of \(Q\)). So, the general strategy is to first write \(\vec p\) as a linear combination of the columns of \(Q\), and then use the information in \(R\) to write that as a linear combination of the columns of \(X\).
If \(X\) is a full rank matrix, then the projection of \(\vec y\) onto \(\text{colsp}(X)\) is
$$ X (X^TX)^{-1}X^T \vec y $$
\(X\) isn’t full rank here, but \(Q\) is, and that is the matrix whose columns we’re writing \(\vec p\) as a linear combination of to begin with. So, we have
$$ \vec p = Q (Q^TQ)^{-1}Q^T \vec y $$
But, since \(Q\)’s columns are orthonormal, \(Q^TQ = I\), so
$$ \vec p = Q (Q^TQ)^{-1} Q^T \vec y = Q I Q^T \vec y = Q Q^T \vec y = Q \begin{bmatrix} -2 \\\\ 10 \end{bmatrix} = -2 \vec q^{(1)}+10 \vec q^{(2)} $$
Good, so now we have \(\vec p\) as a linear combination of the columns of \(Q\). How do the columns of \(X\) relate to the columns of \(Q\)? \(R = \begin{bmatrix} 2 & 0 & 2\\0 & 1 & -1 \end{bmatrix}\) tells us that
As discussed in Chapter 6.4, the full sete of minimizers results from taking one particular solution and adding any vector in \(\text{nullsp}(X)\). So, all we need to do is find a basis for \(\text{nullsp}(X)\).
Note that \(X\) has two linearly independent columns (\(\vec x^{(1)}\) and \(\vec x^{(2)}\)), with a third column defined by
The coefficients on the three vectors in the linear combination above are \(1\), \(-1\), and \(-1\). So, \(\begin{bmatrix} 1 \\ -1 \\ -1 \end{bmatrix}\) is in \(\text{nullsp}(X)\). Not only that, but it’s a basis for \(\text{nullsp}(X)\), since \(\text{rank}(X) = 2\) and thus \(\text{dim}(\text{nullsp}(X)) = 3-2 = 1\) (meaning any one vector in \(\text{nullsp}(X)\) is a basis for it). Another commonly chosen basis for \(\text{nullsp}(X)\) was \(\begin{bmatrix} -1 \\ 1 \\ 1 \end{bmatrix}\).
So, the full set of minimizers is
$$ \boxed{\left\{ \begin{bmatrix}-1\\\\10\\\\0\end{bmatrix} + t \begin{bmatrix}1\\\\-1\\\\-1\end{bmatrix} : t \in \mathbb{R} \right\}} $$
Problem 7 8 ptsMT2 Redemption
Suppose we’d like to fit a multiple linear regression model without an intercept term to predict an apartment’s monthly rent (in hundreds of dollars) using various features.
For apartment \(i\), the corresponding feature vector is \(\vec x_i = \begin{bmatrix} \text{bedrooms}_i & K_i & C_i & N_i \end{bmatrix}^T\), where \(\text{bedrooms}_i\) is the number of bedrooms in apartment \(i\), and \(K_i\), \(C_i\), and \(N_i\) are one hot encoded features for the Kerrytown, Central Campus, and North Campus neighborhoods, respectively.
The model is fit by minimizing mean squared error. All rows of the dataset are shown to the right. The model’s predictions, \(h(x_i)\), are shown, along with the true rents, \(y_i\). Several values are missing.
is \(\begin{bmatrix} 4 & 1 & 0 & 0 \end{bmatrix}\).
Find all four missing values in the table. Show your work, and write your final answers in the boxes provided. Your answers should be integers with no variables. Hint: Think about orthogonality.
Solution
For clarity, let’s start by writing out the full design matrix \(X\).
First, let’s take the dot product of the error vector with the second column of \(X\), the one hot encoded column for Kerrytown. We know this dot product must be \(0\).
Intuitively, this says that the errors for Kerrytown apartments must sum to \(0\). Since there is only one Kerrytown apartment, this means that its prediction must be correct.
Similarly, if we take the dot product of the error vector with the third column of \(X\), this tells us that the errors for the Central Campus apartments must sum to \(0\).
but this is not enough information to determine the values of (iii) and (iv). To get another equation, we can set the dot product of the error vector with the first column of \(X\) to \(0\).
Consider the function \(g: \mathbb{R}^3 \to \mathbb{R}\). We’d like to minimize \(g\) using gradient descent.
a)
(6 pts) Suppose two separate runs of gradient descent are started from the same initial guess\(\vec x^{(0)}\), but with different learning rates (step sizes), \(\alpha\).
If \(\alpha = 1/2\), then \(\vec x^{(1)} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}\), and if \(\alpha = 1/4\), then \(\vec x^{(1)} = \begin{bmatrix} 2 \\ 3 \\ 2 \end{bmatrix}\).
Find \(\nabla g(\vec x^{(0)})\), the gradient of \(g\) at \(\vec x^{(0)}\). Show your work, and write your final answer in the box provided. Your answer should be a vector with no variables.
$$ \nabla g(\vec x^{(0)}) = \_\_\_\_\_\_ $$
Solution
Let \(\vec d = \nabla g(\vec x^{(0)})\). The gradient descent update rule is
We applied the chain rule above by writing \(\left( x_1 + 2x_2 - 6 \right)^2 = (\begin{bmatrix} 1 \\ 2 \end{bmatrix} \cdot \vec x - 6)^2\). If this feels foreign, we can instead take partial derivatives with respect to \(x_1\) and \(x_2\) separately.
Consider the matrix \(A = \begin{bmatrix} 2 & 3 \\ -4 & k \end{bmatrix}\) where \(k \in \mathbb{R}\) is some unknown constant.
a)
3 pts Suppose \(\lambda_1 = 0\) is an eigenvalue of \(A\). Find the value of \(k\). Give your answer as a number with no variables.
\(k = \_\_\_\_\_\_\)
Solution
If \(0\) is an eigenvalue, then \(\det(A)=0\). So
$$ \det(A)=2k-3(-4)=2k+12=0 $$
This gives
$$ k=\boxed{-6} $$
b)
4 pts Suppose \(\begin{bmatrix} 1 \\ 1 \end{bmatrix}\) is an eigenvector of \(A\). Find the value of \(k\). Give your answer as a number with no variables.
$$ k = \_\_\_\_\_\_ $$
Solution
If \(\begin{bmatrix}1\\1\end{bmatrix}\) is an eigenvector, then
must be a scalar multiple of \(\begin{bmatrix}1\\1\end{bmatrix}\). Therefore,
$$ k-4=5 $$
so
$$ k=\boxed{9} $$
c)
5 pts Suppose \(\lambda_1 = 3\) is an eigenvalue of \(A\). Find \(\lambda_2\), the other eigenvalue of \(A\). Show your work, and write your final answer in the box provided. Give your answer as a number with no variables.
This gives \(k=15\). The trace of \(A\) is then \(2+15=17\), so the two eigenvalues sum to \(17\). Thus,
$$ \lambda_2 = 17-3 = \boxed{14} $$
Problem 10 14 pts
The state diagram below describes a Markov chain with four states.
a)
4 pts Find the adjacency matrix \(A\) for this Markov chain.
\(A =\) ______
Solution
Column \(j\) contains the probabilities of transitioning from state \(j\) to all other states; columns must sum to \(1\). Reading from the diagram, the first two columns come from the left “connected component” (made up of states \(1\) and \(2\)), and the last two columns come from the right connected component. So
6 pts Suppose the chain starts in state \(\mathbf{1}\). Fill each box with the long-run fraction of time spent in each state. Your answers should be numbers with no variables, and should sum to \(1\).
State 1: ______ State 2: ______ State 3: ______ State 4: ______
Solution
As we know from Chapter 9.3, the long-run fraction of time spent in each state is described by the eigenvector of the adjacency matrix corresponding to eigenvalue \(1\) (and whose components sum to \(1\)).
What is tricky about this particular adjacency matrix is that it has two linearly independent eigenvectors, both for the eigenvalue \(1\). Why? Note that the Markov chain has two isolated islands, and its impossible to transition between them. So if we ever start in states \(1\) or \(2\), in the long run, we will only spend time in states \(1\) and \(2\). Similarly, if we start in states \(3\) or \(4\), in the long run, we will only spend time in states \(3\) and \(4\).
This means that we can simplify the problem by just looking at the \(2 \times 2\) matrix in the top right of \(A\) corresponding to the left island (states \(1\) and \(2\)). This matrix is
All we need to do now is find the eigenvector of \(A_{\text{left}}\) corresponding to eigenvalue \(1\). If such an eigenvector is of the form \(\begin{bmatrix} a \\ b \end{bmatrix}\), then
$$ \begin{bmatrix} 1/4 & 1/2 \\\\ 3/4 & 1/2 \end{bmatrix} \begin{bmatrix} a \\\\ b \end{bmatrix} = 1 \begin{bmatrix} a \\\\ b \end{bmatrix} $$
The first row gives us
$$ \frac{1}{4}a + \frac{1}{2} b = a \implies \frac{1}{2} b = \frac{3}{4}a \implies b = \frac{3}{2}a $$
So, if \(a = 2\), then \(b = 3\). But, the steady-state distribution must have components that sum to \(1\), so as probabilities, we’re looking at \(2/5\) and \(3/5\).
Not only is \(\begin{bmatrix} 2/5 \\ 3/5 \end{bmatrix}\) an eigenvector of \(A_{\text{left}}\) corresponding to eigenvalue \(1\), but
is an eigenvector of the full matrix \(A\) corresponding to eigenvalue \(1\)! The 0’s in the latter two components effectively “ignore” states \(3\) and \(4\), representing the assumption that we start in state \(1\).
There’s a section in Chapter 9.4 about block diagonal matrices that is relevant here.
Now, consider a modified version of the Markov chain. Changes have been emphasized in bold.
c)
4 pts Consider the statement: “‘If we start in ____, the long-run fraction of time spent in each state is the same as in the original chain.’’
Which of the following could be placed in the blank to make the statement true? Select all that apply.
state 1 state 2 state 3 state 4 none of these are valid
Solution
state 1 state 2 state 3 state 4 none of these are valid
In the modified chain, starting in state \(1\) or state \(2\) eventually leads to the right connected component, because there is now a positive-probability path from state \(2\) to state \(3\). This changes the long-run fractions compared to the original chain. The long-run fraction of time spent in states \(1\) and \(2\) now will be \(0\).
Starting in state \(3\) or state \(4\), the chain stays in the right connected component, and that component has not changed. There is no way to go from state \(3\) to \(2\) or \(1\). So, the long-run fractions are the same as in the original chain; \(3/8\) for state \(3\) and \(5/8\) for state \(4\), and \(0\) for states \(1\) and \(2\).
The correct choices are
$$ \boxed{\text{state 3 and state 4}} $$
Problem 11 10 pts
Let \(S\) be a \(3 \times 3\)symmetric matrix with eigenvectors \(\vec v_1\), \(\vec v_2\), and \(\vec v_3\) corresponding to eigenvalues \(5\), \(2\), and \(-1\), respectively. Assume that each \(\vec v_i\) is a unit vector.
Suppose \(\vec x \in \mathbb{R}^3\) and that
$$ \vec x = 3\vec v_1 - 4\vec v_2 + \vec v_3 $$
a)
6 pts Write \(S^2 \vec x\) as a linear combination of \(\vec v_1\), \(\vec v_2\), and \(\vec v_3\). Fill in each box with a number with no variables.
This result doesn’t rely on the fact that \(\vec v_1\), \(\vec v_2\), and \(\vec v_3\) are unit vectors or orthogonal; we’ll use these assumptions in the next part.
b)
4 pts What is the value of \(\lVert S\vec x \rVert^2\)?
\(24\)\(26\)\(218\)\(290\)\(5882\) Not enough information
Solution
\(24\)\(26\)\(218\)\(290\)\(5882\) Not enough information
Applying \(S\) once gives
$$ S\vec x = 15\vec v_1 - 8\vec v_2 - \vec v_3 $$
Since \(S\) is symmetric, eigenvectors corresponding to distinct eigenvalues are orthogonal. The vectors \(\vec v_1\), \(\vec v_2\), and \(\vec v_3\) are also unit vectors, so
Yet another way to look at this is to see that \(S = Q \Lambda Q^T\), where the columns of \(Q\) are the vectors \(\vec v_i\) and the diagonal entries of \(\Lambda\) are \(5\), \(2\), and \(-1\). So,
In this solution, we used the fact that \(\vec x = 3 \vec v_1 - 4 \vec v_2 + \vec v_3 = Q \begin{bmatrix} 3 \\ -4 \\ 1 \end{bmatrix}\), and since \(Q^T Q = I\) (if \(Q\)’s columns are the orthonormal \(\vec v_i\)’s), then \(Q^T \vec x = Q^TQ \begin{bmatrix} 3 \\ -4 \\ 1 \end{bmatrix} = \begin{bmatrix} 3 \\ -4 \\ 1 \end{bmatrix}\).
Problem 12 12 pts
Suppose \(\tilde X\) is an \(n \times 2\) matrix whose columns are mean-centered (i.e. have a mean of 0). Furthermore, suppose
Note that \(\tilde X^T \tilde X\) has eigenvalues of \(7\) and \(2\). Let \(\tilde X = U \Sigma V^T\) be the singular value decomposition of \(\tilde X\), and let \(\vec v_1\) be the first column of \(V\) (not \(V^T\)).
a)
4 pts What is \(\vec v_1\)? Give your answer as a vector with no variables. If there are multiple correct answers, you only need to provide one.
\(\vec v_1 = \_\_\_\_\_\_\)
Solution
The first right singular vector, \(\vec v_1\), is an eigenvector of \(\tilde X^T\tilde X\) corresponding to the largest eigenvalue, \(7\). So we solve
3 pts Suppose the variance of the second principal component is \(1/15\). What is \(n\), the number of rows in \(\tilde X\)? Give your answer as a number with no variables.
\(n = \_\_\_\_\_\_\)
Solution
The variance of the second principal component is
$$ \frac{\sigma_2^2}{n} $$
Since \(\sigma_2^2\) is the second-largest eigenvalue of \(\tilde X^T\tilde X\), we have \(\sigma_2^2=2\). So
$$ \frac{2}{n}=\frac{1}{15} $$
This gives
$$ n=\boxed{30} $$
c)
5 pts Suppose that \(\vec u_2\) is the second column of \(U\), corresponding to the singular value \(\sigma_2\), in the singular value decomposition of \(\tilde X\).
Prove that \(\tilde X \vec v_1\) and \(\sigma_2 \vec u_2\) are orthogonal. You do not need to re-prove any facts about the singular value decomposition, but you should state any facts you use.
The columns of \(U\) are orthonormal, so \(\vec u_1^T\vec u_2=0\). Therefore,
$$ (\tilde X\vec v_1)^T(\sigma_2\vec u_2)=0 $$
This proves that \(\tilde X\vec v_1\) and \(\sigma_2\vec u_2\) are orthogonal.
Problem 13 4 pts
What is one topic you studied a lot for that wasn’t on the Final Exam? Blank answers will receive no credit!
Solution
One topic that didn’t appear was convexity — there was originally going to be a question about convexity but we cut it to prevent the exam from being too long.
