Full search page →

IT 08 · Networks, Information Inequalities and Learning

Information TheoryAdvanced19 minUpdated Oct 4, 2026

Needs: IT 07 · Statistical Evidence, Maximum Entropy and Growth

Navigate: this page and this track: Navigate: this page and this track
Explore this chapter 1 interactive experiment

Compute information about a noisy XOR label from each independent bit and from their pair.

What you’ll learn

  • Describe rate regions for distributed sources and multiple-access channels.
  • Explain why broadcast, relay and general networks need different arguments.
  • Apply log-sum, Pinsker, entropy-power and conditional-information inequalities.
  • Distinguish representation information from information about a training sample.
  • Run a small distributed parity-code decoder with explicit finite errors.
  • Connect the book’s complete chapter map to current learning research without overstating limits.

The big picture

One sender and one receiver lead to a single capacity. Several sources or receivers lead to a region of compatible rates. Improving one rate may reduce another, and information can be useful jointly even when each component looks useless alone.

This final tutorial follows Cover and Thomas’s Chapter 15 on networks and Chapter 17 on inequalities [1]. Earlier chapters covered the other fifteen book chapters through the reading map in IT 01. We end with a finite synthetic experiment that connects source dependence, coding, decoding and task information.

The course uses the published second edition, supplemented by current surveys and a clearly labeled 2026 proposed chapter.

Distributed source coding: correlation can save rate

Two encoders can separately describe correlated observations while a joint decoder uses their relationship. The encoders need not each send every bit independently.

Let independent pairs (Xt,Yt)(X_t,Y_t) follow a fixed finite joint law. Encoder one observes only XnX^n, encoder two only YnY^n, and a common decoder reconstructs both blocks. The Slepian–Wolf asymptotically almost-lossless region is

RX≥H(X∣Y),RY≥H(Y∣X),RX+RY≥H(X,Y).R_X\geq H(X\mid Y),\qquad R_Y\geq H(Y\mid X),\qquad R_X+R_Y\geq H(X,Y).

Here RX,RYR_X,R_Y are bits per paired source sample sent by the separate encoders, and the entropies use the specified joint source. Boundary inequalities describe the closure; codes operate with suitable rate margins and vanishing block error [1].

The individual bounds assume the other source can help at decoding. The sum bound counts total joint uncertainty. Neither encoder is assumed to see the other’s current block; allowing that observation would define a different problem.

For fair XX and Y=X⊕EY=X\oplus E with independent Bernoulli noise probability ee, both marginal entropies are one and joint entropy is 1+h2(e)1+h_2(e). Separately ignoring dependence would require two bits per pair asymptotically; joint decoding can exploit the smaller joint uncertainty.

One corner sends YY at its full marginal rate and compresses XX toward H(X∣Y)H(X\mid Y). The decoder already has the reconstructed YY, which acts as side information. This corner motivates the parity-syndrome experiment below.

Random binning supplies an existence argument: assign source blocks to bins and use the other decoded source to find the likely matching block in the signaled bin. The bin index tells less than a full source index, while the correlation resolves ambiguity.

This result is not exact reconstruction of every possible finite pair. Rare or ambiguous blocks can fail. Truly lossless finite protocols require an additional escape or other treatment if every allowed realization must be recovered.

Why random bins produce three rate constraints

Each encoder randomly assigns every possible source block to a bin and sends its bin index. The decoder searches for a jointly typical pair in the two indicated bins. A competing pair can be wrong in three ways: only X is wrong, only Y is wrong, or both are wrong.

Competing pairTypical candidate count scaleCollision probability per candidate
Wrong X, correct Y2nH(X∣Y)2^{nH(X\mid Y)}2−nRX2^{-nR_X}
Correct X, wrong Y2nH(Y∣X)2^{nH(Y\mid X)}2−nRY2^{-nR_Y}
Both wrong2nH(X,Y)2^{nH(X,Y)}2−n(RX+RY)2^{-n(R_X+R_Y)}

Here nn is paired block length, RX,RYR_X,R_Y the sent bin-index rates, and the entropy exponents use the fixed joint source. These scales omit the small typicality tolerances and finite prefactors. Independent bin assignments give the collision factors, while joint typicality limits how many candidates need consideration.

