This document contains the homework questions for a course on mathematical methods in communication. The homework covers properties of entropy and mutual information. Question 1 asks to show that the entropy of a function of a random variable is less than or equal to the entropy of the variable. Question 2 provides a joint probability distribution and asks to calculate various entropies. Question 3 gives statements to identify as true or false, proving or providing counterexamples. Later questions ask about the relationship between entropies expressed in bits versus bytes, independence of multiple variables, and defining a measure of correlation between two variables.
This document contains the homework questions for a course on mathematical methods in communication. The homework covers properties of entropy and mutual information. Question 1 asks to show that the entropy of a function of a random variable is less than or equal to the entropy of the variable. Question 2 provides a joint probability distribution and asks to calculate various entropies. Question 3 gives statements to identify as true or false, proving or providing counterexamples. Later questions ask about the relationship between entropies expressed in bits versus bytes, independence of multiple variables, and defining a measure of correlation between two variables.
This document contains the homework questions for a course on mathematical methods in communication. The homework covers properties of entropy and mutual information. Question 1 asks to show that the entropy of a function of a random variable is less than or equal to the entropy of the variable. Question 2 provides a joint probability distribution and asks to calculate various entropies. Question 3 gives statements to identify as true or false, proving or providing counterexamples. Later questions ask about the relationship between entropies expressed in bits versus bytes, independence of multiple variables, and defining a measure of correlation between two variables.
This document contains the homework questions for a course on mathematical methods in communication. The homework covers properties of entropy and mutual information. Question 1 asks to show that the entropy of a function of a random variable is less than or equal to the entropy of the variable. Question 2 provides a joint probability distribution and asks to calculate various entropies. Question 3 gives statements to identify as true or false, proving or providing counterexamples. Later questions ask about the relationship between entropies expressed in bits versus bytes, independence of multiple variables, and defining a measure of correlation between two variables.
Homework Set #1 Properties of Entropy and Mutual Information 1. Entropy of functions of a random variable. Let X be a discrete random variable. Show that the entropy of a function of X is less than or equal to the entropy of X by justifying the following steps: (a)
H(X, g(X)) = H(X) + H(g(X)|X)
(b)
= H(X).
(c)
H(X, g(X)) = H(g(X)) + H(X|g(X))
(d)
H(g(X)).
Thus H(g(X)) H(X).
Solution: Entropy of functions of a random variable. (a) H(X, g(X)) = H(X)+H(g(X)|X) by the chain rule for entropies. (b) H(g(X)|X) = 0 since for any particular value of X, g(X) is fixed, P P and hence H(g(X)|X) = x p(x)H(g(X)|X = x) = x 0 = 0. (c) H(X, g(X)) = H(g(X)) + H(X|g(X)) again by the chain rule. (d) H(X|g(X)) 0, with equality iff X is a function of g(X), i.e., g(.) is one-to-one. Hence H(X, g(X)) H(g(X)). Combining parts (b) and (d), we obtain H(X) H(g(X)). 2. Example of joint entropy. Let p(x, y) be given by Y 0 1
X 0 1 1
1 3
1 3 1 3
Find (a) H(X), H(Y ). (b) H(X|Y ), H(Y |X). (c) H(X, Y ). (d) H(Y ) H(Y |X). (e) I(X; Y ). 3. True or False questions Copy each relation and write true or false. Then, if its true, prove it. If it is false give a counterexample or prove that the opposite is true. (a) H(X) H(X|Y ) (b) H(X) + H(Y ) H(X, Y ) (c) Let X, Y be two independent random variables. Then H(X Y ) H(X). 4. Solution to True or False questions e. (a) H(X) H(X|Y ) is true. Proof: In the class we showed that I(X; Y ) > 0, hence H(X) H(X|Y ) > 0. (b) H(X) + H(Y ) H(X, Y ) is false. Actually the opposite is true, i.e., H(X) + H(Y ) H(X, Y ) since I(X; Y ) = H(X) + H(Y ) H(X, Y ) 0. (c) Let X, Y be two independent random variables. Then H(X Y ) H(X). True
(a)
(b)
H(X Y ) H(X Y |Y )) H(X)
(a) follows from the fact that conditioning reduces entropy. (b) Follows from the fact that given Y , X Y is a Bijective Function.
5. Bytes. P The entropy, Ha (X) = p(x) loga p(x) is expressed in bits if the logarithm is to the base 2 and in bytes if the logarithm is to the base 256. What is the relationship of H2 (X) to H256 (X)? Solution: Bytes. H2 (X) =
where (a) comes from the property of logarithms and (b) follows from the definition of H256 (X). Hence we get H2 (X) = 8H256 (X). Solution: Example of joint entropy (a) H(X) =
6. Two looks. Here is a statement about pairwise independence and joint independence. Let X, Y1 , and Y2 be binary random variables. If I(X; Y1) = 0 and I(X; Y2 ) = 0, does it follow that I(X; Y1, Y2 ) = 0? 3
(a) Yes or no?
(b) Prove or provide a counterexample. (c) If I(X; Y1) = 0 and I(X; Y2) = 0 in the above problem, does it follow that I(Y1; Y2 ) = 0? In other words, if Y1 is independent of X, and if Y2 is independent of X, is it true that Y1 and Y2 are independent? Solution: Two looks. (a) The answer is no. (b) Although at first the conjecture seems reasonable enoughafter all, if Y1 gives you no information about X, and if Y2 gives you no information about X, then why should the two of them together give any information? But remember, it is NOT the case that I(X; Y1 , Y2) = I(X; Y1) + I(X; Y2). The chain rule for information says instead that I(X; Y1, Y2 ) = I(X; Y1) + I(X; Y2|Y1). The chain rule gives us reason to be skeptical about the conjecture. This problem is reminiscent of the well-known fact in probability that pair-wise independence of three random variables is not sufficient to guarantee that all three are mutually independent. I(X; Y1 ) = 0 is equivalent to saying that X and Y1 are independent. Similarly for X and Y2 . But just because X is pairwise independent with each of Y1 and Y2 , it does not follow that X is independent of the vector (Y1 , Y2 ). Here is a simple counterexample. Let Y1 and Y2 be independent fair coin flips. And let X = Y1 XOR Y2 . X is pairwise independent of both Y1 and Y2 , but obviously not independent of the vector (Y1 , Y2 ), since X is uniquely determined once you know (Y1 , Y2 ). (c) Again the answer is no. Y1 and Y2 can be arbitrarily dependent with each other and both still be independent of X. For example, let Y1 = Y2 be two observations of the same fair coin flip, and X an independent fair coin flip. Then I(X; Y1) = I(X; Y2) = 0 because X is independent of both Y1 and Y2 . However, I(Y1 ; Y2) = H(Y1 ) H(Y1|Y2 ) = H(Y1) = 1.
7. A measure of correlation. Let X1 and X2 be identically distributed, but not necessarily independent. Let H(X2 |X1 ) =1 . H(X1 ) (a) Show =
I(X1 ;X2 ) . H(X1 )
(b) Show 0 1. (c) When is = 0? (d) When is = 1? Solution: A measure of correlation. X1 and X2 are identically distributed and =1
(c) = 0 iff I(X1 ; X2 ) = 0 iff X1 and X2 are independent.
(d) = 1 iff H(X2 |X1 ) = 0 iff X2 is a function of X1 . By symmetry, X1 is a function of X2 , i.e., X1 and X2 have a one-to-one correspondence. For example, if X1 = X2 with probability 1 then = 1. Similarly, if the distribution of Xi is symmetric then X1 = X2 with probability 1 would also give = 1. 5
