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

7 cards in “7 The entropy of an information source” · whole deck

7 The entropy of an information source

  1. How is the entropy of a Markov source defined?
    The average of the entropies \(H_i\) of the next-symbol distribution in each state, weighted by the state probabilities: \(H = \sum_i P_i H_i = -\sum_{i,j} P_i\,p_i(j) \log p_i(j)\) bits per symbol. Per second, \(H' = mH\) for \(m\) symbols per second.
  2. What does the asymptotic equipartition result (Theorem 3) say?
    For long sequences, almost all probability goes to sequences whose probability \(p\) satisfies \(\frac{\log p^{-1}}{N} \approx H\). So we may treat long sequences as if there were just \(2^{HN}\) of them, each with probability \(2^{-HN}\).
  3. What are \(G_N\) and \(F_N\), and how do they approach the source entropy?
    \(G_N = -\frac1N \sum p(B) \log p(B)\) over blocks \(B\) of \(N\) symbols (entropy per symbol of blocks); \(F_N\) is the conditional entropy of the next symbol given the \(N - 1\) before it, the entropy of the \(N\)th-order approximation. Both decrease monotonically to \(H\), and \(F_N \le G_N\) is the better estimate.
  4. Define relative entropy and redundancy in Shannon’s sense.
    Relative entropy: the ratio of a source’s entropy to the maximum it could have with the same symbols, which is the maximum compression into the same alphabet. Redundancy = 1 − relative entropy.
  5. What did Shannon estimate the redundancy of English to be, and what does it mean?
    Roughly 50%, counting statistical structure over about eight letters: half of what we write is determined by the structure of the language and half is chosen freely.
  6. How did Shannon estimate the redundancy of English?
    By several independent methods that agreed: computing the entropy of the approximations to English, deleting a fraction of letters and having people restore them, and known results in cryptography.
  7. How does redundancy relate to crossword puzzles?
    With zero redundancy any letter array would be a crossword; with too much, constraints make large crosswords impossible. Under random-like constraints large two-dimensional crosswords are just possible at 50% redundancy, and three-dimensional ones at about 33%.

Source