learn.ifs.name

A Mathematical Theory of Communication

Shannon, 1948, A Mathematical Theory of Communication (Bell System Technical Journal)

Subscriber deck — free during early access

9 cards in “6 Choice, uncertainty and entropy” · whole deck

6 Choice, uncertainty and entropy

  1. What three properties did Shannon require of a measure of uncertainty \(H(p_1, \ldots, p_n)\)?
    (1) Continuous in the \(p_i\). (2) For equally likely events, a monotonically increasing function of \(n\). (3) If a choice is broken into successive choices, \(H\) is the weighted sum of the individual values of \(H\).
  2. Illustrate the decomposition requirement for \(H\) with probabilities ½, ⅓, ⅙.
    Choosing directly among three outcomes is equivalent to first choosing between two halves, then (half the time) between ⅔ and ⅓, so \(H(\tfrac12, \tfrac13, \tfrac16) = H(\tfrac12, \tfrac12) + \tfrac12 H(\tfrac23, \tfrac13)\).
    ½⅓⅙=½½⅔⅓½⅓⅙
  3. State Shannon’s Theorem 2 (the form of entropy).
    The only \(H\) satisfying continuity, monotonicity and decomposition is \(H = -K \sum_{i=1}^{n} p_i \log p_i\), with \(K\) a positive constant (which just fixes the unit). Shannon called it entropy, after the \(H\) of Boltzmann’s H theorem.
  4. Did Shannon rest the case for entropy on the uniqueness theorem?
    No: he said the theorem isn’t necessary for the theory and only lends plausibility; the real justification of the definitions lies in their implications (the coding theorems).
  5. What does the entropy of a binary choice look like?
    \(H = -(p \log p + q \log q)\), \(q = 1 - p\): zero when \(p = 0\) or \(1\), maximal at 1 bit when \(p = \tfrac12\), symmetric around it.
    0½1p01Hbits
  6. When is entropy zero, and when is it maximal?
    \(H = 0\) only when one outcome is certain. For \(n\) outcomes \(H\) is maximal, \(\log n\), when all are equally likely; any change toward equalizing the probabilities (an averaging of them) increases \(H\).
  7. How do joint and individual entropies relate?
    \(H(x, y) \le H(x) + H(y)\), with equality only if \(x\) and \(y\) are independent: the uncertainty of a joint event is at most the sum of the individual uncertainties.
  8. Define conditional entropy and state the chain rule.
    \(H_x(y) = -\sum_{i,j} p(i, j) \log p_i(j)\), the average uncertainty about \(y\) when \(x\) is known. Then \(H(x, y) = H(x) + H_x(y)\).
  9. Can knowing \(x\) increase our uncertainty about \(y\)?
    No: \(H(y) \ge H_x(y)\), with equality only if \(x\) and \(y\) are independent.

Source