T1: 4. Information Theory

Question 1

Define Shannon entropy (words)

Answer 1

A measure of how unsure we are about the value of X, or on average how much information we gain when we learn the value of X.

Question 2

Define Shannon entropy (formula)

Answer 2

H(X) = -SUM_x[p(x)log(p(x)]

where x = {finite set}

Question 3

What is 0log(0) in this case?

Answer 3

0

Question 4

Define Shannon’s Noiseless Coding Theorem

Answer 4

The Shannon entropy gives a lower bound for the number of bits per letter required to encode a message.

Question 5

What probability would specify N yes or no questions to Shannon entropy?

Answer 5

p(x) = (1/2)^n

Question 6

What distribution of probabilities maximises H(X)

Answer 6

p(x_n)=1/n

Equal probability for each outcome.

Question 7

Give the formula for joint entropy

Answer 7

H(X,Y) = -SUM_x,y[p(x,y)log(p(x,y)]

where x = {finite set}

Question 8

How does joint entropy relate to individual entropies of two events X and Y?

Under what condition is this equality?

Answer 8

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

If X and Y are independent, with p(x,y)=p(x)p(y).

Question 9

Where is relative entropy useful?

Answer 9

Where we have the two random variables which take the same values but with different probability distributions.

Question 10

State the relative entropy formula H(p(x)||q(x))

Answer 10

• H(X) - SUM_x p(x) log q(x)

Question 11

Under what case is relative entropy =0?

Answer 11

p(x) = q(x)

Question 12

Define the Von-Neumann entropy

Answer 12

S(ρ) = Tr (ρ logρ) = SUM_i ei log ei

where ei are eigenvalues of ρ

Question 13

Define the relative Von-Neumann entropy S(ρ_1 ||ρ_2)

Answer 13

Tr (ρ_1 log ρ_1) - Tr (ρ_1 log ρ_2) >= 0

Question 14

Define conditional uncertainty H(X|Y)

Answer 14

This is the remaining uncertainty in X given we know the value of Y

Question 15

State the conditional uncertainty formula H(X|Y)

Answer 15

H(X|Y) = H(X,Y) - H(Y)

Question 16

Define mutual information of X and Y: H(X:Y)=H(Y:X)

Answer 16

H(X) + H(Y ) - H(X, Y )

Question 17

Given a bipartite system with density matrices ρ_a, ρ_b and ρ for the combined system, state each VN entropy

Answer 17

S(A) = S(ρ_a)
S(B) = S(ρ_b)
S(A,B) = S(ρ)

Question 18

Why can conditional VN entropy be negative?

Answer 18

If ρ is a pure state, S(A, B) = 0 but this does not imply S(B) = 0. If Bob makes a measurement on the pure state, unless he CC to Alice the result, she has a mixed state.