ECE 515
Information Theory

Assignment Submission

Assignments

1. A discrete memoryless source X has symbols x₁, x₂, …, x₉ with p(x₁) = 1/2, and p(x₂) = p(x₃) = 1/8. In addition p(x₄) = p(x₅) and p(x₆) = p(x₇) = p(x₈) = p(x₉). Determine the upper and lower bounds on its entropy and the corresponding symbol probabilities.
2. Consider an alphabet of 9 symbols with probabilities as follows: p(A) = 1/2, p(B) = 1/4, p(C) = 1/8, p(D) = 1/16, p(E) = 1/32, p(F) = 1/64, p(G) = 1/128, p(H) = 1/256, and p(I) = 1/256.
   a) If someone has selected one of these symbols and you need to discover which symbol it is by asking yes/no questions that will be truthfully answered, what is the most efficient sequence of asking such questions in order to discover the selected symbol?
   b) Show that each of these proposed questions is maximally informative.
   c) On average, how many such questions will need to be asked before the selected symbol is discovered?
3. The sum of the faces of two normal dice (six sided) when thrown is 7. How much information does this fact supply us with?
   Note: Outcomes such as (6,1) and (1,6) are to be considered as being different.
4. Consider two binary random variables X and Y with joint probability distribution p(x_i,y_j) given by
   p(0,0) = 1/2, p(0,1) = 1/4, p(1,0) = 1/8, and p(1,1) = 1/8.
   Find the value of H(X), H(Y), H(X|Y), H(Y|X), H(XY), and I(X;Y).
5. Of a group of students, 25% are not suitable for the University of Victoria. As the result of an admission selection, however, only 75% of these unsuitable students are rejected and 50% of all students are rejected.
   (a) How much information does one receive if a student, who knows that he is not suitable for UVic, hears the results of the selection?
   (b) Answer the previous question if the selection is determined by tossing a coin.
   (c) Compare the results in (a) and (b) and give an explanation for the difference.
6. The record of the UVic weatherperson is given in the table below.
   
   

   	Actual
   Prediction	Rain	No Rain
   Rain	1/8	3/16
   No Rain	1/16	10/16

   
   The values indicate the frequencies of the events. An engineering student notices that the weatherman is right only 12/16 of the time, but could be right 13/16 of the time by always predicting no rain. The student explains the situation and applies to be the new weatherperson, but the university turns him down. Explain why using information theory?
7. The inhabitants of a town can be divided into two groups, C and H. Half the people in group C tell the truth, three-tenths lie, and two-tenths refuse to answer. In group H, three-tenths of the people tell the truth, half lie, and two-tenths refuse to answer. Let p be the probability that a randomly selected person in the town will belong to group C. Let I = I(p) be the information conveyed about a person's truth-telling status by specifying the group they belong to. Find the maximum possible value of I and the percentage of people in group C corresponding to this maximum.

1. a) Consider a fair coin. When it is flipped, what is the mutual information between the top side and the bottom side of the coin?
   b) Consider a 6-sided fair die. When it is rolled, what is the mutual information between the top side and the front face (the side facing you)?
2. Chouinard Course Notes Problem 1.2
3. Let ABC be a discrete joint ensemble of three random variables. Prove the validity of the following inequalities and if true find conditions for equality. Venn diagrams are not sufficient.
   a) I(AB;C) ≥ I(A;C)
   b) H(AB|C) ≥ H(A|C)
   c) I(A;C|B) ≥ I(C;B|A) - I(C;B) + I(A;C)
   d) H(ABC) - H(AB) ≤ H(AC) - H(A)
4. For the following inequalities, determine the sign ≥, =, ≤ and justify your answer.
   a) H(5X) vs. H(X)
   b) I(g(X);Y) vs. I(X;Y)
   c) H(X₀|X₁) vs. H(X₀|X₁X₂)
   d) H(XY)/(H(X) + H(Y)) vs. 1