Multiply each count by its collision probability and use a union bound. All three terms vanish with suitable margins exactly when the two individual rates exceed their conditional entropies and their sum exceeds joint entropy. The true pair fails typicality with a probability that also vanishes. Averaging over assignments then proves some fixed shared binning rule has small block error [1].

This proof explains both the correlation gain and its limit. Decoder side information reduces the number of candidate X blocks from the full source catalog to a conditional catalog. It does not eliminate the need to distinguish the remaining candidates. The sum constraint handles simultaneous ambiguity that neither individual bound can remove alone.

For fair bits with flip probability 0.1, conditional entropy is about 0.468996 and joint entropy 1.468996 bits per pair. The corner rates are approximately (0.468996,1)(0.468996,1) and (1,0.468996)(1,0.468996). A symmetric point has rate 0.734498 for each encoder; assigning 0.5 to each passes the individual bounds but fails the sum bound. These are limiting boundary values, so actual asymptotic constructions use margins rather than promising a short-block code at the boundary.

Multiple access: independent messages share one output

Two senders can both communicate through a common receiver. The receiver’s observation limits their combined information as well as each individual rate.

For a finite memoryless channel W(y∣x1,x2)W(y\mid x_1,x_2) with independent messages, the region for a fixed product input law includes

R1≤I(X1;Y∣X2),R2≤I(X2;Y∣X1),R1+R2≤I(X1,X2;Y).R_1\leq I(X_1;Y\mid X_2),\qquad R_2\leq I(X_2;Y\mid X_1),\qquad R_1+R_2\leq I(X_1,X_2;Y).

Here X1,X2X_1,X_2 are sender inputs, YY the shared output, and R1,R2R_1,R_2 bits per common channel use. Union over product input laws and time-sharing gives the ordinary two-user multiple-access capacity region [1].

Conditioning in an individual bound reflects the receiver being able to distinguish that user’s message when the other input is known. The sum bound addresses joint decoding. Maximizing each individual expression separately does not remove the shared sum constraint.

Time-sharing introduces a common predetermined variable TT and product inputs given TT. The corresponding bounds condition each expression on TT, and convexify operating points. The senders do not gain arbitrary message-dependent cooperation simply because they share a schedule.

For independent real Gaussian signals with powers P1,P2P_1,P_2 and additive noise variance NN,

R1≤12log⁡2(1+P1/N),R2≤12log⁡2(1+P2/N),R1+R2≤12log⁡2(1+(P1+P2)/N).\begin{aligned} R_1&\leq\tfrac12\log_2(1+P_1/N),\\ R_2&\leq\tfrac12\log_2(1+P_2/N),\\ R_1+R_2&\leq\tfrac12\log_2(1+(P_1+P_2)/N). \end{aligned}

Here one use contains both simultaneous real inputs; the signals have independent messages and the standard average-power constraints. The one-half factors retain the real-valued convention.

Pentagonal two-user real Gaussian multiple-access region under powers two and one and noise variance one.
Figure 1 — P₁=2, P₂=1 and N=1. Individual maxima cannot both be reached simultaneously because of the sum-rate constraint.

Successive decoding can achieve corner points by first decoding one message while treating the other as noise, then removing the decoded contribution. The order changes which user receives the more favorable conditional rate. Joint decoding and time-sharing describe the broader region.

Work through the two Gaussian decoding orders

For the figure’s powers P1=2P_1=2, P2=1P_2=1 and noise variance N=1N=1, user one’s individual bound is about 0.792481 bits per use, user two’s is 0.5, and the shared sum bound is one. The pair (0.75,0.4)(0.75,0.4) satisfies both individual bounds but violates the sum. The pair (0.6,0.35)(0.6,0.35) satisfies all three.

Decode user one first. Its decoder initially treats user two’s independent Gaussian signal as additional noise of variance one, so its rate is limited to 12log⁡2(1+2/(1+1))=0.5\tfrac12\log_2(1+2/(1+1))=0.5. After successful decoding and subtraction, user two sees only the original noise and reaches 0.5. This order gives corner (0.5,0.5)(0.5,0.5).

