Week 1

Show your work and briefly explain what each numerical answer means in the context of the problem. You may use the facts from Lectures 01 and 02 without proving them.

Problem 1

A dataset contains $100$ images. Of these, $60$ are daytime images and $40$ are nighttime images. A daytime image passes an automated quality check with probability $0.80$, while a nighttime image passes with probability $0.50$.

For image $i$, let \[ I_i= \begin{cases} 1, & \text{if image $i$ passes the quality check},\\ 0, & \text{otherwise}, \end{cases} \] and let $S=I_1+\cdots+I_{100}$ be the number of images that pass.

What is $\Ebb[I_i]$ for a daytime image? What is it for a nighttime image?
Use linearity of expectation to compute $\Ebb[S]$.
Let $F$ be the number of images that fail the check. Express $F$ in terms of $S$, and compute $\Ebb[F]$.

Solution sketch

Since each $I_i$ is an indicator variable, its expectation is the probability that it equals $1$. Thus $\Ebb[I_i]=0.80$ for a daytime image and $\Ebb[I_i]=0.50$ for a nighttime image.
Linearity of expectation gives \[ \Ebb[S] =60(0.80)+40(0.50) =68. \] Thus we expect $68$ images to pass the check.
Since every image either passes or fails, $F=100-S$. Therefore \[ \Ebb[F]=100-\Ebb[S]=32. \]

Problem 2

A sensor reading $X$ has mean $20$ and variance $4$. The calibrated reading is \[ Y=\frac32X-2. \]

Compute $\Ebb[Y]$.
Compute $\Var(Y)$.
Now suppose $Y_1,\ldots,Y_{16}$ are independent calibrated readings, each with the same distribution as $Y$. Let \[ \overline{Y}=\frac1{16}\sum_{i=1}^{16}Y_i. \] Compute $\Ebb[\overline{Y}]$, $\Var(\overline{Y})$, and the standard deviation of $\overline{Y}$.
Compare the standard deviation of one calibrated reading with that of the average. Briefly, explain what averaging accomplished.

Solution sketch

By linearity of expectation, \[ \Ebb[Y]=\frac32\Ebb[X]-2=28. \]
Adding a constant does not affect variance, while scaling by $3/2$ multiplies variance by $(3/2)^2$. Hence \[ \Var(Y)=\left(\frac32\right)^2\Var(X)=9. \]
The average has expectation \[ \Ebb[\overline{Y}]=28. \] Independence allows the variances to add, so \[ \begin{aligned} \Var(\overline{Y}) &=\frac1{16^2}\sum_{i=1}^{16}\Var(Y_i) =\frac{9}{16},\\ \sigma(\overline{Y}) &=\sqrt{\frac9{16}}=\frac34. \end{aligned} \]
One calibrated reading has standard deviation $3$, while the average has standard deviation $3/4$. Averaging $16$ independent readings reduces the standard deviation by a factor of $\sqrt{16}=4$.

Problem 3

Recall that the $d$-dimensional unit cube, centered at the origin, is \[ C^d(1)=\left[-\frac12,\frac12\right]^d. \]

A random variable $U$ is uniformly distributed on an interval $[a,b]$ if it has density \[ f_U(u)= \begin{cases} \dfrac{1}{b-a}, & a\leq u\leq b,\\ 0, & \text{otherwise}. \end{cases} \] Consequently, for a function $g$ for which the expectation exists, \[ \Ebb[g(U)] =\int_{-\infty}^{\infty}g(u)f_U(u)\,du =\frac{1}{b-a}\int_a^b g(u)\,du. \]

First consider one dimension. Let $U$ and $V$ be independent random variables, each uniformly distributed on $C^1(1)=[-1/2,1/2]$. Compute \[ \Ebb[(U-V)^2]. \] You may find it useful first to compute $\Ebb[U]$ and $\Ebb[U^2]$.
Now let $\bfX=(X_1,\ldots,X_d)$ and $\bfY=(Y_1,\ldots,Y_d)$ be independent uniformly random points in $C^d(1)$. Their squared Euclidean difference is defined by \[ \|\bfX-\bfY\|_2^2 =\sum_{j=1}^d(X_j-Y_j)^2. \] Use linearity of expectation and your answer to part 1 to compute \[ \Ebb\!\left[\|\bfX-\bfY\|_2^2\right]. \]
What can you conclude about this quantity as $d$ increases?

