Notes 43–44 · 15-minute mathematical summary · November 6, 2026
CS 574 · University of Illinois, Urbana-Champaign
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).\]
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=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\mapsto00,\quad b\mapsto010,\quad c\mapsto011,\quad d\mapsto1.\]
Prefix-free: no codeword is a prefix of another. Codeword length equals leaf depth.
Start with one weighted leaf for each symbol.
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.
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.
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.
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.
| 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