Information Theory

Points covered:

• Shannon entropy
• Optimum code length
• Divergence measures (Kullback-Liebler, etc)
• Various theorems and their proofs regarding entropies and relative entropies. If $P = (p_1, p_2, \cdots, p_n)$, then

  1.

  $H(P) = \sum_{i=1}^n p_i \log p_i$

  2.

  $\underset{P}{\rm argmax}\quad H(P) = (1/n, 1/n, \cdots, 1/n)$

  3.

  $H(P) \ge 0$ with equality iff some $p_i \in P = 1$

  4.

  $H(P) \le -\sum_{i=1}^n p_i \log q_i$ with equality iff $p_i = q_i \forall i$

• Prefix codes
• Kraft inequality

Read the two papers given: Shannon's seminal BSTJ report (1949) and the Village paper (1999) by myself and Ray Kemp.

What is information?

Pay particular attention to how Shannon characterizes information Section 6 (p.10) of the report. This is crucial in proving his result later on.

Information is quantified by the measure of how much ``choice'' is involved in the event selection. This measure, $H(p_1, p_2, \cdots, p_i)$, where the p_i are the probabilities of occurrences of the events whose info-content H is trying to quantify, must have the following desirable properties:

1.

H should be continuous in the p_i

2.

If all the p_i are equal, p_i = 1/n, then H should be a monotonic increasing function of n. With equally likely events there is more choice, or uncertainty, when there are more possible events.

3.

If a choice be broken down into two successive choices, the original H should be the weighted sum of the individual values of H.

Ponder:

• Is the above characterization of information sensible?
• Can you think of any other way of characterizing information?