Homework 1

Description

No extension of the deadline is allowed. Late submission will lead to 0 credit.

Discussion is encouraged on Piazza as part of the Q/A. However, all as-signments should be done individually.

Instructions

This assignment has no programming, only written questions.

We will be using Gradescope this semester for submission and grading of assignments.

Your write up must be submitted in PDF form, you may use either Latex or markdown, whichever you prefer. We will not accept handwritten work.

Please make sure to start answering each question on a new page. It makes it more organized to map your answers on GradeScope. When submitting your assignment, you must correctly map pages of your PDF to each question/subquestion to re ect where they appear. Im-properly mapped questions may not be graded correctly.

Please show the calculation process used to arrive at the answer. Sub-missions with only the nal answer and no derivation/calculation process will receive 0 credit

• Linear Algebra [30pts]

1.1 Determinant and Inverse of Matrix [15pts]

Given a matrix M:

• 3

r 6 0

M = 4	2	3	r	5
	4	7	3

1. Calculate the determinant of M in terms of r. [4pts]

2. For what value(s) of r does M ¹ not exist? Why? What does it mean in terms of rank and singularity of M for these values of r? [3pts]

3. Calculate M ¹ by hand for r = 4. [5pts] (Hint 1: Please double check your answer and make sure M M ¹ = I)

4. Find the determinant of M ¹ for r = 4. [3pts]

1.2 Characteristic Equation [5pts]

Consider the eigenvalue problem:

Ax = x; x 6= 0

where x is a non-zero eigenvector and is eigenvalue of A. Prove that the de-terminant jA Ij = 0.

1.3 Eigenvalues and Eigenvectors [10pts]

Given a matrix A:

x 3 A = _{1 x}

1. Calculate the eigenvalues of A as a function of x [5 pts]

2. Find the normalized eigenvectors of matrix A [5 pts]

• Expectation, Co-variance and Independence [18pts]

Suppose X; Y and Z are three di erent random variables. Let X obey a Bernouli Distribution. The probability disbribution function is

0:5 x = c

p(x) =

0:5 x = c:

c is a constant here. Let Y obey a standard Normal (Gaussian) distribution, which can be written as Y N(0; 1). X and Y are independent. Meanwhile, let Z = XY .

1. Show that Z also follows a Normal (Gaussian) distribution. Calculate the Expectation and Variance of Z. [9pts] (Hint: Sum rule and conditional probability formula)

2. How should we choose c such that Y and Z are uncorrelated(which means Cov(Y; Z) = 0)? [5pts]

2. Are Y and Z independent? Make use of probabilities to show your con-clusion. Example: P (Y 2 ( 1; 0)) and P (Z 2 (2c; 3c)) [4pts]

• Optimization [15 pts]

Optimization problems are related to minimizing a function (usually termed loss, cost or error function) or maximizing a function (such as the likelihood) with respect to some variable x. The Kuhn-Tucker conditions are rst-order conditions that provide a uni ed treatment of constraint optimization. In this question, you will be solving the following optimization problem:

max f(x; y) = 2x² + 3xy

x;y

s.t. g₁(x; y) = ¹₂ x² + y 4

g₂(x; y) = y 2

1. Specify the Legrange function [2 pts]

2. List the KKT conditions [2 pts]

3. Solve for 4 possibilities formed by each constraint being active or inactive [5 pts]

4. List all candidate points [4 pts]

5. Check for maximality and su ciency [2 pts]

• Maximum Likelihood [10 + 25 pts]

4.1 Discrete Example [10 pts]

Suppose we have two types of coins, A and B. The probability of a Type A coin showing heads is . The probability of a Type B coin showing heads is 2 . Here, we have a bunch of coins of either type A or B. Each time we choose one coin and ip it. We do this experiment 10 times and the results are shown in the chart below. (Hint: The probabilities aforementioned are for the particular sequence below.)

Coin Type Result

• Tail

• Tail

• Tail

• Tail

• Tail

