Information Theory for ML6 / 16

Module 6. Source coding: from entropy to real bits

Choose your answers and select “Check”. Numbers accept a decimal point, comma, or simple fraction. Answers and drafts are saved in this browser and shared between RU/EN.

Checked: 0 / 29 · Correct: 0

Question 6.1.1

6.1. Engineering setup: the probabilistic model and the entropy coder

Under ideal coding of data from $P$ using model $Q$ , how is $D_{\mathrm{KL},2}(P\|Q)$ interpreted?

One correct optionAAs the maximum codeword lengthBAs the expected extra length caused by model mismatch, in bits per symbolCAs the alphabet sizeDAs the rounding overhead of integer codeword lengths

A) As the maximum codeword length

B) As the expected extra length caused by model mismatch, in bits per symbol

C) As the alphabet size

D) As the rounding overhead of integer codeword lengths

Answer and explanation

Correct answer: B. Cross-entropy decomposes as H₂(P) + D_KL,2(P‖Q), so the KL term is exactly the mismatch surcharge. Integer rounding is a separate cost that appears on top of it.

Question 6.2.1

6.2. Prefix codes and the Kraft–McMillan inequality

Which property defines a prefix code?

One correct optionAAll codewords have the same lengthBEvery symbol uses at most two bitsCCodeword lengths increase with symbol probabilityDNo codeword is the beginning of another codeword

A) All codewords have the same length

B) Every symbol uses at most two bits

C) Codeword lengths increase with symbol probability

D) No codeword is the beginning of another codeword

Answer and explanation

Correct answer: D. This is what permits left-to-right decoding without separators. Equal lengths give a prefix code but are far from necessary, and lengths should decrease with probability, not increase.

Question 6.2.2

6.2. Prefix codes and the Kraft–McMillan inequality

Which lengths can be the lengths of a binary prefix code?

One correct optionAAny positive integer lengthsBOnly lengths whose sum equals oneCOnly lengths satisfying

\sum_i2^{-\ell_i}=1

DExactly the positive integer lengths satisfying

\sum_i2^{-\ell_i}\le1

A) Any positive integer lengths

B) Only lengths whose sum equals one

C) Only lengths satisfying $\sum_i2^{-\ell_i}=1$

D) Exactly the positive integer lengths satisfying $\sum_i2^{-\ell_i}\le1$

Answer and explanation

Correct answer: D. This is Kraft's criterion. Requiring equality, as in option C, would exclude codes that leave part of the tree unused, and such codes exist and are perfectly valid.

Question 6.3.1

6.3. The one-symbol source coding theorem

What does the lower bound $L\ge H_2(P)$ state for lossless coding?

One correct optionAExpected code length for a specified source cannot be smaller than its entropyBEvery individual file must have length at least

nH(P)

CNo particular string can be compressed below the source averageDNo code can compress any string at all below its raw length

A) Expected code length for a specified source cannot be smaller than its entropy

B) Every individual file must have length at least $nH(P)$

C) No particular string can be compressed below the source average

D) No code can compress any string at all below its raw length

Answer and explanation

Correct answer: A. The bound is about an expectation under a specified source. Individual sequences can and do come out shorter than the average, which is what options B, C and D deny.

Question 6.3.2

6.3. The one-symbol source coding theorem

When can a one-symbol prefix code attain $L=H_2(P)$ exactly?

One correct optionAFor every distribution after reordering the symbolsBOnly for a uniform distributionCWhen

p_i=2^{-\ell_i}

for integer lengths, so the Kraft budget is fully usedDWhenever the alphabet size is a power of two

A) For every distribution after reordering the symbols

B) Only for a uniform distribution

C) When $\sum_i2^{-\ell_i}=1$ for integer lengths, so the Kraft budget is fully used

D) Whenever the alphabet size is a power of two

Answer and explanation

Correct answer: C. Such a distribution is dyadic. A uniform distribution qualifies only when its size is a power of two, so options B and D each capture one special case rather than the condition.

Question 6.4.1

6.4. Huffman coding, arithmetic coding, and range coding

What does Huffman's algorithm optimize?

