Practice: Information theory

Information theory

Warm-upHuman

A source emits one of $8$ symbols, all equally likely. What is its entropy, in bits?

Information theory

CoreHuman

A binary prefix code already contains the codewords $0$ and $10$ . What is the largest number of further codewords of length exactly $3$ that can be added while keeping the code prefix-free?

Information theory

CoreHuman

Which statements about the mutual information $I(X; Y)$ of finite random variables are true? (Choose all that apply.)

Choose all that apply

I(X; Y) = I(Y; X)

.

I(X; Y) \ge 0

, with equality if and only if

X

and

Y

are independent.

I(X; Y) \le \min(H(X), H(Y))

.Applying a function

g

to

Y

can increase the information it carries:

I(X; g(Y))

may exceed

I(X; Y)

.

Information theory

CoreHuman

In the proof of Gibbs' inequality we bound $\sum_x p(x)\ln\frac{q(x)}{p(x)} \le \sum_x \big(q(x) - p(x)\big)$ . Which fact justifies this step?

Choose one

\ln t \le t - 1

for all

t > 0

, applied with

t = q(x)/p(x)

and multiplied by

p(x) \ge 0

.

\ln

is increasing.

\sum_x q(x) \le 1

.

\ln t \ge 0

for

t \ge 1

.

Information theory

CoreHuman

Build a Huffman code for four symbols with probabilities $0.4, 0.3, 0.2, 0.1$ . What is the expected codeword length, in tenths of a bit (so $1.5$ bits would be $15$ )?

Information theory

CoreHuman

A binary symmetric channel flips each bit independently with probability $p$ . For which values of $p$ is its capacity exactly $1$ bit per use? (Choose all that apply.)

Choose all that apply

p = 0

p = 1

p = \tfrac12

p = 0.01

Information theory

StretchHuman

A start-up claims its lossless compressor shortens every file of exactly $1000$ bits by at least one bit. What is wrong?

Choose one

There are

2^{1000}

such files but only

2^{1000} - 1

files shorter than

1000

bits, so two files would get the same output and could not both be recovered.Nothing in principle: with a good enough model, every file can be compressed below its entropy.It is possible, but the compressor would be too slow.Only files with meaningful content can be compressed, and random files have no meaning.

Information theory

CoreFormal

Which Lean statement formalises Kraft's inequality for prefix codes? (u <+: v means u is a prefix of v.)

Choose one

(hpf : ∀ u ∈ C, ∀ v ∈ C, u <+: v → u = v) : ∑ w ∈ C, (1 / 2 : ℝ) ^ w.length ≤ 1(hpf : ∀ u ∈ C, ∀ v ∈ C, u <+: v → u = v) : ∑ w ∈ C, (1 / 2 : ℝ) ^ w.length = 1(hpf : ∀ u ∈ C, ∀ v ∈ C, u ≠ v) : ∑ w ∈ C, (1 / 2 : ℝ) ^ w.length ≤ 1(hpf : ∀ u ∈ C, ∀ v ∈ C, u <+: v → u = v) : ∑ w ∈ C, (2 : ℝ) ^ w.length ≤ 1

Information theory

StretchComputational

Write entropy(probs) returning $-\sum p\log_2 p$ in bits (skipping zero probabilities), and kl(p, q) returning $D(p\,\|\,q) = \sum p\log_2(p/q)$ (also skipping terms with $p = 0$ ). The tests check examples from the lesson, Gibbs' inequality on random distributions, and the asymmetry of relative entropy.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.