Notes 43–44 · Lecture 22 · November 6, 2026
CS 574 · University of Illinois, Urbana-Champaign
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)\).
| 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.
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\).
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.
A coin is heads with probability \(p\).
\[H(p)=-p\lg p-(1-p)\lg(1-p).\]
\(H(0)=H(1)=0\), while \(H(1/2)=1\).
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.
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).}\]
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.
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).\]
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)}.\]
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}.\]
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.
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.
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.
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.
Write \(m\) in binary: \(m=\sum_i a_i2^i\), with \(a_i\in\{0,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.
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.
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\).
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\).
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\).
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\}\).
\[\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.
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)\).
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)\).
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).}\]
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)\).
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.
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?
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\mapsto00,\quad b\mapsto010,\quad c\mapsto011,\quad d\mapsto1.\]
No leaf lies on the path to another leaf.
\[\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.
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.
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.
Start with one weighted leaf for each symbol.
Rare symbols tend to participate in more merges and acquire longer codewords.
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.
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.
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.
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.
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\).
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.
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 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.
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.
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\).
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.
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.
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)\).
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.
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.
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.
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.
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.
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).\]
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.
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.\]
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\).
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.
| 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.
\[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.
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.
CS 574 · Entropy · November 6, 2026