Decode user two first instead. Its initial rate is 12log⁡2(1+1/(1+2))≈0.207519\tfrac12\log_2(1+1/(1+2))\approx0.207519. After removing that signal, user one reaches 12log⁡2(1+2/1)≈0.792481\tfrac12\log_2(1+2/1)\approx0.792481. This gives corner (0.792481,0.207519)(0.792481,0.207519). Both corners have total rate one, but decoding order allocates that total differently.

The subtraction argument assumes the first message was decoded correctly. A wrong first decision can propagate to the second, so a finite receiver must measure joint message error as well as individual errors. The asymptotic corner calculation guides design without hiding that implementation issue.

Broadcast and relay channels change the information pattern

One sender with two receivers is not the reverse of two senders with one receiver. A relay that hears and retransmits creates another distinct pattern.

In a physically degraded broadcast channel, X→Y1→Y2X\to Y_1\to Y_2 makes receiver one stronger in the specified statistical sense. A superposition construction uses an auxiliary variable UU with U→X→Y1→Y2U\to X\to Y_1\to Y_2:

R2≤I(U;Y2),R1≤I(X;Y1∣U).R_2\leq I(U;Y_2),\qquad R_1\leq I(X;Y_1\mid U).

Here R2R_2 is the weaker receiver’s private-message rate, R1R_1 the stronger receiver’s private-message rate, and UU the layer both can resolve. Union over appropriate p(u,x)p(u,x) gives the degraded-channel capacity region [1].

The Markov order is an assumption about receiver observations, not simply a ranking by sample accuracy. A general broadcast channel need not be degraded and does not inherit this exact region.

For a memoryless relay, let source input be XsX_s, relay input XrX_r, relay observation YrY_r and destination observation YdY_d. A cut-set upper bound is

Crelay≤max⁡p(xs,xr)min⁡{I(Xs;Yr,Yd∣Xr),I(Xs,Xr;Yd)}.C_{\mathrm{relay}}\leq \max_{p(x_s,x_r)} \min\{I(X_s;Y_r,Y_d\mid X_r),I(X_s,X_r;Y_d)\}.

Here the first cut separates the source from relay plus destination; the second separates source plus relay from the destination. The input joint law in the upper bound permits statistical cooperation as an outer relaxation.

A cut-set bound is not automatically achievable. Relays may decode a message, describe an observation, or use other causal strategies, each with its own conditions. General network capacity remains unresolved in many settings.

The lesson is to draw the actual information pattern before applying a formula: independent messages, correlated sources, side observations, causal relays and receiver demands are different assumptions. A scalar point-to-point capacity cannot summarize all of them.

Joint usefulness can be invisible to marginal information

Two individually uninformative features can jointly determine a target. Ranking only one feature at a time may discard both.

Let X1,X2X_1,X_2 be independent fair bits and Y=X1⊕X2Y=X_1\oplus X_2. Then

I(X1;Y)=I(X2;Y)=0,I(X1,X2;Y)=1,I(X1;Y∣X2)=1.I(X_1;Y)=I(X_2;Y)=0,\qquad I(X_1,X_2;Y)=1,\qquad I(X_1;Y\mid X_2)=1.

Here YY is the binary exclusive-or target. Each marginal input leaves the target fair; knowing both gives an exact answer. Conditioning on the other input reveals the first one’s full relevance.

XOR example has zero mutual information with either individual input but one bit with the pair.
Figure 2 — Exact synthetic joint law. This illustrates joint usefulness without invoking a particular decomposition of redundancy and synergy.

The word synergy is useful informally for this joint-only information, but a general quantitative redundancy–synergy decomposition requires an additional definition. The three mutual-information values alone do not define a universal decomposition for arbitrary variables.

This matters for multimodal learning. A modality that seems weak by itself may be useful in context. Conversely, two strong marginal features may carry largely overlapping information. Analyze the actual joint law and receiver task rather than equating marginal relevance with unique contribution.

Computing a function is another distributed problem