One correct optionAThe maximum codeword lengthBExpected length among binary prefix codes for a known finite distributionCThe parameter size of a language modelDExpected length among all uniquely decodable codes, including block codes

A) The maximum codeword length

B) Expected length among binary prefix codes for a known finite distribution

C) The parameter size of a language model

D) Expected length among all uniquely decodable codes, including block codes

Answer and explanation

Correct answer: B. Its optimality is within one class: binary prefix codes with one codeword per symbol. Coding blocks of symbols can do better, which is why option D claims too much.

Question 6.4.2

6.4. Huffman coding, arithmetic coding, and range coding

For the binary source $P=(0.99,0.01)$ , a one-symbol binary prefix code has $L=1$ although $H_2(P)\approx0.0808$ . Which conclusion is correct?

One correct optionAShannon's theorem is violatedBEntropy must be at least one bitCHuffman's algorithm failed to find the optimum hereDInteger one-symbol lengths can cost almost one extra bit per symbol

A) Shannon's theorem is violated

B) Entropy must be at least one bit

C) Huffman's algorithm failed to find the optimum here

D) Integer one-symbol lengths can cost almost one extra bit per symbol

Answer and explanation

Correct answer: D. The bound H ≤ L < H + 1 permits exactly this. Huffman is optimal in its class; the class of one-symbol integer lengths is simply too coarse for a highly skewed source.

Question 6.4.3

6.4. Huffman coding, arithmetic coding, and range coding

What is the width of the final ideal arithmetic-coding interval for $x_{1:n}$ ?

One correct optionA

q(x_{1:n})=\prod_tq(x_t\mid x_{<t})

BThe mean token probabilityC

1/n

2^{-n}

A) $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$

B) The mean token probability

C) $1/n$

D) $2^{-n}$

Answer and explanation

Correct answer: A. The interval is narrowed multiplicatively at every step, so its width is the sequence probability and the ideal length is −log₂ q(x_(1:n)).

Question 6.4.5

6.4. Huffman coding, arithmetic coding, and range coding

Which statement about a practical range coder or ANS is most accurate?

One correct optionAIt emits exactly

-\log_2q(x)

bits without qualificationBIt does not use model probabilitiesCFinite precision, metadata, and boundary rules can add a small redundancyDIt requires the probability model to be static

A) It emits exactly $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$ bits without qualification

B) It does not use model probabilities

C) Finite precision, metadata, and boundary rules can add a small redundancy

D) It requires the probability model to be static

Answer and explanation

Correct answer: C. The ideal information length remains the reference, but an implementation has its own protocol and overhead. Adaptive models are the normal case, not an exception.

Question 6.5.1

6.5. Long sequences: block coding, AEP, and entropy rate

What follows from encoding i.i.d. blocks of length $n$ as supersymbols?

One correct optionA

L_n/n=0

for every sourceB

H(X)\le L_n/n<H(X)+1/n

CDecoding must have a nonzero error probabilityD

H(X)\le L_n/n<H(X)+1

A) $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$ for every source

B) $H(X)\le L_n/n<H(X)+1/n$

C) Decoding must have a nonzero error probability

D) $H(X)\le L_n/n<H(X)+1$

Answer and explanation

Correct answer: B. One unit of rounding is spread over n symbols. Option D is the one-symbol bound, which is exactly what block coding improves on.

Question 6.5.2

6.5. Long sequences: block coding, AEP, and entropy rate

What does the AEP state for an i.i.d. source?

One correct optionAAll sequences have equal probabilityBEvery sequence of length

n

has probability close to

2^{-nH}

CSingle-symbol entropy tends to zeroD

-n^{-1}\log_2p(X^n)

concentrates near

H_2(X)

A) All sequences have equal probability

B) Every sequence of length $nH(P)$ has probability close to $2^{-nH}$

C) Single-symbol entropy tends to zero

D) $-n^{-1}\log_2p(X^n)$ concentrates near $H_2(X)$

Answer and explanation

Correct answer: D. Typical sequences are approximately equiprobable, and they carry almost all the probability mass. Option B drops the word "typical" and thereby makes a false claim about all sequences.

Question 6.5.3

6.5. Long sequences: block coding, AEP, and entropy rate

How does a typical-set code usually differ from a zero-error variable-length code?

