The supplied sources were reviewed locally: Cover and Thomas, Elements of Information Theory, first edition (1991); Stanford EE376A notes supplied as a 75-page January 2016 PDF; Michèle Wigger's four Mn908/MICAS exercise sheets from September–October 2024. Chapter numbers below refer to the supplied first edition. Original PDFs are preserved under ignored legacy/originals; their hashes are in the manifest. This guide contains new explanations and implementation mappings, rather than redistributing course materials.
A theoretical exercise may be best answered by a proof plus a numerical example. A finite simulation illustrates a theorem; it does not replace its proof.
| Problem | Result and implementation |
|---|---|
| 1, joint PMF | foundations/joint_entropy: H(X)=1, H(X,Y)=1.5, H(X |
| 2, functions | Chain rule gives H(X,f(X))=H(X) and also H(f(X))+H(X |
| 3, parity | Exact enumeration for n=2,3,10. Pair MI is one bit for n=2 and zero for n>2. I(X1;X2 |
| 4, conditioning | If X=Y=Z is a fair bit, MI drops from one to zero after conditioning. If X and Y are independent fair bits and Z=X XOR Y, MI rises from zero to one. Conditioning is not monotone for mutual information. The n=3 parity case implements the second example. |
| 5.1, mixing | Averaging two masses is the midpoint of a PMF and its transposition. Entropy concavity and permutation invariance imply entropy cannot decrease. The configured uniform-mixture family illustrates repeated mass equalization. |
| 5.2, fixed masses | Let s=1-p1-pm. The maximum puts s/(m-2) on every remaining symbol; the minimum puts all s on one remaining symbol, with zeros elsewhere. Concavity proves the minimum occurs at a simplex vertex; Jensen proves the maximum. Both feasible extremizers are saved. |
| Problem | Result and implementation |
|---|---|
| 1, prefix codes | Owned Huffman, Shannon and exact exhaustive feasible-length oracle. The specified code has expected length 2.5 bits and is optimal. It is not a greedy Huffman tree for these weights: the smallest 1/24 leaf is paired with 1/12 instead of a remaining 1/16 leaf. Optimal codes need not be obtainable from the particular greedy merge rule. |
| 2, nearly one-bit redundancy | A two-symbol source (1-delta,delta) has optimal integer expected length one. Its entropy tends to zero as positive delta tends to zero, so redundancy approaches one bit. Do not use delta=0: a singleton framed alphabet may have an empty codeword. |
| 3, weighted costs | Put a_i=p_ic_i, A=sum a_i. The real-valued optimum is l_i=log2(A/a_i), cost AH(a/A). Huffman on weights a_i minimizes integer weighted cost. Rounding the relaxed lengths upward is feasible and gives cost strictly below the relaxed cost plus A for a nontrivial supported alphabet. The weighted and ordinary cases save weights, lengths, codewords and bounds. |
| 4, general stationary processes | All three transformed processes are stationary. Overlapping pairs Y have entropy rate H_X per pair; nonoverlapping pairs Z have rate 2H_X per pair. For V=X_(2i), H_X <= H_V <= 2H_X, per subsampled output. One inequality follows because the even sequence is a function of a 2n-block; the other follows by splitting the whole block into odd/even subsequences and using stationarity and subadditivity. Entropy rates of V are not automatically computable from a one-step transition matrix for a general process. |
| 5, Markov example | Stationary law (3/7,4/7), rate 0.9649839289 bits/output. Subsampling is Markov with P squared, rate 0.9846718866 bits/subsampled output. Adjacent swaps are not first-order Markov: the saved conditional-MI witness is positive. They preserve rate because block permutations are invertible and boundary effects vanish. Anchored sums are invertible via X_k=Z_k-X_(k-1), preserve rate, but have a positive non-Markov witness. See sources.transformation_examples. |
| 6, window LZ | lossless.py supplies an explicit bounded-window LZ77 encoder/decoder and real rate measurements. The sheets do not specify the class token/integer framing completely. The supplied encoded bitstring therefore has no defensible unique decoded answer here. Exact class-format reproduction requires those missing conventions; this limitation is stated, not filled with an invented result. The two input strings can be round-tripped under the documented owned format. |
| Problem | Result and implementation |
|---|---|
| 1.1, strong implies weak | On supported symbols, absolute surprisal deviation is bounded by (epsilon/alphabet_size)*sum_a abs(log2 Q(a)), so it tends to zero with epsilon. The sheet's global codomain [0,1] is too restrictive for arbitrary Q and all epsilon: for Q=(0.1,0.9), a sequence with frequencies (0.6,0.4) is strongly 1-typical under the sheet's convention, but its surprisal deviation is 0.5*log2(9)=1.58496 bits. The theorem is the local implication for sufficiently small epsilon; use the displayed linear bound with a nonnegative real codomain. Zero-mass symbols are excluded. |
| 1.2, reverse implication | A uniform source gives constant surprisal for every sequence. Even an all-identical-symbol sequence is weakly typical with tolerance zero and need not be strongly typical. Exact multinomial-count simulations compare both definitions. |
| 2, course channels | W1 rows (1,0,0), (1/2,1/2,0), (0,0,1); C=log2(9/4), maximizing input (1/3,2/9,4/9). W2 rows (1,0,0), (1/2,1/4,1/4), (0,1/2,1/2); C=1. Distinguishing input 0 from input 2 achieves one bit. W2=W1*T where T leaves output 0 unchanged and splits both other symbols uniformly between outputs 1/2. Data processing bounds C2 by C1; direct reduction to a binary observation establishes C2 exactly. Numerical solvers retain certified bounds. |
| 3, Z channel | For crossover 1/2, capacity log2(5/4), maximizing input (0.6,0.4). General crossover curves are also evaluated. |
| 4, symmetry | BSC is symmetric. The configured 2x4 weakly symmetric example has row permutations and equal column sums, but columns are not all permutations. Row entropies are equal, so H(Y |
| 5, strictness | The statements without 'strict' are valid: MI is concave in input PMF and convex in channel law, and capacity is convex in channel law as a supremum of convex functions. The blanket strict claims are false. Any input-independent channel has zero MI for all input PMFs. Two distinct input-independent channels and their mixture have zero MI and capacity, giving equality in convexity. The explicit counterexample is saved and tested. |
| Problem | Result and implementation |
|---|---|
| 1, jammer | Unknown state gives effective crossover q*epsilon+(1-q)/2 and capacity 1-Hb(effective crossover). Decoder-known state gives q*(1-Hb(epsilon)). With both sides informed, communicate only on free positions using a capacity-approaching BSC code; their asymptotic frequency q gives the same rate. The unknown/known discrete channels are evaluated numerically. |
| 2, symbol-error converse | Block error tending to zero implies average symbol error tends to zero, since each symbol error is contained in the block-error event. Chain rule, dropping conditioning, symbolwise Fano and concavity of Hb give H(U^K|Z^K)/K <= Hb(Pb)+Pb*log2(a-1). For IID source symbols and one channel use per source symbol, data processing and capacity imply H(V) <= C + Hb(Pb)+Pb*log2(a-1). Thus H(V)>C excludes Pb tending to zero. For stationary sources replace H(V) by entropy rate; unequal source/channel use ratios change the capacity term accordingly. Actual code comparisons show both BER and BLER. |
| 3, infinite distortion | Only errors 1→0 are permitted. If their joint mass is D, the allowed reconstruction kernel yields R(D)=Hb(1/2-D)-(1/2)*Hb(2D) for 0<=D<=1/2, and zero above 1/2. The certified solver uses exactly zero forbidden-transition probabilities and matches this analytic function. |
| 4, row offsets | For every reconstruction kernel, E[d']=E[d]-sum p_i*w_i, while MI is unchanged. The feasible sets are identical after shifting the constraint, hence R'(D)=R(D+E[w]). Choosing w_i as the row minimum sets each row's minimum to zero when it is finite. No simulated optimization is needed to prove this identity. |
| Source concept | Practical implementation |
|---|---|
| Cover–Thomas chapters 2–5 | Information algebra, IID AEP, stationary sources, prefix/arithmetic/LZ coding, real code and genomic corpora. |
| Chapters 8–10 | Certified finite-channel capacity; actual Hamming, convolutional, Polar and LDPC codes; BPSK information; Gaussian water filling and normal approximations with explicit limits. |
| Chapter 12 and Stanford types notes | Exact rare-event probabilities, tilted importance sampling, method-of-types bounds, randomized Neyman–Pearson tests and Stein convergence. |
| Chapter 13 and Stanford separation notes | Certified discrete rate–distortion, quantized Gaussian sources, real scalar streams, equal-use analog/digital comparison, traditional/learned image bitstreams. |
| Further statistical learning | KSG/Gaussian/histogram MI estimation; held-out MINE-style DV and InfoNCE; discrete information bottleneck with restart diagnostics. |
Gambling, Kolmogorov complexity and general multiuser network regions are not implemented as if a short simulation established their theorems. They are honest future extensions. The practical scope concentrates on reproducible compression, communication, estimation and optimization.