Entropy, Randomness, and Compression

Notes 43–44 · Condensed lecture · November 6, 2026

Sariel Har-Peled

CS 574 · University of Illinois, Urbana-Champaign

How many bits are in a biased coin?

A source produces \(n\) independent coin flips, with heads probability \(p\).

Extraction: how many fair bits can we obtain?

Compression: how many bits do we need to store the source?

The same quantity governs both answers: \(nH(p)\).

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).\]

The counting upper bound

Flip a coin with heads probability \(q=j/n\).

The probability of exactly \(j\) heads is at most \(1\):

\[\binom njq^j(1-q)^{n-j}\leq1.\]

But \(q^j(1-q)^{n-j}=2^{-nH(q)}\). Therefore

\[\binom nj\leq2^{nH(q)}.\]

The counting lower bound

Let \(\mu(k)=\binom nkq^k(1-q)^{n-k}\), where \(nq=j\) is an integer.

\[\frac{\mu(k+1)}{\mu(k)}=\frac{n-k}{k+1}\frac q{1-q}.\]

The terms increase up to \(j\) and decrease after \(j\).

The largest of \(n+1\) nonnegative terms summing to \(1\) is at least \(1/(n+1)\):

\[\binom nj2^{-nH(q)}=\mu(j)\geq\frac1{n+1}.\]

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.

An extraction example

The input 10 has offset 2 inside the block from 8 through 11.

For \(m=15\) and \(X=10\), output 10: the two-bit representation of \(10-8=2\).

The singleton block at \(14\) produces the empty string.

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)\).

Prefix-free codes

A binary code is prefix-free if no codeword is a prefix of another codeword.

Store symbols at the leaves of a binary tree.

An edge to the left contributes 0; an edge to the right contributes 1.

The codeword length is the leaf’s depth.

A code is a tree

A prefix tree from Notes 44.

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

No leaf lies on the path to another leaf.

The objective

Let \(f_i>0\) be the frequency of symbol \(i\) and \(d_T(i)\) its depth in tree \(T\).

\[\operatorname{cost}(T)=\sum_i f_i\,d_T(i).\]

This is the total encoded message length, excluding the codebook.

Dividing by the message length gives the average number of bits per symbol.

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.

Rare symbols tend to participate in more merges and acquire longer codewords.

Move a rare symbol deeper

Suppose \(f_x\leq f_\alpha\) and \(\alpha\) is \(\Delta\geq0\) levels deeper than \(x\).

Swap the two leaf labels.