One correct optionAIt can be fixed-rate and allow an error probability that tends to zeroBIt must be longer than the uncompressed messageCIt applies only to one symbolDIt achieves a rate strictly below the entropy rate

A) It can be fixed-rate and allow an error probability that tends to zero

B) It must be longer than the uncompressed message

C) It applies only to one symbol

D) It achieves a rate strictly below the entropy rate

Answer and explanation

Correct answer: A. Atypical sequences are either errors or need a separate escape mechanism. No code beats the entropy rate asymptotically, which rules out option D.

Question 6.5.4

6.5. Long sequences: block coding, AEP, and entropy rate

Which quantity determines the asymptotic coding cost of a stationary dependent source?

One correct optionAOnly

H(X_1)

BThe maximum token lengthCThe entropy rate

h=\lim_nH(X_{1:n})/n

DThe average of

H(X_i)

over positions

A) Only $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$

B) The maximum token length

C) The entropy rate $h=\lim_nH(X_{1:n})/n$

D) The average of $H(X_i)$ over positions

Answer and explanation

Correct answer: C. Dependencies can lower the cost far below the marginal entropy, and both options A and D ignore them by treating positions separately.

Question 6.6.1

6.6. Language-model metrics: PPL, BPC, and BPB

Why can token perplexity usually not be compared directly across tokenizers?

One correct optionAPerplexity is defined only for ASCII charactersBEvery tokenizer gives the same PPLCA larger vocabulary always lowers perplexityDMean NLL is normalized by different units: tokens of different size and composition

A) Perplexity is defined only for ASCII characters

B) Every tokenizer gives the same PPL

C) A larger vocabulary always lowers perplexity

D) Mean NLL is normalized by different units: tokens of different size and composition

Answer and explanation

Correct answer: D. Even at a fixed probability for the text, a different grouping gives a different per-unit average. The direction of the change is not fixed either, so option C is not a rescue.

Question 6.6.2

6.6. Language-model metrics: PPL, BPC, and BPB

Which statement about BPC and BPB is correct?

One correct optionAThey provide a common denominator but do not guarantee invariance to tokenizer and model changesBThey always equal eightCThey are independent of preprocessingDThey make results comparable across corpora

A) They provide a common denominator but do not guarantee invariance to tokenizer and model changes

B) They always equal eight

C) They are independent of preprocessing

D) They make results comparable across corpora

Answer and explanation

Correct answer: A. Fixing the unit removes one source of incomparability and leaves the rest: data, normalization, model, context policy. That is also why option D overstates the case.

Question 6.6.3

6.6. Language-model metrics: PPL, BPC, and BPB

If a fixed text probability is merely regrouped from single tokens into pairs, without changing $q(x)$ , what happens?

One correct optionAThe total number of bits doublesBBPB becomes zeroCThe total number of bits stays fixed, while perplexity per pair is the square of the token perplexityDBoth the total bits and the perplexity stay the same

A) The total number of bits doubles

B) BPB becomes zero

C) The total number of bits stays fixed, while perplexity per pair is the square of the token perplexity

D) Both the total bits and the perplexity stay the same

Answer and explanation

Correct answer: C. The message probability has not changed, so the code length cannot change. What changes is the unit the average is taken over, which is precisely the point of options C and D differing.

Question 6.7.1

6.7. A language model as part of a compressor

Which limitation matters for the raw compression ratios reported for Chinchilla 70B by Delétang et al.?

One correct optionAReconstruction was lossyBOnly a one-bit vocabulary was usedCThe evaluation used a single languageDThe cost of the model parameters was excluded from the raw ratio

A) Reconstruction was lossy

B) Only a one-bit vocabulary was used

C) The evaluation used a single language

D) The cost of the model parameters was excluded from the raw ratio

Answer and explanation

Correct answer: D. A self-contained archive must also carry the weights, which changes the picture radically for a gigabyte of data. The result is still a valid statement about predictive log loss.

Question 6.8.1

6.8. Model size, scaling laws, and total description length

What cannot be inferred solely from a smooth scaling-law decrease in test cross-entropy?

