Question 3

Let X be a random variable taking on n values with probabilities p1, p2, . . . , pn. We will assume all probabilities are non-zero. Recall from Lecture 9 that the min-entropy of X, denoted E∞(X), is given by

(a) Show that if X is not uniformly distributed then necessarily one of the pi’s is > 1/n.

(b) Show that if X is not uniformly distributed then F∞(X) < n.

(c) Argue that min-entropy is the highest if X is uniformly distributed. What is the min-entropy (E∞(X)) in this case.