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.

Aaron Gulliver
2026-09-16