1

Problem sheet 1, 2005, Oct. 5  MT441 Channels

Ex. 1 Verify that the function H(p_{1}, …, p_{n}) = − ∑_{k} p_{k} log_{2} p_{k} satisfies all 8 axioms on H.

Ex. 2 (Not to be handed in). List as many of the 8 axioms as you can, (without just looking at the notes).

Ex. 3 Let X be a random variable, taking the values a_{1} and a_{2} with probability p_{1} and p_{2}, respectively. Let Y be a random variable, taking the values b_{1}, b_{2} and b_{3} with probability q_{1}, q_{2} and q_{3}, respectively. Prove that H(X, Y) ≤ H(X) + H(Y), with equality if and only if X and Y are independent. (You should work through the proof here, not just say that this is a special case of a more general theorem stated in the lecture).

Ex. 4 Two fair dice are thrown. X denotes the value obtained by the first, and Y the value obtained by the second, and let Z = X + Y be the corresponding random variable. Evaluate H(X), H(Y), H(X, Y), H(Z), H(X|Y). From this, verify that H(X, Y) = H(X) + H(Y) and show that H(Z) < H(X, Y).

Ex. 5 Show that, for any random variable H(X, X^{2}) = H(X). Show that H(X^{2}|X) = 0 but that H(X|X^{2}) is not necessarily zero.

Ex. 6 The random variable X takes the values 1, 2, …, 2N with equal probability. The random variable Y is defined by

Y = \begin{cases}0 & if X is even, \\ 1 & if X is odd. \end{cases}

Evaluate H(X|Y), and show that H(Y |X) = 0.

Ex. 7 (Think about this one for a while). Suppose you want to compress, encode and encrypt a message. (Compression for shortening the data if possible, encoding for securing against noise on the channel, encryption to keep the message secret). Does it matter in which order you do this, and if yes, in which order should you do it?

Ex. 8 Make yourself familiar with the restricted bookshelf, there are copies of the recommended books, (Welsh, MCKay, Jones and Jones, Hill). (The restricted bookshelf is behind the counter on the left hand side, then inside at the very end close to the copy machine, 001.5*** .. library coding).

To be returned in one week, before the lecture. My web page contains a collection of related material. http://www.ma.rhul.ac.uk/∼elsholtz/WWW/lectures/0506mt441/lecture.html