cschaffner / informationtheory Goto Github PK

Homework 5 is now on staging. I have selected some exercises from previous years, so there is not a lot you need to check, except if all the material is going to be covered in the lecture. (specifically, channel capacity?)

I have also created a concept quiz on moodle, it would be great if you could check it. If not, just let me know, then I will recalculate some of the answers myself to minimize the error probability (kind of like a repetition code 😁 )

If you have any comments (about the homework or the concept quiz) I can implement them during the lecture tomorrow.

Section 1.9 (Further Reading) has a link to the pdf of Cramer and Fehr, but the link is broken. Also, I think that having a bibliography (or at least a different bibliography style that includes author names) would be very useful in general 👍

The link to CF is found at: https://github.com/cschaffner/InformationTheory/blob/master/Script/InfTheory3.tex#L58

Be more explicit about the definition of I(X;Y|Z=z). Same for conditional entropy earlier, be more explicit about H(X|Y=y).

I think we should have proper bibliographic references in the lecture notes (maybe in a seperate chapter at the end?), e.g. when referencing to the various Shannon theorems.
No hurry for now, but would be nice to have eventually.

The generator matrix should have 5 rows instead of 4.

I had a quick look at the homework set. I think it is fine, maybe a bit on the easy side. I would like them to prove the weak law of large number themselves, but as I do the symbol codes and arithmetic codes first, there's still time for that in next week's homework (before using it in the AEP).
In 2, we could draw the entropy diagram and ask them to fill in all numbers. The title of Problem 3 is a bit strange. Problem 5 should include a reference to the definition of relative entropy, as I will probably not talk about it in the lectures.

Also, can we change the exercise.sty template in a way that it becomes easy for them to directly insert their answers into the source? So we can tell them to download the .tex file and directly start editing there (with the obvious advantage of already having all the shortcuts defined, diagrams etc., and the obvious disadvantage the our source has to actually be clean, but that should probably be the case anyway, as it is on github...)

Maybe it would be fun to have some more challenging problem as well for those who dare. It does not have to be part of the homework, we could just put it on moodle as "Challenge of the week". For this week it could be: Find a discrete distribution with an infinite amount of entropy. I'm not sure if I can come up with a nice challenge every week, but it should be possible. ;-)

In chapter 1.1 (Definition 1.1.1 and 1.1.2), we have to check if the line "where by convention P[emptyset] = 0" is needed. And at the same time, if the probability measure P is well-defined (and that we don't run into issues when taking countable unions)

I've put up the practice & (partial) homework for week 4. I cannot access surfdrive right now (maintenance) so will do the rest of homework 4 next week. Assigning this issue to myself.

@cschaffner I checked the exercises on stochastic processed and they are not super hard, but for a practice session where the students are new to the topic I think they will be challenging enough. A quick overview for you before the werkcollege:

4(a) is pretty straightforward (compute entropy rate of i.i.d. bernoulli(p) samples, the answer is h(p)), 4(b) is the observation that this process has the same rate because there is a bijection between the two processes.

5 is that prove/disprove exercise. (a), (c) and (d) are true and are relatively straightforward to prove (applying the definition of stationary process and then maybe one or two steps before/after that). (b) is not true: it has a counterexample of X_1 through X_n being independent fair coin flips, and X_{n+i} = X_{i} from there. This process is stationary but H(X_n|X_0) = 0 < 1 = H(X_{n-1}|X_0).

6 is not a stationary process, but does converge to one (it is a finite-state, aperiodic and irreducible Markov chain*). Maybe we should split it up into two subexercises, first asking the students to draw transition graph and verify that it is aperiodic etc.

7 does not exist yet but I might want to add a starred exercise (suggestions are welcome). Or if I'm missing some of the lecture material please let me know.

*CT says that those chains become stationary as n goes to infinity. This seems intuitive if you draw a few diagrams but a proof is not given and I don't see where to start. If we can figure it out it might be an insightful exercise for the homework or exam?

I have added some practice problems for Tuesday's tutorial based on the ideas we discussed, can you have a look at them and make changes/additions as needed? They are in staging.

I've uploaded all of our files to the new repo. Maybe a slight overkill, but let's use the dev/staging/production structure, where we generally keep three branches active:

• Master (production): the one that the students can see, which contains only the completely finished chapters. Only hotfixes (typos, small errors) on this branch. It also contains the published homework sets.
• Staging: parts that are ready for review: all the content is there, but there might be errors / structural changes / additions, and there are still comments visible in the pdf.
• Development: where I/we work on new chapters. This is a separate branch so that the staging branch can quickly be pushed to production.

Right now I have put week 1 on production. I think you checked most of that already, but maybe you can still check out section 1.8 on relative entropy.

Week 2 is in staging: generally all of the content is there but it still needs to be checked.

PS week 2 is actually 1.5 week worth of content. Maybe we should rename it back to "Chapter" to avoid confusion?

1. Prove that average codeword length of non-prefix free arithmetic code is H(X) + 1
2. something with sampling from a non-uniform distribution using uniform bits, as in CT section 5.11

(For next year)

Provide higher precision table for problem 2b. Right now the result differs if the students calculate the values themselves instead of getting them from the table.

Throughout the section, we should check that the lemmas / theorems (and also text) reads "linear code" instead of "code" where applicable.