Information Theory for ML2 / 16

Module 2. Entropy

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 / 20 · Correct: 0

Question 2.1.1

2.1. Definition and properties

Which quantity is the surprisal of a particular outcome $x$ relative to a distribution $P$ ?

One correct optionA

-\sum_xp(x)\log_2p(x)

\sum_xp(x)^2

-\log_2p(x)

2^{-\log_2p(x)}

A) $-\sum_xp(x)\log_2p(x)$

B) $\sum_xp(x)^2$

C) $-\log_2p(x)$

D) $2^{-\log_2p(x)}$

Answer and explanation

Correct answer: C. Surprisal refers to one outcome. Option A is entropy, the expectation of surprisal, and option D simplifies back to p(x) itself.

Question 2.1.2

2.1. Definition and properties

A random variable has an alphabet of $n$ symbols, but only $m<n$ have positive probability. What is the sharpest general upper bound on its entropy?

One correct optionA

H(X)\le\log_2(n-m)

H(X)\le\log_2n

, attained by the uniform distribution on the

m

symbolsC

H(X)\le m/n

H(X)\le\log_2m

, attained by the uniform distribution on the support

A) $-\sum_xp(x)\log_2p(x)$

B) $H(X)\le\log_2n$ , attained by the uniform distribution on the $m$ symbols

C) $H(X)\le m/n$

D) $H(X)\le\log_2m$ , attained by the uniform distribution on the support

Answer and explanation

Correct answer: D. Entropy cannot exceed the logarithm of the positive support size. The bound log₂ n is also true but weaker, and it cannot be attained when m < n, which is exactly why option B is wrong about the equality case.

Question 2.1.3

2.1. Definition and properties

Which inequality correctly states concavity of entropy?

One correct optionA

H(\lambda p+(1-\lambda)q)\ge\lambda H(p)+(1-\lambda)H(q)

H(\lambda p+(1-\lambda)q)\le\lambda H(p)+(1-\lambda)H(q)

H(\lambda p+(1-\lambda)q)=H(p)+H(q)

H(\lambda p+(1-\lambda)q)\ge\max\{H(p),H(q)\}

A) $-\sum_xp(x)\log_2p(x)$

B) $H(\lambda p+(1-\lambda)q)\le\lambda H(p)+(1-\lambda)H(q)$

C) $H(\lambda p+(1-\lambda)q)=H(p)+H(q)$

D) $H(\lambda p+(1-\lambda)q)\ge\max\{H(p),H(q)\}$

Answer and explanation

Correct answer: A. The entropy of a mixture is no smaller than the average entropy of its components. It need not exceed every component, so option D claims more than concavity gives.

Question 2.2.1

2.2. Joint and conditional entropy

What is the chain rule for three random variables?

One correct optionA

H(X,Y,Z)=H(X)+H(Y)+H(Z)

for all

X,Y,Z

H(X,Y,Z)=H(X)+H(Y\mid X)+H(Z\mid X,Y)

H(X,Y,Z)=H(X)+H(Y\mid X)+H(Z\mid Y)

H(X,Y,Z)=H(X)H(Y\mid X)H(Z\mid X,Y)

A) $-\sum_xp(x)\log_2p(x)$ for all $X,Y,Z$

B) $H(X,Y,Z)=H(X)+H(Y\mid X)+H(Z\mid X,Y)$

C) $H(X,Y,Z)=H(X)+H(Y\mid X)+H(Z\mid Y)$

D) $H(X,Y,Z)=H(X)H(Y\mid X)H(Z\mid X,Y)$

Answer and explanation

Correct answer: B. Each new variable is added conditioned on all previous ones, not just the most recent. Conditioning only on Y, as in option C, drops information that X may still carry about Z.

Question 2.2.2

2.2. Joint and conditional entropy

Which statement about conditional entropy is correct?

One correct optionAFor every

x

, necessarily

H(Y\mid X=x)\le H(Y)

BAlways

H(Y\mid X)=H(Y)-H(X)

CAlways

H(Y\mid X)<H(Y)

unless

Y

is constantDAlways

H(Y\mid X)\le H(Y)

, but for an individual

x

it may happen that

H(Y\mid X=x)>H(Y)

