Course 375 Information Theory

Sample Exam

1991

Answer as many questions as you can; all carry the same number of marks.

1. Define the entropy

H(X) = H(p_{1}, …, p_{n})

of a finite probability space X; and show that the entropy is maximised for given n when the probabilities are equal. When is it minimised?

2. Show that the joint entropy H(XY) of 2 finite (but not necessarily independent) probability spaces X, Y satisfies

H(XY) ≤ H(X) + H(Y).

3. Define the algorithmic entropy H(s) of a string s. Extending the definition to the entropy H(n) of a natural number n, show that

H(s) ≤ ∥s∥ + H(∥s∥) + O(1),

where ∥s∥ denotes the length of the string s.

Sketch the proof that this is (in a sense to be defined) the best possible result.

4. What is meant by saying that a set S = {s_{i}} of strings is prefix-free? Show that if the set {n_{i}} of natural numbers satisfies

∑_{i} 2^{−n_{i}} ≤ 1

then a prefix-free set {s_{i}} of strings can be found such that

∥s_{i}∥ ≤ n_{i}.

5. Define the statistical algorithmic entropy h(s) of a string s; and show

that

h(s) = H(s) + O(1).

6. Define the joint entropy H(s, t) of 2 strings s, t, and the relative entropy H(s | t) of s given t; and show that

H(s, t) = H(s) + H(t | s) + O(1).