Suppose separate encoders observe independent fair blocks X1nX_1^n and X2nX_2^n, and the decoder needs only their coordinatewise exclusive-or. The output has one bit of entropy per pair. It is tempting to conclude that one total bit per pair must suffice.

That conclusion ignores who sees the inputs. Give the decoder the second raw block as extra information. If it can recover the exclusive-or from the two transmitted indices, it can then recover the first block. The second encoder’s index supplies no additional first-block information because the inputs are independent.

Consequently the first encoder must convey approximately one bit per coordinate for vanishing error in this example. By symmetry, so must the second. The distributed sum requirement can therefore be two bits even though the desired function has entropy one.

If one central encoder observed both inputs, it could instead transmit the exclusive-or itself at one bit per pair. The target is unchanged, but the observation pattern differs. This is a concrete reason to keep the network diagram beside a task-oriented rate claim.

The example also separates two meanings of “joint information.” The receiver may need a joint computation, while the senders lack joint observation. A learned system cannot assume a centrally available feature merely because that feature would be sufficient after it had been computed.

Real applications can have correlated inputs, interaction, common randomness or additional side information, each changing the problem. Do not transfer the independent noninteractive example’s rate conclusion to those settings without deriving the corresponding constraints.

Stronger inequalities extend the toolkit

Information inequalities often compare what remains after merging outcomes, changing a distribution, or adding independent noise. Their units and assumptions decide what they imply.

For nonnegative numbers aia_i and positive bib_i, the log-sum inequality states

∑iailn⁡aibi≥Aln⁡AB,A=∑iai,B=∑ibi.\sum_i a_i\ln\frac{a_i}{b_i} \geq A\ln\frac AB, \qquad A=\sum_i a_i,\quad B=\sum_i b_i.

Here ii indexes entries, A,BA,B are their sums, and zero terms use the standard continuous convention. The all-zero AA case has both sides zero. This inequality underlies divergence convexity and aggregation forms of data processing [1].

Applying it inside each cell of a partition shows that merging outcomes cannot increase relative entropy. Fine measurements can distinguish distributions in ways a coarse summary no longer reveals.

For finite probability vectors p,qp,q, Pinsker’s inequality gives

TV⁡(p,q)=12∑i∣pi−qi∣≤12Dnats(p∥q).\operatorname{TV}(p,q)=\frac12\sum_i|p_i-q_i| \leq\sqrt{\frac12D_{\mathrm{nats}}(p\Vert q)}.

Here total variation bounds differences in event probabilities, and divergence uses natural logarithms. If divergence is reported in bits, multiply it by ln⁡2\ln2 inside the square root. A small divergence therefore controls event-probability differences, while large divergence can make the bound uninformative.

Discrete entropy is also submodular:

H(XA)+H(XB)≥H(XA∪B)+H(XA∩B).H(X_A)+H(X_B)\geq H(X_{A\cup B})+H(X_{A\cap B}).

Here A,BA,B are sets of variable indices, XAX_A is the corresponding collection, and the empty collection has entropy zero. The difference is a conditional mutual information between the nonoverlapping parts given the intersection, so it is nonnegative.

This is a relation among entropies of subsets, not a statement that every task-relevance function is submodular. The XOR target is a useful reminder that feature information can increase when another feature is supplied.

Entropy power and added Gaussian noise

Differential entropy can be converted into a variance-like quantity. Adding independent continuous signals cannot make their combined entropy power smaller than the sum.

For a dd-dimensional vector with finite natural-unit differential entropy, define entropy power

N(X)=12πeexp⁡(2hnats(X)d).\mathcal N(X)=\frac1{2\pi e}\exp\left(\frac{2h_{\mathrm{nats}}(X)}d\right).

Here dd is dimension and hnatsh_{\mathrm{nats}} uses natural logarithms. A scalar Gaussian has entropy power equal to its variance; an isotropic Gaussian vector has the common coordinate variance.

The entropy-power inequality for independent vectors of the same dimension states

N(X+Y)≥N(X)+N(Y).\mathcal N(X+Y)\geq\mathcal N(X)+\mathcal N(Y).