A) For every $-\sum_xp(x)\log_2p(x)$ , necessarily $H(Y\mid X=x)\le H(Y)$

B) Always $H(Y\mid X)=H(Y)-H(X)$

C) Always $H(Y\mid X)<H(Y)$ unless $Y$ is constant

D) Always $H(Y\mid X)\le H(Y)$ , but for an individual $x$ it may happen that $H(Y\mid X=x)>H(Y)$

Answer and explanation

Correct answer: D. The inequality concerns the average over X. A particular observation can reveal a more ambiguous regime, and under independence the inequality is an equality, which rules out option C.

Question 2.2.3

2.2. Joint and conditional entropy

When does

$H(X,Y)=H(X)+H(Y)$

hold?

One correct optionAFor all discrete

X

and

Y

BIf and only if

X=Y

CIf and only if

X

and

Y

are independentDWhenever

X

and

Y

are uncorrelated

A) For all discrete $-\sum_xp(x)\log_2p(x)$ and $H(Y\mid X=x)\le H(Y)$

B) If and only if $X=Y$

C) If and only if $X$ and $Y$ are independent

D) Whenever $X$ and $Y$ are uncorrelated

Answer and explanation

Correct answer: C. By the chain rule, equality is equivalent to H(Y|X) = H(Y), which happens exactly under independence. Zero correlation is a much weaker condition and does not suffice.

Question 2.2.4

2.2. Joint and conditional entropy

Suppose data are generated by a distribution $P$ , while an autoregressive model defines $Q_\theta$ . What does

$\mathbb E_{X_{1:n}\sim P}\!\left[-\log_2q_\theta(X_{1:n})\right]$

compute?

One correct optionAThe entropy of

P

for every modelBThe cross-entropy of source

P

relative to model

Q_\theta

CThe entropy of the parameters

\theta

DThe predictive entropy of

Q_\theta

A) The entropy of $-\sum_xp(x)\log_2p(x)$ for every model

B) The cross-entropy of source $P$ relative to model $Q_\theta$

C) The entropy of the parameters $\theta$

D) The predictive entropy of $Q_\theta$

Answer and explanation

Correct answer: B. Whose distribution sits inside the logarithm and whose supplies the averaging are different questions. This equals the entropy of P only when the model and source conditionals agree P-almost surely, and it is not the model's own predictive entropy, which averages under Q.

Question 2.3.2

2.3. A coin, entropy rate, and English text

For a stationary process on a finite alphabet, the entropy rate can be written as

One correct optionA

\displaystyle h=\lim_{n\to\infty}H(X_n)

\displaystyle h=\sum_{n=1}^{\infty}H(X_n)

\displaystyle h=\lim_{n\to\infty}\frac1nH(X_n\mid X_1,\ldots,X_{n-1})

\displaystyle h=\lim_{n\to\infty}H(X_n\mid X_1,\ldots,X_{n-1})=\lim_{n\to\infty}\frac1nH(X_1,\ldots,X_n)

A) $-\sum_xp(x)\log_2p(x)$

B) $\displaystyle h=\sum_{n=1}^{\infty}H(X_n)$

C) $\displaystyle h=\lim_{n\to\infty}\frac1nH(X_n\mid X_1,\ldots,X_{n-1})$

D) $\displaystyle h=\lim_{n\to\infty}H(X_n\mid X_1,\ldots,X_{n-1})=\lim_{n\to\infty}\frac1nH(X_1,\ldots,X_n)$

Answer and explanation

Correct answer: D. Under stationarity the next-symbol conditional entropies are non-increasing and converge, and normalized block entropy has the same limit as a Cesàro mean. Note that the conditional entropy is not divided by n, which is the error in option C.

Question 2.3.3

2.3. A coin, entropy rate, and English text

What is the most accurate reading of Shannon's 1951 result for English text?

One correct optionAIn a particular prediction experiment he obtained roughly 0.6 to 1.3 bits per symbol as lower and upper bounds at long context, and concluded the magnitude was about one bitBHe measured the loss of a language model on a test corpusCHe proved a universal constant of exactly 1 bit for every English characterDHe established the entropy rate of English independently of the alphabet and the preprocessing

