15-minute mathematical summary · Lecture 23
CS 574 · University of Illinois, Urbana-Champaign · Fall 2026
The binary symmetric channel flips each bit independently with probability \(p\).
\[E:\{0,1\}^k\to\{0,1\}^n,\qquad D:\{0,1\}^n\to\{0,1\}^k,\qquad\text{rate}=k/n.\]
Fix \(0<p<1/2\). Write \(\Delta(x,r)\) for Hamming distance and
\[H(p)=-p\lg p-(1-p)\lg(1-p),\qquad C=1-H(p).\]
All logarithms \(\lg\) are base \(2\).
Fix \(\delta>0\) and \(0<\gamma<1\). For sufficiently large \(n\):
If \(k\leq n(C-\delta)\), some encoder and decoder have error at most \(\gamma\) for every message.
If \(k\geq n(C+\delta)\), every encoder and decoder have success probability less than \(\gamma\) for a uniform random message.
We prove achievability. The converse is stated without proof in the notes.
This proves existence; the unstructured codebook and exhaustive decoder are not computationally efficient.
For \(0<\varepsilon<1\), define
\[\mathcal R(x)=\{r:(1-\varepsilon)np\leq\Delta(x,r)\leq(1+\varepsilon)np\}.\]
Given \(r\), return index \(i\) if \(r\in\mathcal R(Y_i)\) for exactly one index.
Otherwise declare failure. A declared failure counts as an error.
Either the output misses the transmitted word’s ring, or it lies in that ring and a competing ring.
For fixed \(Y_i=x\), \(\Delta(x,R)\sim\operatorname{Binomial}(n,p)\).
\[\Pr[R\notin\mathcal R(x)] \leq a_n:=2e^{-\varepsilon^2pn/4}.\]
Choose \(n\) large enough that \(a_n\leq\gamma/8\).
The bound is uniform in \(x\) and independent of the other codewords.
Put \(q=(1+\varepsilon)p<1/2\). Binomial coefficients increase up to \(n/2\):
\[\begin{aligned} |\mathcal R(r)| &=\sum_{m=\lceil(1-\varepsilon)np\rceil}^{\lfloor(1+\varepsilon)np\rfloor}\binom nm\\ &\leq(n+1)\binom n{\lfloor nq\rfloor} \leq(n+1)2^{nH(q)}. \end{aligned}\]
The last inequality is the entropy counting bound from the preceding lecture.
Condition on \(Y_i=x\) and a received word \(r\in\mathcal R(x)\). Every \(Y_j\), \(j\ne i\), remains uniform and independent of this conditioning.
\[\Pr[r\in\mathcal R(Y_j)] =\Pr[Y_j\in\mathcal R(r)] =\frac{|\mathcal R(r)|}{2^n}.\]
\[\Pr[\text{ambiguity}\mid x,r] \leq2^{k+1}(n+1)2^{n(H(q)-1)}.\]
Symmetry of Hamming distance gives the first equality; a union bound gives the second display.
Since \(k\leq n(1-H(p)-\delta)\),
\[\Pr[\text{ambiguity}\mid x,r] \leq2(n+1)2^{n(H(q)-H(p)-\delta)}.\]
Choose \(\varepsilon\) by continuity so that \(q<1/2\) and \(H(q)-H(p)\leq\delta/2\).
Then ambiguity is at most \(b_n:=2(n+1)2^{-n\delta/2}\leq\gamma/8\) for large \(n\).
Choose \(p,\delta,\gamma\), then \(\varepsilon\), then \(n\).
Let \(S_i\) be the received words that uniquely decode to index \(i\).
\[w(x,r)=p^{\Delta(x,r)}(1-p)^{n-\Delta(x,r)},\qquad\sum_rw(x,r)=1.\]
\[W_i=\sum_rw(Y_i,r)\mathbf1_{\{r\notin S_i\}}.\]
\(W_i\) is the channel error of index \(i\) for a fixed codebook. It becomes a random variable when we sample the codebook.
Fix \(Y_i=x\) and average over the competing codewords:
\[\begin{aligned} \mathbb E[W_i\mid Y_i=x] &\leq\sum_{r\notin\mathcal R(x)}w(x,r) +\sum_{r\in\mathcal R(x)}w(x,r)b_n\\ &\leq a_n+b_n\leq\gamma/4. \end{aligned}\]
Hence \(\mathbb E[W_i]\leq\gamma/4\) for every index \(i\).
\[\mathbb E\!\left[\sum_{i=0}^{N-1}W_i\right] \leq\frac{N\gamma}{4}.\]
Therefore some fixed codebook satisfies \(\sum_iW_i\leq N\gamma/4\).
No independence among the \(W_i\) is needed.
Let \(B=\{i:W_i>\gamma\}\) for this fixed codebook.
\[\gamma|B|\leq\sum_iW_i\leq\frac{N\gamma}{4} \quad\Longrightarrow\quad |B|\leq N/4.\]
At least \(3N/4\) indices have error at most \(\gamma\).
Keep the best \(N/2=2^k\) indices.
Deleting competing codewords enlarges each retained success region.
Thus every retained codeword has error at most \(\gamma\) under the new decoder.
Assign the \(2^k\) messages bijectively to these words.
Duplicates cannot survive: two identical indexed words each have error \(1\) under the original unique-ring decoder, while \(\gamma<1\).
\[\boxed{k\leq n(1-H(p)-\delta) \quad\Longrightarrow\quad \max_m\Pr[D(R)\ne m\mid m]\leq\gamma}\]
for all sufficiently large block lengths.
Random coding controls expected error; expurgation protects every message.
The guarantee concerns independent random noise, not every pattern of \(np\) flips.
\[\underbrace{2^k}_{\text{messages}} \cdot\underbrace{2^{nH(p)}}_{\text{typical noise scale}} \quad\text{versus}\quad \underbrace{2^n}_{\text{outputs}}.\]
Disjoint decoding regions motivate the threshold \(k/n=1-H(p)\).
This picture explains the converse intuition; it does not prove the strong converse stated earlier.
Notes 45: Entropy III — Shannon’s Theorem.
Mitzenmacher and Upfal, Probability and Computing (2005), §§9.1–9.3, as cited in the notes.
Concentration + entropy counting + the probabilistic method + expurgation.
CS 574 · Lecture 23 · Entropy III