One correct optionAThat the larger model had lower loss in the measured rangeBThat the fitted asymptote equals the true entropy rate and the KL gap tends to zeroCThat loss can be measured in nats or bitsDThat the trend held across the scales that were actually tested

A) That the larger model had lower loss in the measured range

B) That the fitted asymptote equals the true entropy rate and the KL gap tends to zero

C) That loss can be measured in nats or bits

D) That the trend held across the scales that were actually tested

Answer and explanation

Correct answer: B. Extrapolating a fit to an asymptote and calling it the source entropy requires assumptions about the source, the model family, optimization, and context. The other three are just restatements of what was measured.

Question 6.8.2

6.8. Model size, scaling laws, and total description length

Which length corresponds to a self-contained two-part compressor?

One correct optionAOnly

L(x\mid\theta)

BOnly the parameter countC

L(\theta)+L(x\mid\theta)

, plus the necessary metadataD

L(\theta)

alone, since the data follow from the model

A) Only $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$

B) Only the parameter count

C) $L(\theta)+L(x\mid\theta)$ , plus the necessary metadata

D) $L(\theta)$ alone, since the data follow from the model

Answer and explanation

Correct answer: C. Both parts must be transmitted, along with the protocol needed to decode them. Validation NLL usually measures only the second part, because the model is already known to both sides.

Question 6.10.1

6.10. Compression quality and model capabilities

Which final statement about compression and intelligence is most defensible?

One correct optionAThe better compressor must be better at every form of intelligenceBCompression quality is exactly linked to predictive log loss and may proxy some capabilities, but is not a universal definition of intelligenceCPrediction and compression have no mathematical relationshipDThe link holds only for text and breaks down for other modalities

A) The better compressor must be better at every form of intelligence

B) Compression quality is exactly linked to predictive log loss and may proxy some capabilities, but is not a universal definition of intelligence

C) Prediction and compression have no mathematical relationship

D) The link holds only for text and breaks down for other modalities

Answer and explanation

Correct answer: B. The prediction-compression link is an exact construction. Moving from there to a general notion of intelligence is a much stronger empirical and philosophical claim, and the construction itself is not restricted to text.

Question 6.4.4

6.4. Huffman coding, arithmetic coding, and range coding

Why is the five-bit prefix 01111 not a valid termination for $[0.45,0.48)$ ?

One correct optionAThe number

15/32

lies outside the intervalBArithmetic codes must have an even lengthCThe dyadic interval

[15/32,16/32)

is not fully contained in the target intervalDFive bits are fewer than the ideal length of about 5.06 bits

A) The number $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$ lies outside the interval

B) Arithmetic codes must have an even length

C) The dyadic interval $[15/32,16/32)$ is not fully contained in the target interval

D) Five bits are fewer than the ideal length of about 5.06 bits

Answer and explanation

Correct answer: C. The whole interval of binary continuations has to fit, not just one point. The value 15/32 is in fact inside the target interval, which is exactly why option A is tempting and wrong.

Question 6.5.5

6.5. Long sequences: block coding, AEP, and entropy rate

How should the Shannon–McMillan–Breiman theorem be read?

One correct optionAFor a stationary ergodic source, the normalized information density converges to the entropy rate under standard conditionsBEvery text has a universal entropy of one bit per characterCEvery neural network reaches the Shannon limitDIt holds for any stationary source, ergodic or not

A) For a stationary ergodic source, the normalized information density converges to the entropy rate under standard conditions

B) Every text has a universal entropy of one bit per character

C) Every neural network reaches the Shannon limit

D) It holds for any stationary source, ergodic or not

Answer and explanation

Correct answer: A. The theorem is about a specified stochastic source, not about an undefined object called "language". Ergodicity is part of the hypothesis and cannot be dropped.

Question 6.9.1

6.9. Mathematical deepening: universal coding, online log-loss, and ICL

For a Bayesian mixture $Q=\sum_jw_jP_j$ , what is the regret relative to model $P_j$ on a particular sequence?

One correct optionAAt most

\log_2(1/w_j)

bitsBExactly

n

bitsCAlways infiniteDAt most

\log_2(1/w_j)

bits per symbol

A) At most $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$ bits

B) Exactly $n$ bits

C) Always infinite

D) At most $\log_2(1/w_j)$ bits per symbol