A) In a particular prediction experiment he obtained roughly 0.6 to 1.3 bits per symbol as lower and upper bounds at long context, and concluded the magnitude was about one bit

B) He measured the loss of a language model on a test corpus

C) He proved a universal constant of exactly 1 bit for every English character

D) He established the entropy rate of English independently of the alphabet and the preprocessing

Answer and explanation

Correct answer: A. Shannon emphasized the limits of the sample and the method. The result is historically important, but it is not an exact constant, and it is stated for a specific 27-symbol alphabet and protocol.

Question 2.3.4

2.3. A coin, entropy rate, and English text

What does bits per character computed from a particular LLM on a fixed corpus primarily measure?

One correct optionAThe number of model parameters per characterBA universal entropy of English independent of corpus and modelCA model-dependent cross-entropy, that is a coding rate under the specified evaluation setupDA lower bound on the entropy rate of the source

A) The number of model parameters per character

B) A universal entropy of English independent of corpus and model

C) A model-dependent cross-entropy, that is a coding rate under the specified evaluation setup

D) A lower bound on the entropy rate of the source

Answer and explanation

Correct answer: C. The result depends on corpus, preprocessing, available context, model, and possible leakage. Expected cross-entropy is no smaller than the corresponding source entropy. Average NLL on one finite corpus can fluctuate in either direction and does not by itself certify an upper or lower bound on entropy rate.

Question 2.4.1

2.4. Applications in ML/NLP/LLMs

Low predictive entropy of an LLM at a fixed context means that

One correct optionAprobability mass is concentrated on a small number of tokensBthe most probable token is factually correctCthe model is well calibratedDthe loss on the observed token will be small

A) probability mass is concentrated on a small number of tokens

B) the most probable token is factually correct

C) the model is well calibrated

D) the loss on the observed token will be small

Answer and explanation

Correct answer: A. Entropy measures concentration and nothing else. A model can be confidently wrong, which is exactly the case where the entropy is low and the loss on the observed token is large.

Question 2.4.4

2.4. Applications in ML/NLP/LLMs

What is the general relationship between mean loss $\widehat L_b$ and perplexity?

One correct optionA

\operatorname{PPL}=\log_b\widehat L_b

, independent of tokenizationB

\operatorname{PPL}=b^{\widehat L_b}

, and its numerical value also depends on tokenizationC

\operatorname{PPL}=b^{\widehat L_b}

, and it is comparable across tokenizersD

\operatorname{PPL}=1-\widehat L_b

A) $-\sum_xp(x)\log_2p(x)$ , independent of tokenization

B) $\operatorname{PPL}=b^{\widehat L_b}$ , and its numerical value also depends on tokenization

C) $\operatorname{PPL}=b^{\widehat L_b}$ , and it is comparable across tokenizers

D) $\operatorname{PPL}=1-\widehat L_b$

Answer and explanation

Correct answer: B. The base must match the base the loss was measured in: e for nats, 2 for bits. The tokenizer defines the prediction events themselves, so perplexities from different tokenizers are not directly comparable.

Question 2.1.4

Optional mathematical and engineering deepening

Why is it convenient to restrict to the support $\mathcal S=\{x:p(x)>0\}$ in the Jensen proof of $H(X)\le\log_2n$ ?

One correct optionABecause entropy is defined only for strictly positive probabilitiesBTo change the logarithm base from 2 to

e

CTo avoid the undefined expression

1/p(x)

when

p(x)=0

DBecause Jensen's inequality requires a finite support

A) Because entropy is defined only for strictly positive probabilities

B) To change the logarithm base from 2 to $e$

C) To avoid the undefined expression $1/p(x)$ when $p(x)=0$

D) Because Jensen's inequality requires a finite support

Answer and explanation

Correct answer: C. The convention 0 log 0 = 0 defines entropy correctly on the boundary of the simplex, so entropy itself is fine there. It is the intermediate expression inside the Jensen step that breaks at zero probability.

Question 2.3.1

Optional mathematical and engineering deepening

Why does the module denote binary entropy by $h_2(p)$ rather than $H_2(p)$ ?

One correct optionALowercase marks a quantity measured in natsBUppercase

H

