Mid-length lecture · Lecture 23
CS 574 · University of Illinois, Urbana-Champaign · Fall 2026
For input \(x=(x_1,\ldots,x_n)\), the output is
\[R=x\oplus Z,\qquad Z_j\sim\operatorname{Bernoulli}(p),\]
where the \(Z_j\) are independent and \(\oplus\) is bitwise XOR.
Thus \(\Pr[R_j\ne x_j]=p\), independently for every position.
We work with a fixed \(0<p<1/2\).
\[\{0,1\}^k\ \xrightarrow{\ E\ }\ \{0,1\}^n \ \xrightarrow{\ \text{channel}\ }\ \{0,1\}^n \ \xrightarrow{\ D\ }\ \{0,1\}^k.\]
The sender transmits \(E(m)\); the receiver computes \(D(R)\).
For message \(m\), an error is the event \(D(R)\ne m\).
Our decoder may declare failure; a declared failure counts as an error.
\[H(p)=-p\lg p-(1-p)\lg(1-p).\]
Here \(\lg\) means logarithm to base \(2\), and \(0\lg0=0\).
For \(0<p<1/2\), \(H(p)\) is continuous and increasing.
About \(2^{nH(p)}\) noise patterns matter on the exponential scale.
Fix \(0<p<1/2\), a rate gap \(\delta>0\), and an error target \(0<\gamma<1\).
For sufficiently large \(n\), if
\[k\leq n\bigl(1-H(p)-\delta\bigr),\]
there are encoding and decoding functions with
\[\Pr[D(R)\ne m\mid m\text{ sent}]\leq\gamma \qquad\text{for every }m.\]
Fix \(0<p<1/2\), \(\delta>0\), and \(0<\gamma<1\).
For sufficiently large \(n\), if
\[k\geq n\bigl(1-H(p)+\delta\bigr),\]
then every encoder and decoder satisfy
\[\Pr[D(R)=M]<\gamma, \qquad M\text{ uniform on }\{0,1\}^k.\]
We state this direction without proof, as in the notes.
Set \(N=2^{k+1}\), where \(k\leq n(1-H(p)-\delta)\).
Sample \(Y_0,\ldots,Y_{N-1}\) independently and uniformly from \(\{0,1\}^n\).
Analyze the ring decoder using all \(N\) codewords.
Eventually retain only \(2^k\) of them.
The randomness is used to prove that a good fixed codebook exists.
Choose a small constant \(0<\varepsilon<1\).
\[\mathcal R(x)=\{r\in\{0,1\}^n: (1-\varepsilon)np\leq\Delta(x,r)\leq(1+\varepsilon)np\}.\]
The ring consists of the plausible received words for \(x\).
Also require \((1+\varepsilon)p<1/2\).
The red curve marks distance \(np\); the ring has width \(2\varepsilon np\).
Given the received word \(r\), inspect every codeword.
If exactly one codeword \(Y_i\) satisfies \(r\in\mathcal R(Y_i)\), output its index.
If none or more than one qualify, declare failure.
Being too close to a codeword can also put \(r\) outside its ring.
Let \(S_i\) be the received words that decode uniquely to index \(i\).
\[W_i=\Pr[R\notin S_i\mid Y_i\text{ sent}] =\sum_r w(Y_i,r)\,\mathbf1_{\{r\notin S_i\}}.\]
For a fixed codebook, \(W_i\) is a number in \([0,1]\).
For a random codebook, \(W_i\) is a random variable.
Our goal is \(\mathbb E_{\mathcal C}[W_i]\leq\gamma/4\) for every index \(i\).
The two-sided Chernoff bound gives, for \(0<\varepsilon<1\),
\[\Pr[R\notin\mathcal R(x)] \leq 2\exp\!\left(-\frac{\varepsilon^2pn}{4}\right).\]
For fixed \(p,\varepsilon>0\), this decays exponentially with \(n\).
Write the bound as \(a_n\) and take \(n\) large enough that \(a_n\leq\gamma/8\).
Combining the layer count and the entropy bound,
\[|\mathcal R(r)| \leq(n+1)\binom n{\lfloor nq\rfloor} \leq(n+1)2^{nH(q)},\]
where \(q=(1+\varepsilon)p<1/2\).
The polynomial factor \(n+1\) will be dominated by an exponential rate gap.
Condition on \(Y_i=x\) and \(R=r\) when index \(i\) is sent.
Each other codeword \(Y_j\) is still uniform on \(\{0,1\}^n\).
The other codewords are independent of \(Y_i\) and its channel noise.
This leaves a simple counting problem for every competitor.
\[\Pr[Y_j\in\mathcal R(r)] =\frac{|\mathcal R(r)|}{2^n}.\]
All strings are equally likely as a sampled codeword.
The number of strings in a Hamming ring is independent of its center.
For fixed \(x\) and \(r\in\mathcal R(x)\), let \(b_{i,r}\) be the conditional ambiguity probability.
\[\begin{aligned} b_{i,r} &\leq\sum_{j\ne i}\Pr[Y_j\in\mathcal R(r)]\\ &\leq2^{k+1}(n+1)2^{n(H(q)-1)}. \end{aligned}\]
No independence between the ambiguity events is needed for this union bound.
Since \(k\leq n(1-H(p)-\delta)\),
\[\begin{aligned} b_{i,r} &\leq2^{k+1}(n+1)2^{n(H(q)-1)}\\ &\leq2(n+1)2^{n(H(q)-H(p)-\delta)}. \end{aligned}\]
We want the exponent to be a negative constant times \(n\).
By continuity of \(H\), choose \(\varepsilon>0\) small enough that
\[q=(1+\varepsilon)p<\frac12, \qquad H(q)-H(p)\leq\frac\delta2.\]
Also keep \(\varepsilon<1\). Then
\[H(q)-H(p)-\delta\leq-\frac\delta2.\]
\[b_{i,r}\leq b_n:=2(n+1)2^{-n\delta/2}.\]
For fixed \(\delta>0\), \(b_n\to0\).
Increase \(n\) until \(b_n\leq\gamma/8\).
This bound holds for every \(i\), every \(x\), and every \(r\in\mathcal R(x)\).
For \(Y_i=x\), the inside-ring contribution is
\[g(x)=\sum_{r\in\mathcal R(x)} w(x,r)\Pr_{\mathcal C\setminus Y_i}[r\notin S_i\mid Y_i=x].\]
Each term keeps its weight \(w(x,r)\).
These weights turn a sum over received strings into a probability.
Apply the pointwise collision bound to every summand:
\[\begin{aligned} g(x) &\leq\sum_{r\in\mathcal R(x)}w(x,r)\frac\gamma8\\ &\leq\frac\gamma8, \end{aligned}\]
because \(\sum_{r\in\mathcal R(x)}w(x,r)\leq1\).
Let \(f(x)=\sum_{r\notin\mathcal R(x)}w(x,r)\leq a_n\leq\gamma/8\).
\[\begin{aligned} \mathbb E_{\mathcal C}[W_i\mid Y_i=x] &=f(x)+g(x)\\ &\leq\frac\gamma8+\frac\gamma8 =\frac\gamma4. \end{aligned}\]
The estimate holds for every transmitted word \(x\).
Average over the uniform choice of \(Y_i\):
\[\mathbb E_{\mathcal C}[W_i] =\mathbb E_{Y_i}\!\left[ \mathbb E_{\mathcal C}[W_i\mid Y_i]\right] \leq\frac\gamma4.\]
Every index has small expected error over random codebooks.
We still need one fixed codebook protecting every retained index.
Linearity gives \(\mathbb E[\overline W]\leq\gamma/4\) for \(\overline W=N^{-1}\sum_iW_i\).
Some sampled codebook satisfies
\[\overline W\leq\frac\gamma4, \qquad\text{so}\qquad \sum_{i=0}^{N-1}W_i\leq\frac{N\gamma}{4}.\]
Otherwise every codebook would have average error greater than its expectation bound.
From now on, the codebook is fixed.
Let \(B=\{i:W_i>\gamma\}\).
\[\gamma|B|\leq\sum_{i\in B}W_i \leq\sum_{i=0}^{N-1}W_i \leq\frac{N\gamma}{4}.\]
Thus \(|B|\leq N/4\); at least \(3N/4\) indices have \(W_i\leq\gamma\).
We need only \(N/2=2^k\) good indices.
Retain the \(2^k\) indices with the smallest \(W_i\).
Call their codewords \(X_0,\ldots,X_{2^k-1}\).
Every retained index had error at most \(\gamma\) in the larger codebook.
Discarding codewords with large error is called expurgation.
The new decoder searches only \(X_0,\ldots,X_{2^k-1}\).
For each retained index,
\[S_i^{\mathrm{old}}\subseteq S_i^{\mathrm{new}}, \qquad W_i^{\mathrm{new}}\leq W_i^{\mathrm{old}}\leq\gamma.\]
Removing competitors can turn ambiguous outputs into uniquely decodable outputs.
Suppose two sampled indices had the same word: \(Y_i=Y_j\).
Their rings coincide, so neither index ever decodes uniquely.
Thus \(W_i=W_j=1\) in the original codebook.
Since \(\gamma<1\), no such index belongs to the selected good half.
For \(k\leq n(1-H(p)-\delta)\) and sufficiently large \(n\),
\[\boxed{\max_m\Pr[D(R)\ne m\mid m\text{ sent}]\leq\gamma.}\]
Random coding controls average error.
Expurgation makes the guarantee hold for every message.
Before choosing the final block length,
\[\mathbb E_{\mathcal C}[W_i] \leq\underbrace{2e^{-\varepsilon^2pn/4}}_{\text{atypical noise}} +\underbrace{2(n+1)2^{-n\delta/2}}_{\text{ambiguity}}.\]
A smaller rate gap leaves less room for noise fluctuations.
A longer block makes both sources of error small.
\[\underbrace{2^k}_{\text{messages}} \cdot\underbrace{2^{nH(p)}}_{\text{typical noise scale}} \quad\text{versus}\quad \underbrace{2^n}_{\text{possible received words}}.\]
The threshold on the exponential scale is \(k/n=1-H(p)\).
The proof makes this intuition precise using a slightly wider ring and a fixed rate gap.
Each message needs a decoding region carrying substantial channel probability.
Different messages have disjoint decoding regions inside a space of \(2^n\) received words.
Typical noise spreads probability over roughly \(2^{nH(p)}\) possible outputs per message.
This motivates the threshold \(1-H(p)\); it is packing intuition, not a proof of the strong converse.
Concentration: the received word lies in a typical ring.
Entropy counting: a random competing codeword rarely explains it.
Expurgation: average reliability yields reliability for every retained message.
Together they achieve every fixed rate below \(1-H(p)\).
Notes 45: Entropy III — Shannon’s Theorem.
The notes follow Michael Mitzenmacher and Eli Upfal, Probability and Computing (2005), §§9.1–9.3.
Prerequisites: entropy, binomial coefficient estimates, Chernoff bounds, and the probabilistic method.
CS 574 · Lecture 23 · Entropy III