Here X,YX,Y must satisfy the relevant density and finiteness assumptions. Equality holds for independent Gaussian vectors with proportional covariance matrices in the standard nondegenerate setting [1].

The de Bruijn identity connects noise smoothing with Fisher information:

ddthnats(X+t G)=12Jloc(X+t G).\frac{d}{dt}h_{\mathrm{nats}}(X+\sqrt t\,G) =\frac12\mathcal J_{\mathrm{loc}}(X+\sqrt t\,G).

Here GG is an independent standard Gaussian vector, t>0t>0 is noise variance per coordinate, and Jloc(V)=E∥∇ln⁡fV(V)∥2\mathcal J_{\mathrm{loc}}(V)=\mathbb E\|\nabla\ln f_V(V)\|^2 is location Fisher information. Smoothness and integrability conditions are required.

This Fisher information is a density-gradient quantity related to location estimation, not an arbitrary parameter’s Fisher information from the previous chapter. Keeping that definition explicit avoids confusing two similarly named objects.

Adding noise can increase observation entropy while reducing information about the original. There is no contradiction: entropy power concerns output spread; data processing concerns retained relationships. Modern noisy representation models must distinguish those two claims.

Representation information and sample information

A feature can preserve a target while limiting raw input detail. A trained model can also reveal how much it depends on a particular training sample. These are different information questions.

An information-bottleneck objective for Y→X→ZY\to X\to Z is

min⁡p(z∣x)I(X;Z)−βI(Z;Y).\min_{p(z\mid x)}I(X;Z)-\beta I(Z;Y).

Here XX is the observation, YY the chosen relevance target, ZZ a possibly stochastic representation, and β≥0\beta\geq0 balances compression against target information. Goldfeld and Polyanskiy’s published tutorial [2] develops this theory and its learning connections.

The objective selects a task-relative statistical representation. It does not establish that every neural network spontaneously follows the same optimization, nor that one representation preserves every future target.

A bottleneck that removes nuisance without losing the label

A finite example makes the representation objective operational. Let label YY and nuisance bit NN be independent fair bits, and let observation X=(Y,N)X=(Y,N) contain both. Compare a full representation Z=XZ=X, a label-only representation Z=YZ=Y, and a constant representation.

RepresentationI(X;Z)I(X;Z)I(Z;Y)I(Z;Y)Objective I(X;Z)−βI(Z;Y)I(X;Z)-\beta I(Z;Y)
Both bits212−β2-\beta
Label only111−β1-\beta
Constant000

All information values are bits. The relevance weight β\beta is dimensionless. The label-only representation retains everything needed for this label and spends one less bit than the full representation. For β<1\beta<1, a constant wins; for β>1\beta>1, retaining the label wins among these choices. At β=1\beta=1, label-only and constant tie.

This conclusion is not limited to those three examples. The information chain rule gives

I(X;Z)−βI(Z;Y)=(1−β)I(Y;Z)+I(N;Z∣Y).I(X;Z)-\beta I(Z;Y) =(1-\beta)I(Y;Z)+I(N;Z\mid Y).

Here X=(Y,N)X=(Y,N), NN is the independent nuisance bit and ZZ any representation generated from XX. The conditional term is nonnegative. For β≤1\beta\leq1, zero is therefore a global lower bound, attained by a constant. For β>1\beta>1, using I(Y;Z)≤H(Y)=1I(Y;Z)\leq H(Y)=1 gives lower bound 1−β1-\beta, attained by Z=YZ=Y. The task-preserving optimum follows from the chain rule and an explicit source, rather than an informal claim that compression always improves learning.

Now change the future target to Y′=Y⊕NY'=Y\oplus N. The old label-only representation has zero information about this new fair target, while the full observation determines it. Irreversible task-specific compression limits future task transfer even when it is optimal for the original relevance criterion.

The notation also separates the two information questions in this section. These values concern one observation and its representation. The learning bound below instead concerns a model WW and the whole training sample SS. Reducing nuisance information in ZZ does not directly establish a smaller I(W;S)I(W;S) or a numerical generalization guarantee.

