Entropy, Randomness, and Compression

Notes 43–44 · 15-minute mathematical summary · November 6, 2026

Sariel Har-Peled

CS 574 · University of Illinois, Urbana-Champaign

Entropy measures average surprise

Let \(p_x=\Pr[X=x]\) for a discrete random variable \(X\).

\[H(X)=\sum_{x:p_x>0}p_x\lg\frac1{p_x} =\mathbb E\!\left[\lg\frac1{p_X}\right].\]

An outcome of probability \(p_x\) contributes \(\lg(1/p_x)\) bits of surprise.

All logarithms denoted by \(\lg\) are base \(2\). Set \(0\lg 0=0\).

Binary entropy

A coin is heads with probability \(p\).

\[H(p)=-p\lg p-(1-p)\lg(1-p).\]

Binary entropy, from the lecture notes.

\(H(0)=H(1)=0\), while \(H(1/2)=1\).

Independent sources add their entropy

If \(X\) and \(Y\) are independent, then

\[H(X,Y)=H(X)+H(Y).\]

Independence factors probabilities; logarithms turn products into sums.

For \(n\) independent flips \(S=(S_1,\ldots,S_n)\),

\[\boxed{H(S)=nH(p).}\]

Counting strings with a fixed number of heads

Exactly \(j\) heads among \(n\) flips gives \(\binom nj\) possible strings.

For \(q=j/n\),

\[\boxed{\frac{2^{nH(q)}}{n+1}\leq\binom nj\leq2^{nH(q)}.}\]

Taking logarithms,

\[nH(q)-\lg(n+1)\leq\lg\binom nj\leq nH(q).\]

What counts as extracted randomness?

Let \(Y=\operatorname{Ext}(X)\) be a binary string and \(L=|Y|\) its length.

For every \(k\) with \(\Pr[L=k]>0\), require

\[\Pr[Y=y\mid L=k]=2^{-k} \quad\text{for every }y\in\{0,1\}^k.\]

Conditional on the output length, the bits are independent and fair.

The empty output (\(k=0\)) is allowed.

Decompose the range into blocks

Write \(m\) in binary: \(m=\sum_i a_i2^i\), with \(a_i\in\{0,1\}\).

For m = 15, use blocks of sizes 8, 4, 2, and 1.

Within a block of size \(2^i\), output the offset using exactly \(i\) bits.

Each block produces all bit strings of its length equally often.

How many bits do the blocks produce?

For \(m=15=8+4+2+1\),

\[\mathbb E[L]=\frac{8\cdot3+4\cdot2+2\cdot1+1\cdot0}{15} =\frac{34}{15}.\]

For every positive integer \(m\), the block extractor satisfies

\[\boxed{\mathbb E[L]\geq\lfloor\lg m\rfloor-1.}\]

Its expected output is within fewer than two bits of \(H(X)=\lg m\).

A biased coin hides uniform distributions

Let \(S\) consist of \(n\) independent flips with heads probability \(p\), and let \(J\) count heads.

Every string with exactly \(j\) heads has probability

\[p^j(1-p)^{n-j}.\]

Conditional on \(J=j\), rank the input among the \(\binom nj\) such strings.

That rank is uniform on \(\{0,\ldots,\binom nj-1\}\).

Extract from the rank

  1. Count the heads: \(j\).
  2. Rank the input within the strings having \(j\) heads.
  3. Apply the block extractor to a uniform range of size \(\binom nj\).

\[\mathbb E[L\mid J=j]\geq \left\lfloor\lg\binom nj\right\rfloor-1.\]

Mixing over head counts preserves uniformity conditional on output length.

What the extraction theorem says

For fixed \(1/2<p<1\), \(0<\delta<1\), and sufficiently large \(n\),

\[ (1-\delta)nH(p)\leq \max_{\operatorname{Ext}}\mathbb E[|\operatorname{Ext}(S)|] \leq nH(p).\]

The output is exactly uniform given its length.

The amount extracted is close to entropy on average.

No extractor beats entropy in expectation

Fix an input \(x\) of probability \(q_x>0\), and let \(y=\operatorname{Ext}(x)\) have length \(\ell\).

\[q_x\leq\Pr[Y=y]=\frac{\Pr[L=\ell]}{2^\ell}\leq2^{-\ell}.\]

Hence \(|\operatorname{Ext}(x)|\leq\lg(1/q_x)\).

\[\boxed{\mathbb E[L]\leq\sum_xq_x\lg\frac1{q_x}=H(X).}\]

For the coin sequence, \(H(X)=nH(p)\).

A code is a tree

A prefix tree from Notes 44.

\[a\mapsto00,\quad b\mapsto010,\quad c\mapsto011,\quad d\mapsto1.\]

Prefix-free: no codeword is a prefix of another. Codeword length equals leaf depth.

Huffman’s algorithm

Start with one weighted leaf for each symbol.

  1. Remove the two trees of smallest total weight.
  2. Join them under a new root whose weight is their sum.
  3. Insert the merged tree and repeat until one tree remains.

This minimizes \(\operatorname{cost}(T)=\sum_i f_i d_T(i)\), where \(f_i>0\) is a symbol frequency and \(d_T(i)\) its leaf depth.

Huffman coding is optimal

Theorem. Huffman’s algorithm produces an optimal binary prefix-free code.

Move the two least frequent symbols to deepest sibling positions: swapping a rare symbol deeper changes cost by \((f_x-f_\alpha)\Delta\leq0\).

Contract the pair into one symbol of weight \(f_x+f_y\); induction gives an optimal smaller tree.

Expanding the pair adds the same \(f_x+f_y\) to both costs.

When probabilities are powers of two

Suppose \(p_i=2^{-\ell_i}\), where \(\ell_i\) are nonnegative integers and \(\sum_i p_i=1\).

Huffman assigns symbol \(i\) a codeword of length

\[\ell_i=\lg\frac1{p_i}.\]

The two smallest probabilities are equal; merging them doubles their probability.

The Huffman compression guarantee

A message \(S\) has \(m\) symbols, with frequencies \(f_i\) and \(p_i=f_i/m\).

\[\boxed{\text{Huffman encoded length}\leq m\bigl(H(X)+1\bigr).}\]

The cost of storing the codebook is excluded.

For dyadic probabilities, the encoded length is exactly \(mH(X)\).

Compress an entire block of flips

Now allow a different codeword for each complete input string \(s\in\{0,1\}^n\).

A lossless compression function \(C\) is injective:

\[s\ne t\quad\Longrightarrow\quad C(s)\ne C(t).\]

The decoder knows where the encoded block ends.

The next lower bound applies even without a prefix-free requirement.

The asymptotic compression theorem

Fix \(1/2<p<1\) and \(0<\delta<1\). Let \(S\) be \(n\) independent flips.

For sufficiently large \(n\),

\[\boxed{(1-\delta)nH(p)\leq \min_{C\text{ injective}}\mathbb E[|C(S)|] \leq(1+\delta)nH(p).}\]

The upper bound constructs a code; the lower bound constrains every code.

Two directions, one rate

Task on \(n\) independent flips Optimal expected length
Extract independent fair bits \((1-o(1))nH(p)\)
Store the input losslessly \((1+o(1))nH(p)\)

Counting identifies the scale \(2^{nH(p)}\).

Concentration makes that scale relevant to almost all probability mass.

Reading

Notes 43: Entropy, Randomness, and Information.

Notes 44: Entropy II.

The notes follow Michael Mitzenmacher and Eli Upfal, Probability and Computing (2005), §§9.1–9.3.