Answer and explanation

Correct answer: A. It follows immediately from Q(x) ≥ w_j P_j(x). The bound is for the whole sequence, so per symbol it vanishes as the sequence grows, which is the point option D misses.

Question 6.9.2

6.9. Mathematical deepening: universal coding, online log-loss, and ICL

What is the careful connection between universal prediction and in-context learning?

One correct optionAEvery LLM is a proven optimal Bayesian predictor for every promptBContext can adapt predictions without weight updates, but theorems require explicit structural assumptionsCICL is unrelated to probabilistic predictionDICL is exactly Bayesian mixture prediction over a known model class

A) Every LLM is a proven optimal Bayesian predictor for every prompt

B) Context can adapt predictions without weight updates, but theorems require explicit structural assumptions

C) ICL is unrelated to probabilistic prediction

D) ICL is exactly Bayesian mixture prediction over a known model class

Answer and explanation

Correct answer: B. Specific theoretical models supply useful mechanisms rather than a universal guarantee about real systems. Option D states as fact what those models assume.

Question 6.11.1

6.11. A practical protocol for evaluating an LLM as a compressor

Why must a sliding-window causal-LM evaluator count targets after the label shift?

One correct optionAThe model compares logits[:, :-1] with labels[:, 1:], so a naive suffix length can cause an off-by-one errorBLogits do not contain probabilitiesCTo reduce perplexity artificiallyDBecause the first token of every window is unpredictable

A) The model compares logits[:, :-1] with labels[:, 1:], so a naive suffix length can cause an off-by-one error

B) Logits do not contain probabilities

C) To reduce perplexity artificially

D) Because the first token of every window is unpredictable

Answer and explanation

Correct answer: A. A correct protocol verifies that every original token enters the loss exactly once. The first token of a window is indeed not scored, but that is a consequence of the shift rather than the reason to count carefully.

Question 6.C.1

Computational block

For $P=(0.40,0.20,0.15,0.15,0.10)$ an optimal Huffman code has lengths $(1,3,3,3,3)$ . Compute the expected code length in bits per symbol. (tolerance 0.005)

AnswerAbsolute tolerance: ±0.005

Answer and explanation

Numeric answer: 2.2 (tolerance 0.005). The expected length is 0.40 · 1 + 0.60 · 3 = 2.20 bits, while the entropy is 2.146 bits. The gap of about 0.054 bits is the price of integer lengths, comfortably inside the guarantee H ≤ L < H + 1.

Question 6.C.2

Computational block

Data come from $P=(0.5,0.25,0.25)$ but ideal fractional code lengths are built from the model $Q=(0.25,0.25,0.5)$ . Compute the expected length in bits per symbol. (tolerance 0.002)

AnswerAbsolute tolerance: ±0.002

Answer and explanation

Numeric answer: 1.75 (tolerance 0.002). The expected length is the cross-entropy H₂(P,Q) = 1.75 bits, and the entropy of P is 1.5 bits. The difference of 0.25 bits is D_KL(P‖Q), the mismatch surcharge, before any rounding is considered.

Question 6.C.3

Computational block

With $p(A)=0.5$ , $p(B)=0.3$ and $p(C)=0.2$ , compute the ideal arithmetic-code length of the string ACB in bits. (tolerance 0.005)

AnswerAbsolute tolerance: ±0.005

Answer and explanation

Numeric answer: 5.059 (tolerance 0.005). The final interval has width 0.5 · 0.2 · 0.3 = 0.03, so the ideal length is −log₂ 0.03 = 5.059 bits. Terminating the code needs a whole dyadic interval inside the target one, which is why the emitted prefix here is six bits rather than five.

Question 6.C.4

Computational block

(optional)

A Bayesian mixture assigns weight $w_j=1/64$ to model $P_j$ . What is the worst-case regret of the mixture relative to $P_j$ on any sequence, in bits? (tolerance 0.005)

AnswerAbsolute tolerance: ±0.005

Answer and explanation

Numeric answer: 6 (tolerance 0.005). The regret is at most log₂ 64 = 6 bits for the whole sequence, no matter how long it is. Per symbol it therefore tends to zero, which is what makes a mixture a usable universal code.