代写COMP2610、代写Java，c++编程

日期：2022-09-22 06:36

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) 1X 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 Xsufficient 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]