• Head

• Head

0. • Head

0. • Head

0. • Head

0. What is the likelihood of the result given ? [4pts]

0. What is the maximum likelihood estimation for ? [6pts]

4.2 Normal distribution [15 pts](Bonus for Undergrads)

Suppose that we observe samples of a known function g(t) = t³ with unknown amplitude at (known) arbitrary locations t₁; : : : ; t_N ; and these samples are corrupted by Gaussian noise. That is, we observe the sequence of random variables

X_n = t³_n + Z_n; n = 1; : : : ; N

where the Z_n are independent and Z_n Normal 0; ²

(a) Given X₁ = x₁; : : : ; X_N = x_N ; compute the log likelihood function

‘ ( ; x₁; : : : ; x_N ) = log f_X1;:::;XN (x₁; : : : ; x_N ; ) = log (f_X1 (x₁; ) f_X2 (x₂; ) f_XN (x_N ; ))

Note that the X_n are independent (as the last equality is suggesting) but not identically distributed (they have di erent means). [9pts]

(b) Compute the MLE for . [6pts]

4.3 Bonus for undergrads [10 pts]

The C.D.F of independent random variables X₁; X₂; :::; X_n is

			8	0;				x < 0
P (X	i	x ; ) =		(	x	) ; 0		x
		j	>
			>
			<
			>	1;				x >
			>

:

where 0, 0.

1. Write down the P.D.F of above independent random variables. [4pts]

2. Find the MLEs of and . [6pts]

• Information Theory [32pts]

5.1 Marginal Distribution [6pts]

Suppose the joint probability distribution of two binary random variables X and Y are given as follows.

XjY	1			2
0		1		1
		3		3
1	0			1
				3

1. Show the marginal distribution of X and Y , respectively. [3pts]

2. Find mutual information for the joint probability distribution in the pre-vious question [3pts]

5.2 Mutual Information and Entropy [19pts]

Given a dataset as below.

Sr:N o:	Age	Immunity	T ravelled?	U nderlyingConditions	Self	quarantine?
1	young	high	no	yes		no
2	young	high	no	no		no
3	middleaged	high	no	yes		yes
4	senior	medium	no	yes		yes
5	senior	low	yes	yes		yes
6	senior	low	yes	no		no
7	middleaged	low	yes	no		yes
8	young	medium	no	yes		no
9	young	low	yes	yes		no
10	senior	medium	yes	yes		yes
11	young	medium	yes	no		yes
12	middleaged	medium	no	no		yes
13	middleaged	high	yes	yes		yes
14	senior	medium	no	no		no

We want to decide whether an individual working in an essential services industry should be allowed to work or self-quarantine. Each input has four features (x₁, x₂, x₃, x₄): Age, Immunity, Travelled, Underlying Conditions. The decision (quarantine vs not) is represented as Y .

1. Find entropy H(Y ). [3pts]

2. Find conditional entropy H(Y jx₁), H(Y jx₄), respectively. [8pts]

3. Find mutual information I(x₁; Y ) and I(x₄; Y ) and determine which one (x₁ or x₄) is more informative. [4pts]

4. Find joint entropy H(Y; x₃). [4pts]

5.3 Entropy Proofs [7pts]

1. Suppose X and Y are independent. Show that H(XjY ) = H(X). [2pts]

2. Suppose X and Y are independent. Show that H(X; Y ) = H(X) + H(Y ). [2pts]

3. Prove that the mutual information is symmetric, i.e., I(X; Y ) = I(Y; X) and x_i 2 X; y_i 2 Y [3pts]

• Bonus for All [10 pts]

• 1. If a random variable X has a Poisson distribution with mean 8, then calculate the expectation E[(X + 2)²] [2 pts]

• 2. A person decides to toss a fair coin repeatedly until he gets a head. He will make at most 3 tosses. Let the random variable Y denote the number of heads. Find the variance of Y. [4 pts]

• 3. Two random variables X and Y are distributed according to

(

6