Homework #1: Review of Linear Algebra, Probability & Statistics and Computing Solution

1. You can modify any of the C++ code on Compass to solve these problems, if you want. It might help you with honing your programming skills. If these attempts (at using C++ code) is turning out to to be intense, you can use MATLAB just this once.

 

2. You will submit a PDF-version of your answers on Compass on-or-before mid- night of the due date.

 

Instructions

 

1. (25 points) Tightness of the Chebyshev Bound: This problem is about discov- ering distributions where the upper-bounds of the Chebyshev Inequality is tight. First, you are going to show (by example) that there is a discrete RV where this bound is tight. Then, you are going to present a cogent argument (no need to be super formal here!)  that there can be no continuous RV where the Chebyshev Bound it tight.

 

(a) (5 points) Show that the Chebyshev Bound is tight for the discrete RV X ∈



k2
 


2k2
 
{−1, 0, 1}, where Prob(X = −1) = Prob(X = 1) =    1  . That is, compute E{X} and var(X) and plug it into the Chebyshev Bound and arrive at the conclusion that Prob(| X |≥ 1) =    1

(b) (20 points) Show that there can be no continuous distribution over the whole real axis where the Chebyshev Bound is tight.

 

2. (25 points) Unit-Ball in High Dimensions:  We will use the `4 -norm to define the unit-ball as

 

B(1, d, 4) = {(x1 , x2 , . . . , xd ) ∈ Rd  |  x4 + x4 + · · · + x4 ≤ 1}

 

(a) (12.5 points) Suppose we define


1         2                     d

 

 

 

1

S := {(x1 , x2 , . . . , xd ) ∈ Rd  |  x4 + x4 + · · · + x4 ≤    },

1         2                     d       2

 

what fraction of the volume of B(1, d, 4) does S occupy?

(b) (12.5 points) For any c    0, prove that the fraction of the volume of

B(1, d, 4) outside the slab

 

  c 


 

 1    c4 /4

|  x1 |≤ d1/4  is at most c3 e−        .

 

 

 

 

 

3. (25 points) Overlap of Spheres in High-Dimensions:  Let x be a random sample from the (surface of the) unit sphere in d-dimensions with the origin as center.

 

(a) (5 points) What is the value of E{x}?

(b) (5 points) What is component-wise variance of x? That is, for i ∈ {1, 2, . . . , d}

what is E{(xi − E{xi })2 }?

(c) (5 points) Show that for any unit length vector u, the variance of the real-

valued random variable uT x is Pd


u2 E{x2 }. Using this, compute the vari-

i=1    i         i

ance and standard deviation of uT x.

(d) (5 points) Given two unit-radius spheres in d-dimensional space whose cen- ters are separated by a distance of a, show that the volume of their intersec- tion is at most

8e−a2 (d−1)/8

a √d − 1

times the volume of each sphere.

(e) (5 points) From your solution to problem 3d, present a verbal argument that supports the conclusion that if the inter-center separation of the two



d
 
spheres of radius r (r is not necessarily unity) is Ω(r/ √    ), then they share

very small mass.  From this, make a cogent case for the conclusion that given randomly generated points from the two distributions, one inside each sphere, we can tell “which sphere contains which point” (i.e.  clas- sify we have a clustering algorithm that separates randomly generated data into two spherical-groups)

 

4. (25 points) A Counterpoint to the Johnson-Lindenstrauss Lemma: Prove that for every fixed dimension reduction matrix A ∈ Rk×d  with k < d, there is a pair of vectors x, y ∈ Rd  such that the distances between their images Ax and Ay is hugely distorted (compared to the distance between x and y).