5. Construct a decision tree for buying a product prediction using the following training data
   
   • Age Group: {Young, Middle, Senior}
   • Income Level: {High, Medium, Low}
   • Student: {Yes, No}
   • Credit Rating: {Good, Poor}

   The output is Buy Product: {Yes, No}.

   Instance	Age Group	Income Level	Student	Credit Rating	Buy Product
   1	Young	High	No	Good	No
   2	Young	High	No	Poor	No
   3	Young	Medium	Yes	Good	Yes
   4	Young	Low	Yes	Poor	Yes
   5	Young	Medium	No	Good	Yes
   6	Middle	High	No	Good	Yes
   7	Middle	Medium	No	Poor	No
   8	Middle	Low	Yes	Good	Yes
   9	Middle	Low	No	Good	No
   10	Middle	Medium	Yes	Poor	Yes
   11	Senior	High	Yes	Good	Yes
   12	Senior	Medium	Yes	Poor	Yes
   13	Senior	Low	No	Poor	No
   14	Senior	High	No	Poor	No
   15	Senior	Medium	No	Good	Yes

   
   (b) Predict buying the product for the following instances
   
   

   Instance	Age Group	Income Level	Student	Credit Rating
   T1	Young	High	No	Good
   T2	Middle	Medium	Yes	Poor
   T3	Senior	Low	No	Poor
   T4	Senior	Medium	No	Good
   T5	Middle	High	No	Good
   T6	Young	Low	Yes	Good

   
   
6. The entropy of a discrete random variable is viewed as a measure of uncertainty. Verify this interpretation by proving that any transfer of probability from one symbol to another which makes the distribution more uniform will increase the entropy of the random variable.
7. Consider a three sided coin with outcomes a, b, and c having unknown probabilities p(a), p(b), and p(c), respectively.
   (a) Devise a means of using two flips of this three sided coin to simulate flipping a fair two sided coin. This should maximize the number of bits generated per flip of the three sided coin.
   (b) Determine the maximum number of bits generated per flip of the three sided coin.

1. An investment portfolio holds three assets that are all exposed to the same broad economic cycle: an equity index fund, a corporate bond fund, and a real estate fund.
   

   X = Equity fund, Y = Corporate bond fund, Z = Real estate fund

   The asset returns are classified as Up (1) or Down (0).
   Historical data gives the following joint probability distribution over 8 daily outcomes.
   
   

   X	Y	Z	P(X,Y,Z)
   0	0	0	7/20
   0	0	1	1/20
   0	1	0	1/20
   0	1	1	1/20
   1	0	0	1/20
   1	0	1	1/20
   1	1	0	1/20
   1	1	1	7/20

   
   a) Compute the Interaction Information I(X;Y;Z) and determine whether there is synergy or redundancy among the three assets.
   b) What would this mean in practice for an investment manager holding all three assets?
2. Let X, Y, Z be three random variables with a joint probability distribution p(x, y, z). The relative entropy between the joint distribution and the product of the individual distributions is D(p(x, y, z)||p(x)p(y)p(z))
   a) Expand this in terms of entropies.
   b) When is this quantity zero?
3. Consider a random variable X with four possible outcomes {x₁, x₂, x₃, x₄} and two probability distributions on X:
   p(x₁) = .5, p(x₂) = .25, p(x₃) = .125, p(x₄) = .125
   q(x₁) = .5, q(x₂) = a, q(x₃) = b, q(x₄) = c
   (a) Find the values of a, b, and c that minimize the cross entropy H(p,q) and the corresponding value of H(p,q). Show that this value is equal to H(p(X)) + D(p(X)||q(X)).
   (b) Suppose we know that c = 0.25. Find the values of a and b that minimize the cross entropy H(p,q) and the corresponding value of H(p,q). Show that this value is equal to H(p(X)) + D(p(X)||q(X)).
   (c) Compare the values of H(p,q) in (a) and (b) and provide an interpretation.
4. Determine which of the following codes is uniquely decodable and which are prefix codes.
   (a) {0,10,11}
   (b) {0,01,11}
   (c) {0,01,10}
   (d) {0,01}
   (e) {110,01,10,11}
   (f) {00,01,10,11}
   (g) {0, 00, 000, 0000}
5. Let X be a random variable with N equiprobable outcomes.
   a) Describe the optimal binary prefix code for this source (i.e. determine the codeword lengths), and compute the average codeword length L(C).
   b) Provide an optimal code for N = 9.
   c) For what values of N does L(C) = H(X)?
   
6. Find an optimal binary prefix code for the infinite source with probabilities
   p = {.9, .09, .009, .0009, … }
7. Consider two discrete memoryless sources. Source 1 has six symbols with probabilities 0.3,0.2,0.15,0.15,0.1 and 0.1. Source 2 has seven symbols with probabilities 0.3, 0.25, 0.15, 0.1, 0.1, 0.05 and 0.05. Construct a binary Huffman code and a ternary Huffman code for each source. Find the efficiency of each code. Are these codes unique in terms of the codeword lengths?

Aaron Gulliver
2026-10-20