AUSTRALIAN NATIONAL UNIVERSITY COMP2610/COMP6261 Information Theory, Semester 2 2022 Assignment 2 Due Date: Monday 26 September 2022, 5:00 pm </br>Assignment 2 weighting is 20% of the course mark. 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 in the cover page. 3. All assignments must be done individually. Plagiarism is a university offence and will be dealtwith according to university procedureshttp://academichonesty.anu.edu.au/UniPolicy.html. 1 Question 1: Inequalities [20 marks total] **All students are expected to attempt this question. Question 1(a) Let the average height of a Raccoon is 10 inches. 1. UseMarkov’s inequality to derive an upper bound on the probability that a certain raccoon is at least 15 inches tall. (You may leave your answer as a fraction.) [3 Marks] 2. Suppose the standard deviation in raccoon’s height distribution is 2 inches. Use Cheby- shev’s inequality to derive a lower bound on the probability that a certain raccoon is between 5 and 15 inches tall. (You may leave your answer as a fraction.) [3 Marks] Question 1(b) A coin is known to land heads with probability (?) < 1/6 . The coin is flipped # times for some even integer # . 1. Using Markov’s inequality, provide a bound on the probability of observing #/3 or more heads. [3 Marks] 2. Using Chebyshev’s inequality, provide a bound on the probability of observing #/3 or more heads. Express your answer in terms of # . [3 Marks] 3. For # 2 {3, 6, . . . , 30}, in a single plot, show the bounds from part (a) and (b), as well as the exact probability of observing #/3 or more heads. [Note: To demonstrate, you can choose any specific value of p < 1/6. Also, you can choose any plotting tool] [8 Marks] 2 Question 2 : Markov Chain [30 marks total] **All students are expected to attempt this question. Question 2(a) Randomvariables - ,. , / are said to form aMarkov chain in that order (denoted by - ! . ! /) if their joint probability distribution can be written as: ?(- ,. , /) = ?(-) · ?(. |-) · ?(/ |. ) 1. Suppose (- ,. , /) forms a Markov chain. Is it possible for (-;. ) = (-; /)? If yes, give an example of - ,. , / where this happens. If no, explain why not. [3 Marks] 2. Suppose (- ,. , /) does not form a Markov chain. Is it possible for (-;. ) (-; /)? If yes, give an example of - ,. , / where this happens. If no, explain why not. [3 Marks] 3. If - ! . ! / then show that [6 Marks] • (-; /) (-;. ) • (-;. |/) (-;. ) Question 2(b) Let - ! (. , /) ! ) form a Markov chain, where by Markov property we mean: ?(G, H, I, C) = ?(G)?(H, I |G)?(C |H, I) Or simply: ?(C |H, I, G) = ?(C |H, I) Do the following: 1. Prove that (-;. , /) (-;)). [5 Marks] 2. Find the condition that (-;. , /) = (-;)). [3 Marks] Question 2(c) Recall that Markov’s inequality states that if - is a non-negative random variable, for any 0 > 0, %(- 0) E[-] 0 1. Give an example of a non-negative random variable X for which Markov’s statement is an equality, i.e.for any 0 > 0, [3 Marks] %(- 0) = E[-] 0 3 2. Given an example of a random variable . (not necessarily non-negative) for which Markov’s statement reverses, i.e. for any 0 0, [3 Marks] %(. 0) E[. ] 0 3. Let / be a random variable such that E[/] = 0. Then, for any 0 > 0, Markov’s inequality tells us that, for any 0 > 0, %( |/ | 0) E[|/ |] 0 while Chebyshev’s inequality tells us that %( |/ | 0) V[/] 02 Is it possible for the bound inMarkov’s inequality to be tighter than that from Chebyshev’s inequality for some 0 > 0, i.e. does there exist a / and 0 > 0 such that [2 Marks] E[|/ |] 0 < V[/] 02 ? If yes, provide an example of a random variable / and a number 0 > 0 for which this is true. If no, provide a proof that this is impossible. [2 Marks] 4 Question 3: AEP [25 marks total] **All students are expected to attempt this question. Let - be an ensemble with outcomes A- = {h, t} with ?⌘ = 0.8 and ?C = 0.2. Consider -# - e.g., # i.i.d flips of a bent coin. a) Calculate (-). [3 Marks] b) What is the size of the alphabet A-# of the extended ensemble -#? [3 Marks] c) What is the Raw bit content 0(-4)? [4 Marks] d) Express Entropy (-# ) as a function of N. [5 Marks] e) LetSX be the smallest set of #-outcome sequences with %(x 2 SX) 1 X where 0 X 1. Use any program language of your choice to plot 1# X (-# ) (‘Normalised Essential Bit Content’) vs X for various values of # (include some small values of # such as 10 as well as large values greater than 1000. Describe your observations and comment on any insights. [10 Marks] 5 Question 4: AEP [25 marks total] **Only COMP2610 students are expected to attempt this question. Let - be an ensemble with alphabet A- = {0, 1} and probabilities ( 25 , 35 ) a) Calculate (-). [3 Marks] b) Recall that -# denotes an extended ensemble. What is the alphabet of the extended ensemble -3? [2 Marks] c) Give an example of three sequences in the typical set (for # = 3, )#V = 0.2). [5 Marks] d) What is the smallest X sufficient subset of -3 when X = 1/25 andwhen X = 1/10 ? [5 Marks] e) Suppose # = 1000, what fraction of the sequences in -# are in the typical set (at V = 0.2) ? [7 Marks] f) If # = 1000, and a sequence in -# is drawn at random, what is the (approximate) probability that it is in the # , V-typical set? [3 Marks] 6 Question 5: AEP [25 marks total] **Only COMP6261 students are expected to attempt this question. Suppose a music collection consists of 4 albums: the album Alina has 7 tracks; the album Beyonce has 12; the album Cecilia has 15; and the album Derek has 14. 1. How many bits would be required to uniformly code: (a) all the albums? Give an example uniform code for the albums. [3 Marks] (b) only the tracks in the album Alina. Give an example of a uniform code for the tracks assuming they are named “Track 1”, “Track 2”, etc. [3 Marks] (c) all the tracks in the music collection? [2 Marks] 2. What is the rawbit content required to distinguish all the tracks in the collection? [2 Marks] 3. Suppose every track in the music collection has an equal probability of being selected. Let denote the album title of a randomly selected track from the collection. (a) Write down the ensemble for – that is, its alphabet and probabilities. [2 Marks] (b) What is the raw bit content of 4? [2 Marks] (c) What is the smallest value of X such that the smallest X-sufficient subset of 4 contains fewer than 256 elements? [2 Marks] (d) What is the largest value of X such that the essential bit content X ( 4) is strictly greater than zero? [2 Marks] 4. Suppose the album titles ensemble A is as in part (c). (a) Compute an approximate value for the entropy ( ) to two decimal places (you may use a computer or calculator to obtain the approximation but write out the expression you are approximating). [2 Marks] (b) Approximately how many elements are in the typical set )#V for when # = 100 and V = 0.1? [3 Marks] (c) Is it possible to design a uniform code to send large blocks of album titles with a 95% reliability using at most 1.5 bits per title? Explain why or why not. [2 Marks] 7
欢迎咨询51作业君