Notes 43–44 · Condensed lecture · 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)\).
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\).
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\).
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).}\]
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}.\]
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.
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\).
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.
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.
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 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.
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.
Start with one weighted leaf for each symbol.
Rare symbols tend to participate in more merges and acquire longer codewords.
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.
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.
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.
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.
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