Solution sketch

By symmetry, $\Ebb[U]=\Ebb[V]=0$. Since the density of $U$ is $1$ on $[-1/2,1/2]$, \[ \Ebb[U^2] =\int_{-1/2}^{1/2}u^2\,du =\frac{1}{12}. \] The same calculation applies to $V$. Independence gives $\Ebb[UV]=\Ebb[U]\Ebb[V]=0$, so \[ \begin{aligned} \Ebb[(U-V)^2] &=\Ebb[U^2]-2\Ebb[UV]+\Ebb[V^2]\\ &=\frac{1}{12}+\frac{1}{12} =\frac{1}{6}. \end{aligned} \]
Uniform sampling from the product cube $[-1/2,1/2]^d$ makes each coordinate uniform on $[-1/2,1/2]$. Because $\bfX$ and $\bfY$ are sampled independently, $X_j$ and $Y_j$ are independent. Thus $(X_j,Y_j)$ has the same distribution as $(U,V)$. Thus, by linearity of expectation, \[ \begin{aligned} \Ebb\!\left[\|\bfX-\bfY\|_2^2\right] &=\sum_{j=1}^d\Ebb[(X_j-Y_j)^2]\\ &=\sum_{j=1}^d\frac{1}{6} =\frac{d}{6}. \end{aligned} \]
It increases!

Problem 4

Let $X$ be a random variable with finite second moment, and let $\mu=\Ebb[X]$.

Prove that, for every $a\in\Rbb$, \[ \Ebb[(X-a)^2] = \Var(X)+(a-\mu)^2. \]
Conclude that $\mu$ is the unique value of $a$ that minimizes $\Ebb[(X-a)^2]$.
Interpret this result: if you must predict $X$ using a single constant, why is the mean the best choice when error is measured by squared error?

Solution sketch

Write \[ X-a=(X-\mu)+(\mu-a). \] Expanding the square and taking expectations gives \[ \begin{aligned} \Ebb[(X-a)^2] &=\Ebb[(X-\mu)^2] +2(\mu-a)\Ebb[X-\mu] +(\mu-a)^2\\ &=\Var(X)+(a-\mu)^2, \end{aligned} \] since $\Ebb[X-\mu]=0$.
The term $\Var(X)$ does not depend on $a$, while $(a-\mu)^2\geq 0$, with equality exactly when $a=\mu$. Therefore the unique minimizer is $a=\mu$.
The expected squared prediction error equals the unavoidable variation $\Var(X)$ plus the additional penalty $(a-\mu)^2$ for predicting away from the mean. Choosing $a = \mu$ completely annhilates the second term. Thus choosing the mean gives the smallest possible expected squared error among all constant predictions.

Problem 5

A dataset contains $100{,}000$ vectors $\bfv_1,\ldots,\bfv_{100{,}000}\in\Rbb^{1000}$, each satisfying $\|\bfv_i\|_2\leq 1$. Let \[ \bfx=\frac{1}{100{,}000}\sum_{i=1}^{100{,}000}\bfv_i. \] You may reference the exact and approximate Carathéodory theorems. If this question is selected for the assessment, these will be reprinted on the exam sheet.

Explain why $\bfx$ belongs to the convex hull of the dataset.
How many dataset vectors suffice to approximate $\bfx$ by their average with Euclidean error at most $0.1$? What about error at most $0.05$?
If the ambient dimension increases to $10{,}000$, with the number of vectors and norm bound unchanged, how do your guarantees change?

Solution sketch

The average is a convex combination with non-negative weights $\alpha_i=1/100{,}000$ that sum to $1$. Thus $\bfx$ belongs to the convex hull. By Carathéodory’s theorem, it can be represented exactly as a convex combination of at most $d+1=1001$ dataset vectors.
The approximate Carathéodory theorem with $R=1$ guarantees an average of $k$ dataset vectors, possibly with repetitions, with error at most $1/\sqrt{k}$. For error at most $\epsilon$, it suffices to take \[ k=\left\lceil\frac{1}{\epsilon^2}\right\rceil. \] Thus $100$ vectors suffice for error $0.1$, and $400$ suffice for error $0.05$. Halving the error tolerance quadruples this sample size.
The approximate guarantees remain $100$ and $400$: they depend on the norm bound and error tolerance, but not on the ambient dimension.