Mathematics RU

Practice · Chapter 50

Entropy, codes and chains

How much information an outcome carries, Shannon entropy, the average code length and Huffman codes, and the share of time a Markov chain spends in each state.

How to solve it

The more surprising an outcome, the more information it carries: an outcome of probability $\frac{1}{8}$ is $3$ bits, like three yes/no answers. Entropy is the average information per outcome, and also the lower bound for the average length of any code: lossless compression cannot go below it.

Step by step

  1. The information of an outcome of probability $p$: $\log_2 \frac{1}{p}$ bits.
  2. Entropy is the weighted average: $H = \sum p_i \log_2 \frac{1}{p_i}$.
  3. The average code length is $\sum p_i \ell_i$, where $\ell_i$ is the length of a letter's code.
  4. A Huffman code: merge the two rarest symbols into one with their total probability until one is left. A symbol's code length is how many merges it took part in.
  5. A Markov chain: in equilibrium the flow out of each state equals the flow into it.
The probabilities of the outcomes, adding up to $1$. Example: $\left(\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{8}, \frac{1}{8}\right)$: $3 \cdot \frac{1}{4} \cdot 2 + 2 \cdot \frac{1}{8} \cdot 3 = \frac{3}{2} + \frac{3}{4} = \frac{9}{4}$ bits.

Common mistakes

  • Taking $\log_2 p$ without the minus or the flipped fraction — entropy is never negative.
  • Adding code lengths without weights: frequent letters count more often.
  • Merging the most frequent symbols in Huffman's algorithm instead of the rarest.
  • Confusing a transition probability in a Markov chain with the share of time in a state.

Example

Mathematics

Chapters

Introduction

  1. 0 What mathematics is

I Numbers

  1. 1 Counting
  2. 2 Zero and minus
  3. 3 Primes
  4. 4 Divisibility
  5. 5 Fractions
  6. 6 Root two

II Algebra

  1. 7 Letters
  2. 8 Equations
  3. 9 Functions and graphs
  4. 10 Quadratic equations
  5. 11 Systems and inequalities
  6. 12 Powers and logarithms
  7. 13 Sequences
  8. 14 Polynomials
  9. 15 Complex numbers

III Geometry

  1. 16 Euclid's Elements
  2. 17 The triangle
  3. 18 Pythagoras' theorem
  4. 19 The circle and π
  5. 20 Area and volume
  6. 21 Trigonometry
  7. 22 Vectors
  8. 23 Symmetry
  9. 24 Conic sections

IV Calculus

  1. 25 Limits
  2. 26 The derivative
  3. 27 Extrema
  4. 28 The integral
  5. 29 The number e
  6. 30 Series
  7. 31 Differential equations
  8. 32 Several variables
  9. 33 Fourier series
  10. 34 Complex analysis

V Linear algebra

  1. 35 Matrices
  2. 36 Gaussian elimination
  3. 37 Vector spaces
  4. 38 Eigenvectors
  5. 39 Least squares and SVD

VI Structures

  1. 40 Groups
  2. 41 Remainders and ciphers
  3. 42 Rings and fields
  4. 43 Galois theory
  5. 44 Zeta and curves

VII Chance & data

  1. 45 Combinatorics
  2. 46 Graphs
  3. 47 Probability
  4. 48 Random variables
  5. 49 Statistics
  6. 50 Markov and information

VIII Foundations

  1. 51 Logic and sets
  2. 52 Infinities
  3. 53 Rigorous analysis
  4. 54 Measure and integral
  5. 55 Functional analysis
  6. 56 Gödel and Turing

IX Horizons

  1. 57 Topology
  2. 58 Non-Euclidean geometries
  3. 59 Chaos and fractals
  4. 60 The frontier