\[\operatorname{cost}(T')-\operatorname{cost}(T) =(f_x-f_\alpha)\Delta\leq0.\]

Moving the less frequent symbol deeper cannot increase cost.

Contract the sibling pair

Replace \(x,y\) by one symbol \(z\) of frequency \(f_z=f_x+f_y\).

\[\operatorname{cost}(T) =\operatorname{cost}(T')+f_x+f_y.\]

The last edge to \(x\) or \(y\) contributes exactly \(f_x+f_y\).

If \(T'\) were not optimal for the contracted alphabet, replacing it would improve \(T\).

Huffman coding is optimal

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

Some optimum makes the first chosen pair siblings.

After contracting that pair, induction gives an optimal smaller Huffman 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.

Entropy appears as average code length

For dyadic probabilities, let \(\overline\ell\) be the average codeword length.

\[\overline\ell=\sum_i p_i\ell_i =\sum_i p_i\lg\frac1{p_i}=H(X).\]

The same expression measures uncertainty, extractable randomness, and coding cost.

Arbitrary probabilities: round downward

For each used symbol, set

\[q_i=2^{\lfloor\lg p_i\rfloor}.\]

\[q_i\leq p_i<2q_i, \qquad \lg\frac1{q_i}<1+\lg\frac1{p_i}.\]

Each \(q_i\) is a power of two, but their sum may be smaller than \(1\).

Fill the missing probability mass

Write \(1-\sum_iq_i\) as a finite sum of powers of two.

Introduce dummy symbols with these probabilities.

The resulting distribution is dyadic and sums to \(1\).

Huffman gives every original symbol a codeword of length \(\lg(1/q_i)\).

For an input of length \(m\), the frequencies \(p_i=f_i/m\) ensure only \(O(\lg m)\) dummy symbols are needed.

A code within one bit of entropy

Evaluate the constructed code under the original probabilities:

\[\begin{aligned} \overline\ell &=\sum_i p_i\lg\frac1{q_i}\\ &\leq\sum_i p_i\left(1+\lg\frac1{p_i}\right) =H(X)+1. \end{aligned}\]

Remove dummy leaves and contract nodes with one child; codewords only get shorter.

Huffman for the original frequencies is at least as good as this code.

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.

Compression: encode a likely set by rank

Choose \(0<\varepsilon<\min\{p-1/2,1-p\}\) and let

\[A=\{s:J(s)\geq\lceil n(p-\varepsilon)\rceil\}.\]

If \(s\in A\), output 0 followed by its fixed-width rank in \(A\).

Otherwise, output 1 followed by the original \(n\) bits.

The first bit identifies the decoding rule.

How large is the likely set?

Let \(k_0=\lceil n(p-\varepsilon)\rceil\). For \(j\geq k_0>n/2\),

\[\binom nj\leq\binom n{k_0}\leq2^{nH(p-\varepsilon)}.\]

\[|A|=\sum_{j=k_0}^n\binom nj \leq(n+1)\,2^{nH(p-\varepsilon)}.\]

The rank needs at most \(nH(p-\varepsilon)+\lg(n+1)+1\) bits.

The fallback is exponentially rare

Chernoff gives

\[\Pr[S\notin A]\leq e^{-n\varepsilon^2/(2p)}.\]

\[\begin{aligned} \mathbb E[|C(S)|]\leq{}&nH(p-\varepsilon)+\lg(n+1)+2\\ &+(n+1)e^{-n\varepsilon^2/(2p)}. \end{aligned}\]

First choose \(\varepsilon\) small, then \(n\) large:

\[\mathbb E[|C(S)|]\leq(1+\delta)nH(p).\]

A shortest code favors likely inputs

Suppose \(\Pr[S=s]>\Pr[S=t]\) but \(|C(s)|>|C(t)|\).

Swapping their codewords changes expected length by

\[-\bigl(\Pr[S=s]-\Pr[S=t]\bigr) \bigl(|C(s)|-|C(t)|\bigr)<0.\]

In an optimal injective code, a more likely input never has a longer codeword than a less likely input.

A large class forces a long codeword

Take \(\tau=\lfloor n(p+\varepsilon)\rfloor\) and \(M=\binom n\tau\).

Some input with \(\tau\) heads must have codeword length at least

\[\lg M-1.\]

Otherwise, there are too few distinct short binary strings to encode all \(M\) inputs.

Since \(M\geq2^{nH(p+\varepsilon)}/(n+1)\), this length is at least

\[\mu=nH(p+\varepsilon)-\lg(n+1)-1.\]

Most inputs are less likely than that input

For a specific string with \(j<\tau\) heads,

\[\frac{p^j(1-p)^{n-j}}{p^\tau(1-p)^{n-\tau}} =\left(\frac{1-p}{p}\right)^{\tau-j}<1.\]

By optimality, every input with \(J<\tau\) needs at least \(\mu\) bits.

And \(\Pr[J<\tau]=1-o(1)\) by concentration, since \(\tau\) is above \(np\) by order \(n\).

The compression lower bound

For an optimal code and sufficiently large \(n\),

\[\mathbb E[|C(S)|]\geq \Pr[J<\tau]\left(nH(p+\varepsilon)-\lg(n+1)-1\right).\]

Choose \(\varepsilon\) small using continuity, then \(n\) large:

\[\boxed{\mathbb E[|C(S)|]\geq(1-\delta)nH(p).}\]

Every other injective code has at least this expected length.

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.