For learning, let S=(Z1,…,Zn)S=(Z_1,\ldots,Z_n) be an independent training sample and WW the learned model. Define population and empirical losses

L(W)=EZ∼P[ℓ(W,Z)],L^S(W)=1n∑i=1nℓ(W,Zi).L(W)=\mathbb E_{Z\sim P}[\ell(W,Z)], \qquad \widehat L_S(W)=\frac1n\sum_{i=1}^{n}\ell(W,Z_i).

Here PP is the population law, a fresh ZZ is independent of training, and ℓ\ell is the chosen loss. Now the relevant information term can be I(W;S)I(W;S), rather than feature information I(X;Z)I(X;Z).

If every fixed model’s loss is σ\sigma-sub-Gaussian under PP, a standard expectation bound has the form

∣E[L(W)−L^S(W)]∣≤2σ2Inats(W;S)n.\left|\mathbb E[L(W)-\widehat L_S(W)]\right| \leq\sqrt{\frac{2\sigma^2 I_{\mathrm{nats}}(W;S)}n}.

Here expectation averages the sample and any learner randomness, σ\sigma is the common concentration parameter, and information uses natural logarithms. Bounded loss in [0,1][0,1] permits σ=1/2\sigma=1/2 [3].

This is an expectation bound, not automatically a high-probability certificate for one trained network. A deterministic continuous learner can have infinite sample information, making it vacuous. Conditional-information frameworks and other refinements address different randomization and sampling conventions [3].

Code: an exact finite learning bound

This complete example learns only a constant binary classifier by majority label. Because its output is a deterministic bit, I(W;S)=H(W)I(W;S)=H(W); all expectations can be summed over binomial counts.

Code · Python · 18 lines
import numpy as np
from scipy.stats import binom

p = 0.65
for n in [5, 20, 100]:
    counts = np.arange(n+1)
    mass = binom.pmf(counts, n, p)
    prediction = counts >= n/2
    training_loss = np.where(prediction, (n-counts)/n, counts/n)
    population_loss = np.where(prediction, 1-p, p)
    gap = mass @ (population_loss-training_loss)
    probability_one = mass[prediction].sum()
    probabilities = np.array([probability_one, 1-probability_one])
    positive = probabilities > 0
    information_nats = -np.sum(probabilities[positive]*np.log(probabilities[positive]))
    bound = np.sqrt(information_nats/(2*n))
    assert abs(gap) <= bound + 1e-12
    print("Length / expected gap / information bound:", n, gap, bound)

The calculation includes the selection dependence between model and sample. Treating the chosen classifier as independent of its training labels would erase the very generalization gap being analyzed.

Capstone: side-information decoding with parity bins

The encoder sends a short parity label for its binary block. The decoder combines that label with a correlated block to select the most likely original.

For binary block x∈{0,1}nx\in\{0,1\}^n and public binary matrix HH with rr independent rows, transmit syndrome

s=Hx(mod2).s=Hx\pmod2.

Here HH has shape rr by nn, ss contains rr parity bits, and multiplication uses binary-field addition and multiplication. Each syndrome identifies a bin of candidate blocks.

The decoder has y=x⊕ey=x\oplus e, with independent flip probability below one half, and chooses a syndrome-compatible candidate minimizing Hamming distance to yy. For this specified law, that is maximum conditional likelihood.

The encoder never sees yy. The matrix and block length are shared; the decoder obtains yy as side information. The payload rate is r/nr/n, excluding any protocol for delivering or reconstructing that side information.

Thus the experiment corresponds to a source-coding corner, rather than compressing both observations for free. If the second block must also be transmitted, its description length belongs in the total rate. Shared side information is an assumption with a source, not an unexplained decoder advantage.

Code: exhaustive finite decoding and full-block error

The complete CPU example uses ten-bit blocks so exhaustive search is practical. It checks matrix rank over the binary field rather than using real-valued numerical rank.

Code · Python · 45 lines
import numpy as np

rng = np.random.default_rng(43)
n, trials, flip = 10, 3000, 0.1
patterns = ((np.arange(2**n)[:, None] >> np.arange(n)) & 1).astype(np.uint8)
source_indices = rng.integers(2**n, size=trials)
source = patterns[source_indices]
side = source ^ rng.binomial(1, flip, size=source.shape).astype(np.uint8)

