COMP2610/COMP6261 Information Theory, Semester 2 2023 Assignment 2

Instructions:

Marks:

1.  The mark for each question is indicated next to the question.  For questions where you are asked to prove results, if you can not prove a precedent part, you can still attempt subsequent parts of the question assuming the truth of the earlier part.

2.  COMP2610 students:  Answer Questions 1-3 and  Question 4.  You are not expected to answer Question 5. You will be marked out of 100.

3.  COMP6261 students:  Answer Questions 1-3 and  Question 5.  You are not expected to answer Question 4. You will be marked out of 100.

Submission:

1.  Submit your assignment together with a cover page as a single PDF on Wattle.

2.  Clearly mention whether you are a COMP2610 student or COMP6261 student on the cover page.

3. A late submission attracts a penalty of 5% per working day as per ANU Policy until  a week (5 working days) from the due date.  We will provide solutions to the assignment after a week from the due date and if you submit after that time you get zero marks (100% penalty). Extensions will be considered according to the ANU Policy.

4. All assignments must be done individually. Plagiarism is a university offence and will be

dealt with according to university procedures http://academichonesty.anu.edu.au/UniPolicy.html.

Question 1: Inequalities  [20 marks total]

**All students are expected to attempt this question.

Question 1(a)

Suppose a fast food restaurant, MC, sells 2000 burgers per day on average.

1.  Use Markov’s inequality to derive an upper bound on the probability that more than 2400 burgers are sold tomorrow. (You may leave your answer as a fraction.)             [3 Marks]

2.  Suppose the standard deviation of burgers sold per day is 200. Use Chebyshev’s inequality to derive a lower bound on the probability that MC will sell between 1600 and 2400 burgers tomorrow (You may leave your answer as a fraction.)                                        [3 Marks]

Question 1(b)

A coin is known to land heads with probability (p) < 1/8 .  The coin is flipped N times for some even integer N.

1. Using Markov’s inequality, provide a bound on the probability of observing N/4 or more heads.                                                                                                           [4 Marks]

2. Using Chebyshev’s inequality, provide a bound on the probability of observing N/4 or more heads. Express your answer in terms of N.                                               [4 Marks]

3.  For N ∈ {4, 8, . . . , 40}, in a single plot, show the bounds from part (1) and (2), as well as the exact probability of observing N/4 or more heads.  [Note:  To demonstrate, you can choose any specific value of p < 1/8. Also, you can choose any plotting tool] [6 Marks]

Question 2 : Markov Chain  [30 marks total]

**All students are expected to attempt this question.

Question 2(a)

Random variables X, Y, Z are said to form a Markov chain in that order (denoted by X → Y → Z) if their joint probability distribution can be written as:

p(X, Y, Z) = p(X) · p(Y |X) · p(Z |Y)

1.  Suppose (X, Y, Z) forms a Markov chain.  Is it possible for I (X; Y) = I (X; Z)?  If yes, give an example of X, Y, Z where this happens. If no, explain why not.            [4 Marks]

2.  Suppose (X, Y, Z) does not form a Markov chain.  Is it possible for I (X; Y)  ≥ I (X; Z)? If yes, give an example of X, Y, Z where this happens. If no, explain why not. [4 Marks]

3. If X → Y → Z then show that                                                                          [6 Marks]

. I (X; Z) ≤ I (X; Y)

. I (X; Y |Z) ≤ I (X; Y)

Question 2(b)

Let X → (Y, Z) → T form a Markov chain, where by Markov property we mean:

p(x, y, z, t) = p(x)p(y, z|x)p(t|y, z)

Or simply:

p(t|y, z, x) = p(t|y, z)

Do the following:

1. Prove that I (X; Y, Z) ≥ I (X; T) .                                                                     [5 Marks]

2. Find the condition that I (X; Y, Z) = I (X; T) .                                                  [3 Marks]

Question 2(c)

Let X1  → X2  → X3  → · · · → Xn form a Markov chain in this order. Thus, the joint probability of X1, . . . , Xn  are given by

p(x1 , x2 , . . . , xn) = p(xn|xn−1)p(xn−1 |xn−2) · · · p(x2 |x1)p(x1) .

1. Express I (X1; X2, . . . , Xn) in terms of its entropy and conditional entropy        [2 Marks]

2.  Simplify the entropy expression you derived above to reduce I (X1; X2, . . . , Xn) to its simplest form.  Please do not use other methods to simplify, you will not receive any marks.          [6 Marks]

Question 3: AEP  [25 marks total]

**All students are expected to attempt this question.

Let X be an ensemble with outcomes A X  = {h, t} with ph  = 0.8 and pt  = 0.2.  Consider XN - e.g., N i.i.d flips of a bent coin.

a) Calculate H(X) .                                                                                                 [3 Marks]

b) What is the size of the alphabet A XN   of the extended ensemble XN?                    [3 Marks]

c) What is the raw bit content H0(X4)?                                                                   [4 Marks]

d) Express entropy H(XN) as a function of N.                                                          [5 Marks]

e)  LetSδ be the smallest set of N-outcome sequences with p(x ∈ Sδ) ≥ 1 − δ where 0 ≤ δ ≤ 1. Use any program language of your choice to plot ) (‘Normalised Essential Bit Content’) vs δ for various values of N (include some small values of N such as 10 as well as large values greater than 1000. Describe your observations and comment on any insights. Please also include your code file as part of your answer.                                  [10 Marks]

Question 4: AEP  [25 marks total]

**Only COMP2610 students are expected to attempt this question.

Let X be an ensemble with alphabet A X  =  , )

a) Calculate H(X) .                                                                                                 [3 Marks]

b)  Recall that XN denotes an extended ensemble. What is the alphabet of the extended ensemble X3?         [2 Marks]

c)  Give an example of three sequences in the typical set (for N = 3, β = 0.2).           [5 Marks]

d) What is the smallest δ−sufficient subset of X3 when δ = 1/25 and when δ = 1/10 ? [5 Marks]

e)  Suppose N = 1000, what fraction of the sequences in XN  are in the typical set (at β = 0.2) ?                                          [7 Marks]

f)  If N = 1000, and a sequence in XN is drawn at random, what is the (approximate) probability that it is in the N, β-typical set?       [3 Marks]