CS760-Assignment 1 Solved

Consider the matrix X and the vectors y and z below:

                                                                                                     9                       7

                                                                                          y =                    z =

                                                                                                     8                       6

1.   What is the inner product of the vectors y and z? (this is also sometimes called the dot product, and is sometimes written as y T z)

2.   What is the product X y ?

3.   Is X invertible? If so, give the inverse, and if no, explain why not

4.   What is the rank of X ?

1.   Calculus If y = 4x3       x2 + 7 then what is the derivative of y with respect to x?
2.   , what is the partial derivative of y with respect to x?

1         Probability and Statistics Consider a sample of data S = f 0; 1; 1; 0; 0; 1; 1g created by flipping a coin x seven times, where 0 denotes that the coin turned up heads and 1 denotes that it turned up tails.
1.   What is the sample mean for this data)

2.   What is the sample variance for this data?

3.   What is the probability of observing this data, assuming it was generated by flipping a biased coin with p(x = 1) = 0:7; p(x = 0) = 0:3.

4.   Note that the probability of this data sample would be greater if the value of p(x = 1) was not 0:7, but instead some other value. What is the value that maximizes the probability of the sample S ? Please justify your answer.

5.   Consider the following joint probability table where both A and B are binary random variables:

A
B
P (A; B)
0
0
0.1
0
1
0.4
1
0
0.2
1
1
0.3
(a)    What is P (A = 0; B = 0)?

(b)   What is P (A = 1)?

(c)    What is P (A = 0jB = 1)?

(d)       What is P (A = 0 _ B = 0)?

(e)       Big-O Notation [20 pts]

For each pair (f; g) of functions below, list which of the following are true: f (n) = O(g(n)), g(n) = O(f (n)), both, or neither. Briefly justify your answers.

1.   .

2.   f (n) = ln(n), g(n) = log2(n).

3.         f (n) = n100, g(n) = 100n . Medium Background Test Algorithm

Divide and Conquer: Assume that you are given a sorted array with n integers in the range [ 10; + 10]. Note that some integer values may appear multiple times in the array. Additionally, you are told that somewhere in the array the integer 0 appears exactly once. Provide an algorithm to locate the 0 which runs in O(log(n)). Explain your algorithm in words, describe why the algorithm is correct, and justify its running time.

2         Probability and Random Variables
2.1        Probability
State true or false. Here  denotes the sample space and A c denotes the complement of the event A .

1.   For any A; B               , P (A jB )P (B ) = P (B jA )P (A ).

2.   For any A; B               , P (A [ B ) = P (A ) + P (B )               P (A jB ).

3.   For any A; B; C          such that .

4.   For any A; B               such that P (B ) 0; P(A c) 0, P (B jA C ) + P (B jA ) = 1.

5.   For any n events , then are mutually independent.

\

2.2        Discrete and Continuous Distributions
Match the distribution name to its probability density / mass function. Below, jx j = k.

                                                         (f) f (x ;     (x          )T              1(x         )

                                                                )n          x for x 2 f0; : : : ; ng; 0

otherwise

(a)    L aplace        

(b)   Multinomial  and

(c)    Poisson           otherwise

(d)   Dirichlet         (j) f (x; ;) = (  ) x             1e x for x 2 (0; + 1 ); 0 oth-

(e)   Gamma         erwise

                                                        (k) f (x ;       ) = and

P ; 0 otherwise

 for all x 2 Z + ; 0 otherwise

2.3        Mean and Variance
1.   Consider a random variable which follows a Binomial distribution: X          Binomial(n; p).

(a)    What is the mean of the random variable

(b)   What is the variance of the random variable?

2.   L et X be a random variable and E [X ] = 1; Var(X ) = 1. Compute the following values:

(a)    E [3X ]

(b)   Var(3X )

(c)    Var(X + 3)

2.4        Mutual and Conditional Independence
1.   If X and Y are independent random variables, show that       .

2.   If X and Y are independent random variables, show that Var(X + Y ) = Var(X ) + Var(Y ). Hint: Var(X + Y ) = Var(X ) + 2Cov(X; Y ) + Var(Y )

If we roll two dice that behave independently of each other, will the result of the first die tell us something about the result of the second die?

If, however, the first die’s result is a 1, and someone tells you about a third event — that the sum of the two results is even — then given this information is the result of the second die independent of the first die? Law of Large Numbers and the Central Limit Theorem

Provide one line justifications.

1.   Suppose we simultaneously flip two independent fair coins (i.e., the probability of heads is 1=2 for each coin) and record the result. After 40,000 repetitions, the number of times the result was two heads is close to 10,000. (Hint: calculate how close.)

2.   L et X i N(0; 1) and , then the distribution of X satisfies

                                                                                  p         n !   1

                                                                                        nX !        N(0; 1)

3         Linear algebra
3.1        Norm-enclature
Draw the regions corresponding to vectors x 2 R 2 with the following norms:

1.   jjx jj1                     1 (Recall that jjx jj1 = P i jx i j)

2.   jjx jj2                     1 (Recall that

3. jjx jj1           1 (Recall that jjx jj1                        = maxi jx i j)

2.



3.



3.2       Geometry
Prove that these are true or false. Provide all steps.

1.   The smallest Euclidean distance from the origin to some point x in the hyperplane w .

2.   The Euclidean distance between two parallel hyperplane w T x + b1 = 0 and w T x  (Hint: you can use the result from the last question to help you prove this one).

)

4         Programming Skills Sampling from a distribution. For each question, submit a scatter plot (you will have 5 plots in total). Make sure the axes for all plots have the same limits. (Hint: You can save the figure as a pdf, and then use includegraphics to include the pdf in your latex file. Suggest to use Python or Matlab.)
1.   Draw 100 samples x = [x1; x2]T from a 2-dimensional Gaussian distribution with mean (0; 0)T and identity covariance matrix, i.e., , and make a scatter plot (x1 vs. x2). For each question below, make each change separately to this distribution.



2.   Make a scatter plot with a changed mean of (1;               1)T .



2              0

3.   Make a scatter plot with a changed covariance matrix of               .

                                                                                                            0    2



2              0:2

4.   Make a scatter plot with a changed covariance matrix of               . 0:2        2



2              0:2

5.   Make a scatter plot with a changed covariance matrix of               . 0:2        2