def binary_rank(matrix):
    work = matrix.copy()
    rank = 0
    for column in range(work.shape[1]):
        pivots = np.flatnonzero(work[rank:, column])
        if len(pivots) == 0:
            continue
        pivot = rank + pivots[0]
        work[[rank, pivot]] = work[[pivot, rank]]
        for row in range(work.shape[0]):
            if row != rank and work[row, column]:
                work[row] ^= work[rank]
        rank += 1
        if rank == work.shape[0]:
            break
    return rank

for parity_bits in [4, 6, 8]:
    while True:
        H = rng.integers(2, size=(parity_bits, n), dtype=np.uint8)
        if binary_rank(H) == parity_bits:
            break
    weights = 2**np.arange(parity_bits)
    syndromes = ((patterns @ H.T) % 2) @ weights
    bins = [np.flatnonzero(syndromes == s) for s in range(2**parity_bits)]
    assert all(len(group) == 2**(n-parity_bits) for group in bins)
    decoded = np.empty(trials, dtype=int)
    for t, (index, observation) in enumerate(zip(source_indices, side)):
        candidates = bins[syndromes[index]]
        distances = np.count_nonzero(patterns[candidates] != observation, axis=1)
        decoded[t] = candidates[np.argmin(distances)]
    block_error = np.mean(decoded != source_indices)
    print("Parity bits / payload rate / full-block error:",
          parity_bits, parity_bits/n, block_error)
conditional_entropy = -flip*np.log2(flip)-(1-flip)*np.log2(1-flip)
print("Asymptotic side-information reference:", conditional_entropy)

This is a finite demonstration, not a capacity-achieving construction. Different random matrices produce different errors; increasing parity count need not improve every unrelated sampled matrix monotonically. The reference entropy is a long-block limit, not an exact ten-bit prediction.

Tie handling is deterministic through candidate order. Noise can move the side block closer to an incorrect syndrome-compatible source. A full round-trip assertion for every noisy trial would therefore be the wrong test: the protocol intentionally reports finite message errors.

For a truly lossless file protocol, provide an escape mechanism or interactive correction with explicit transmitted cost. Here the learning goal is to see how side information narrows bins and how finite ambiguity remains.

Modern view

The published 2025 monograph by Hellström and colleagues [3] maps information-theoretic and PAC-Bayesian generalization through expectation, probability and conditional-information formulations. That taxonomy helps distinguish a bound on average selection dependence from a guarantee for one deployed predictor.

Nguyen and colleagues’ 2025 semantic-communication survey [4] distinguishes receiver-intention modeling, generative decoding and learned joint coding. Its network perspective makes receiver knowledge and task goals central; those must be included in the mathematical information pattern.

El Gamal’s proposed 2026 chapter [5] extends the textbook conversation toward statistical learning. Its draft status remains explicit. Modern inference and generative models can use the same divergence machinery while posing additional computational and evaluation problems.

Open questions include general multiuser regions, short-block distributed codes, realistic dependence and channel shift, task criteria for rare content, and useful information bounds for high-dimensional learned systems. A new model architecture does not solve these questions merely by producing plausible samples.

Our course-level inference is to ask five questions before interpreting an information claim: which random variables are involved; who observes each one; what source and channel laws are assumed; which reconstruction or decision is required; and how rate, error and resource cost are measured.

An information audit can turn those questions into a compact experiment record:

ChoiceWhat to record
SourcePopulation, grouping and dependence assumptions
ObservationVariables available separately at each encoder and receiver
DescriptionAlphabet, actual bitstream, shared parameters and side streams
ChannelConditional law, memory, power and use convention
GoalExact message, lossy reconstruction or specified task
EvaluationFixed test set, error definition, rate and runtime

The record is useful even when no tight theorem is known. It prevents a number from silently changing meaning between training, mathematical analysis and deployment. It also makes negative results informative: a poor rate may come from a probability model, a reconstruction constraint or a finite decoder, rather than from the same underlying limitation.

