32.2 Entropy and Uncertainty

Definition 32–4. Let the random variable X take values from some set { x₁, ... x_n }. The value x_i occurs with probability p(X = x_i), where = 1.

The entropy, or uncertainty, of x is

H(X) = - lg p(X = x_i)

where "lg x" is the base 2 logarithm of x. (For purposes of this definition, we define 0 lg 0 to be 0.)

This definition measures the uncertainty of a message in bits.

EXAMPLE: Suppose the message m is either "yes" or "no," with either message being equally likely. Because there are two possibilities for the message, intuitively there is 1 bit of uncertainty. The message can be represented as either a 0 or a 1. From the definition above, H(M) = p(M = mi) lg p(M = mi)   = – p(M = yes) lg p(M = yes) – p(M = no) lg p(M = no)   = –2–1 lg 2–1 – 2–1 lg 2–1 = 2–1 + 2–1 = 1 as expected.

EXAMPLE: Suppose each message is equally likely—that is, p(M = mi) = 1/n. Then H(M) = p(M = mi) lg p(M = mi)   = (1/n) lg (1/n) = –n [ (1/n) lg (1/n) ] = –lg n–1 = lg n The uncertainty of m is the number of bits needed to represent n.

EXAMPLE: Suppose Ann, Paul, and Pamela are finalists in a game. Ann and Pamela are twice as likely to win as Paul is. Let W be the random variable representing the winner, and let w1 = Ann, w2 = Pamela, and w3 = Paul. Then p(W = w1) = 2/5, p(W = w2) = 2/5, p(W = w3) = 1/5, and H(W) = p(W = wi) lg p(W = wi)   = –p(W = w1) lg p(W = w1) – p(W = w2) lg p(W = w2) – p(W = w3) lg p(W = w3)   = – (2/5) lg (2/5) – (2/5) lg (2/5) – (1/5) lg (1/5) = –4/5 + lg 5 Ý 1.52 Were all three players equally likely to win, the uncertainty would be lg 3 Ý 1.58, again matching our intuition that the winner is less uncertain if two of the three are more likely to win. To take an extreme case, were Paul 100 times more likely to win than either Ann or Pamela, the uncertainty would be 0.14, considerably lower still.

EXAMPLE: Given a fair die, the uncertainty of the result of rolling it is lg 6 Ý 2.58. When two fair dice are rolled, the uncertainty of the result is 3.27.