Entropy, Randomness, and Compression

Notes 43–44 · Lecture 22 · 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)\).

Today’s route

Question Tool Minutes
How much uncertainty? Entropy and counting 15
How many fair bits? Blocks and typical head counts 20
How should we encode symbols? Huffman’s greedy algorithm 25
What is the compression limit? Counting and concentration 15

One recurring idea: about \(2^{nH(p)}\) relevant possibilities require about \(nH(p)\) bits.

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

Uniform choices

If \(X\) is uniform on \(m\) possible outcomes, then

\[H(X)=\sum_{i=1}^m\frac1m\lg m=\lg m.\]

The probabilities matter; the names or numerical values of the outcomes do not.

A fair choice between \(-1\) and \(+1\) has the same entropy as a fair coin.

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

Why is the fair coin the maximum?

For \(0<p<1\),

\[H'(p)=\lg\frac{1-p}{p},\qquad H''(p)=-\frac1{p(1-p)\ln 2}<0.\]

The function is concave and symmetric about \(1/2\).

\[H(3/4)\approx0.8113,\qquad H(7/8)\approx0.5436.\]

Greater bias means less uncertainty.

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

The additivity calculation

Write \(p_x=\Pr[X=x]\) and \(q_y=\Pr[Y=y]\).

\[\begin{aligned} H(X,Y) &=\sum_{x,y}p_xq_y\lg\frac1{p_xq_y}\\ &=\sum_xp_x\lg\frac1{p_x}\sum_yq_y +\sum_yq_y\lg\frac1{q_y}\sum_xp_x\\ &=H(X)+H(Y). \end{aligned}\]

The factorization uses independence.

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

Entropy and counting fit together

Conditional on exactly \(j\) heads, every input string has the same probability.

The conditional distribution is uniform on \(\binom nj\) possibilities.

Near \(j=np\), the logarithm of this count is close to \(nH(p)\).

Concentration puts most probability near this head count.

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.

Powers of two are easy

If \(X\) is uniform on \(\{0,\ldots,2^k-1\}\), output its \(k\)-bit binary representation.

Every \(k\)-bit string appears exactly once.

Keep leading zeros: for \(k=3\), the value \(1\) gives 001.

We extract exactly \(k=H(X)\) fair bits.

A range that is not a power of two

Let \(X\) be uniform on \(\{0,\ldots,11\}\).

Input range Output Length
\(0,\ldots,7\) Binary representation of \(X\) \(3\)
\(8,\ldots,11\) Binary representation of \(X-8\) \(2\)

\[\Pr[Y=00\mid L=2]=\frac14, \qquad \Pr[Y=00]=\frac1{12}.\]

Uniformity is conditional on length.

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

The block bound: isolate the largest block

Write \(m=2^k+r\), where \(0<r<2^k\), and let \(u=\lfloor\lg r\rfloor\).

The first block outputs \(k\) bits. Apply induction to the remaining \(r\) inputs:

\[\begin{aligned} \mathbb E[L] &\geq\frac{2^k}{m}k+\frac rm(u-1)\\ &=k-\frac rm(k-u+1). \end{aligned}\]

We need to show that the loss is at most \(1\).

The block bound: control the loss

Since \(r<2^{u+1}\),

\[\frac rm=\frac r{2^k+r} \leq\frac{2^{u+1}}{2^k+2^{u+1}}.\]

Set \(d=k-u\geq1\).

\[\frac rm(k-u+1) \leq\frac{d+1}{1+2^{d-1}}\leq1.\]

The last inequality uses \(d\leq2^{d-1}\) for every integer \(d\geq1\).

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.

Most head counts are typical

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

\[\Pr[|J-np|\leq\varepsilon n] \geq1-2\exp\!\left(-\frac{n\varepsilon^2}{4p}\right).\]

On this event, \(j/n\in[p-\varepsilon,p+\varepsilon]\subset(1/2,1)\).

Here \(H\) is decreasing, so \(H(j/n)\geq H(p+\varepsilon)\).

A typical class contains many strings

Apply the binomial lower bound with \(q=j/n\):

\[\lg\binom nj\geq nH(j/n)-\lg(n+1).\]

For every typical \(j\),

\[\mathbb E[L\mid J=j] \geq nH(p+\varepsilon)-\lg(n+1)-2.\]

The losses from counting and rounding are only \(O(\lg n)\).

Extraction approaches the entropy rate

For sufficiently large \(n\),

\[\begin{aligned} \mathbb E[L]\geq{}& \left(1-2e^{-n\varepsilon^2/(4p)}\right)\\ &\cdot\left(nH(p+\varepsilon)-\lg(n+1)-2\right). \end{aligned}\]

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

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

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

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.

From extracting bits to storing symbols

We want to assign short codewords to frequent symbols and longer codewords to infrequent ones.

But concatenated codewords must still be decodable.

How can a receiver identify where each codeword ends?

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.

Decode by walking from the root

\[\texttt{010100}=\underbrace{\texttt{010}}_b\; \underbrace{\texttt{1}}_d\; \underbrace{\texttt{00}}_a.\]

Read bits until reaching a leaf, output its symbol, and return to the root.

The bit string decodes as bda.

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.

What does a merge cost?

Join two code trees under a new root.

Every leaf in either tree moves down by one edge.

If the total weights are \(w_A,w_B\), then

\[\operatorname{cost}(T) =\operatorname{cost}(A)+\operatorname{cost}(B)+w_A+w_B.\]

This suggests merging small weights first.

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.

Why should this greedy choice be safe?

We will show that some optimal tree has the two least frequent symbols as deepest siblings.

Merge those siblings into a single symbol.

The remaining tree must solve the smaller problem optimally.

Exchange argument + induction.

An optimal tree is full

Every internal node has exactly two children.

A node with one child can be contracted, shortening every codeword below it.

Since all frequencies are positive, the cost strictly decreases.

Therefore a deepest leaf has a sibling that is also a leaf at the same depth.

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.

Put the two rarest symbols together

Let \(x,y\) be the two least frequent symbols.

Choose a deepest sibling pair in an optimal full tree.

Swap labels to place \(x\) and \(y\) in those two positions.

Each swap has nonpositive cost change.

The resulting tree is still optimal, and \(x,y\) are deepest siblings.

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.

Induction on dyadic probabilities

The merged symbol has probability \(2p_i\).

By induction, its codeword length is

\[\lg\frac1{2p_i}=\ell_i-1.\]

Expanding the merged symbol adds one edge, giving length \(\ell_i\) for each child.

The other codeword lengths remain unchanged.

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.

Why not shorten every input?

There are \(2^n\) input strings of length \(n\).

There are only

\[1+2+\cdots+2^{n-1}=2^n-1\]

binary strings of length less than \(n\), including the empty string.

Lossless compression cannot shorten every input.

It can still shorten the likely inputs on average.

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.

Check your understanding

  1. Why does the block extractor sometimes output nothing?
  2. Where is independence used in \(H(S)=nH(p)\)?
  3. Why can the two least frequent symbols be placed deepest?
  4. Why is the compression lower bound asymptotic?

What to remember

\[H(X)=\mathbb E\!\left[\lg\frac1{p_X}\right], \qquad \binom n{nq}\approx2^{nH(q)}.\]

Extract randomness by finding a uniform class and decomposing it into powers of two.

Build an optimal prefix code by repeatedly merging the two least frequent symbols.

Entropy is the asymptotic rate for both extraction and compression.

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.