is reserved for continuous random variablesCThe notation changes the logarithm base from 2 to

e

DLowercase

h_2

avoids confusion with Rényi entropy of order 2

A) Lowercase marks a quantity measured in nats

B) Uppercase $e$ is reserved for continuous random variables

C) The notation changes the logarithm base from 2 to $e$

D) Lowercase $h_2$ avoids confusion with Rényi entropy of order 2

Answer and explanation

Correct answer: D. The subscript 2 means two outcomes here, while in H₂ it usually means the Rényi order. The case of the letter is the only thing separating the two conventions.

Question 2.4.2

Optional mathematical and engineering deepening

Let $q_T(v)\propto\exp(z_v/T)$ for fixed logits. How does entropy vary with $T$ ?

One correct optionAIt is non-increasingBIt is non-decreasing; in nats,

\displaystyle \frac{dH(q_T)}{dT}=\frac{\operatorname{Var}_{q_T}(z)}{T^3}\ge0

CIt is always constantDIt is non-decreasing, and the same argument covers top-

k

and top-

p

filtering

A) It is non-increasing

B) It is non-decreasing; in nats, $e$

C) It is always constant

D) It is non-decreasing, and the same argument covers top- $k$ and top- $H(X)\le\log_2m$ filtering

Answer and explanation

Correct answer: B. Unless all logits are equal, entropy increases strictly with temperature. The statement is specific to pure temperature scaling: truncation methods first change the support and then renormalize, so they need a separate argument.

Question 2.4.3

Optional mathematical and engineering deepening

In basic one-step exact speculative decoding, the mean probability of accepting a draft token is

One correct optionA

\sum_v\min\{p(v),q(v)\}=1-\operatorname{TV}(p,q)

H(p)+H(q)

1-\operatorname{TV}(p,q)

only when

p

and

q

have equal entropyD

1-H(q)

A) $-\sum_xp(x)\log_2p(x)$

B) $H(p)+H(q)$

C) $1-\operatorname{TV}(p,q)$ only when $p$ and $q$ have equal entropy

D) $1-H(q)$

Answer and explanation

Correct answer: A. Acceptance is determined by the overlap of the draft and target distributions. Two drafts with identical entropy can have completely different acceptance rates, because entropy says nothing about where the mass lies.

Question 2.C.1

Computational block

Compute the entropy of $q_B=(0.40,0.30,0.20,0.10)$ in bits. (tolerance 0.002)

AnswerAbsolute tolerance: ±0.002

Answer and explanation

Numeric answer: 1.846 (tolerance 0.002). The classifier q_A = (0.97, 0.01, 0.01, 0.01) from §2.1 has the same argmax but an entropy of only 0.242 bits. Entropy is what separates them; the decision does not.

Question 2.C.2

Computational block

For the same $q_B$ , compute the effective number of alternatives $2^{H}$ . (tolerance 0.005)

AnswerAbsolute tolerance: ±0.005

Answer and explanation

Numeric answer: 3.596 (tolerance 0.005). Four outcomes with these probabilities carry as much uncertainty as about 3.6 equally likely ones. The number need not be an integer and is not the size of the support.

Question 2.C.3

Computational block

A biased die has $p=(1/2,1/4,1/8,1/16,1/32,1/32)$ . Compute its entropy in bits. (tolerance 0.002)

AnswerAbsolute tolerance: ±0.002

Answer and explanation

Numeric answer: 1.9375 (tolerance 0.002). Every probability is a power of two, so each surprisal is a whole number of bits and the entropy comes out exactly. A fair die would cost log₂ 6 = 2.585 bits, so the bias saves about 0.647 bits per roll.

Question 2.C.4

Computational block

(optional)

A target distribution is $p=(0.9,0.1)$ and a draft is $q=(0.1,0.9)$ . Compute the mean acceptance probability in one-step exact speculative decoding. (tolerance 0.005)

AnswerAbsolute tolerance: ±0.005

Answer and explanation

Numeric answer: 0.2 (tolerance 0.005). The overlap is min(0.9, 0.1) + min(0.1, 0.9) = 0.2. A draft equal to p would give 1.0 at exactly the same entropy, which is why acceptance depends on agreement rather than on sharpness.