A reading and project path after the course

Revisit the full book in three passes. First consolidate Chapters 1–5 and 7–10 with the entropy, coding, channel and distortion examples. Then connect Chapters 6 and 11–14 to prediction, evidence, maximum entropy, universal codes and description complexity. Finally study Chapters 15–17 with the network assumptions and inequalities kept beside every theorem.

For a small project, choose one explicit joint law or independently collected dataset and one receiver objective. Implement a baseline encoder–decoder, report actual rate and decision error, then change only one component at a time. A probability model, a quantizer and a channel code answer different experimental questions.

The autoregressive vision chapter connects sequential probability factorization with modern models. The representation chapter develops task features, and the language-model chapter connects conditional prediction with token sequences.

These connections are strongest when the information definitions stay concrete. A tokenization choice changes the alphabet and unit; a learned latent changes the observation; a generated reconstruction changes the distortion question. State those choices before comparing numerical information values.

Key takeaways

  • Networks produce compatible rate regions rather than one universal scalar rate.
  • Distributed decoding exploits correlation without granting encoders unobserved inputs.
  • Multiple-access individual rates remain subject to a shared sum constraint.
  • Broadcast and relay formulas depend on their specific information pattern.
  • Joint task information can be invisible to individual feature information.
  • Advanced inequalities require explicit units, supports and independence assumptions.
  • Representation information and sample-dependent generalization are distinct objects.
  • Finite decoding, actual rate and honest error reporting complete the theoretical picture.

Exercises

  1. For fair XX and Y=X⊕EY=X\oplus E with flip probability 0.2, calculate the Slepian–Wolf corner rates and joint entropy. Explain what each encoder observes.
Hint

Use h2(0.2)h_2(0.2) for conditional entropy.

  1. Compute the two Gaussian multiple-access corner points for the figure parameters. Verify the sum constraint and describe the successive-decoding order.
Hint

One individual rate reaches its maximum and the other fills the sum bound.

  1. Explain why an arbitrary broadcast channel cannot inherit the physically degraded region. Identify the missing conditional relation.
Hint

Check X→Y1→Y2X\to Y_1\to Y_2.

  1. Verify Pinsker’s bound for probability vectors (0.6,0.4)(0.6,0.4) and (0.5,0.5)(0.5,0.5), using both natural and base-two divergence consistently.
Hint

Convert bits to nats with ln⁡2\ln2.

  1. Change parity-code block length to 12 and compare at several parity counts. Keep exhaustive-search cost visible and report block errors rather than only bit errors.
Hint

The candidate table has 2n2^n rows.

  1. For the XOR target, compare keeping only X1X_1 with keeping the pair. Then explain why a deterministic continuous representation’s raw-input information can be infinite while its discrete task information stays bounded.
Hint

Separate target entropy from exact continuous relationships.

References

  1. T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006, Chapters 15 and 17. Publisher book and contents.
  2. Z. Goldfeld and Y. Polyanskiy, “The Information Bottleneck Problem and Its Applications in Machine Learning,” IEEE Journal on Selected Areas in Information Theory, 1(1), 2020, DOI: 10.1109/JSAIT.2020.2991561. Institutional final-manuscript record.
  3. F. Hellström, G. Durisi, B. Guedj and M. Raginsky, “Generalization Bounds: Perspectives from Information Theory and PAC-Bayes,” Foundations and Trends in Machine Learning, 18(1), 1–223, 2025. Publisher metadata, author version.
  4. L. X. Nguyen, A. D. Raha, P. S. Aung, D. Niyato, Z. Han and C. S. Hong, “A Contemporary Survey on Semantic Communications: Theory of Mind, Generative AI, and Deep Joint Source-Channel Coding,” IEEE Communications Surveys & Tutorials, 2025. Published-paper metadata and author version.
  5. A. El Gamal, “Information Theory and Statistical Learning,” proposed textbook chapter, arXiv preprint, 2026. Draft and publication status.

Check your understanding

This tutorial has 6 exercises. Can you solve them without opening the hints?

Go to the exercises ↑

This is the last tutorial in Information Theory. Back to the learning map →