Entropy

 

Definitions:

Let X  be a random variable that takes on a finite set of values x1, x2, . . . , xn with probability P(X =xi) = pi, where 0 ≤ pi ≤ 1 for each i, 1 ≤ i ≤ n, and .

Also, let Y  be a random variable that takes on a finite set of values.

Information theory is concerned with a mathematical theory of communication and includes the study of redundancy and the underlying limits of communication channels.

The entropy (or uncertainty) of X is defined to be H(X) = , where  if pi = 0.

The joint entropy of X and Y is defined to be

H(X, Y ) = −.

If X and Y are random variables, the conditional entropy of X given Y = y is

H(X | Y =y) = −.

The conditional entropy of X given Y (or equivocation of Y about X), is

H(X | Y) = −.

(The summation indices x and y range over all values of X and Y , respectively.)

Facts:

1. Information theory provides a theoretical basis for many results in error-correcting codes and cryptography, and provides theoretical bounds useful as metrics for evaluating conjectures in both areas.

2. The entropy of X is a measure of the amount of information provided by an observation of X.

3. The entropy of X is also useful for approximating the number of bits required to encode the elements of X.

4. If X and Y are random variables, then:

• 0 ≤ H(X) ≤ log2 n;

• H(X) = 0 if and only if pi = 1 for some i, and pj = 0 for all j ≠ i (that is, there is no uncertainty of the result);

• H(X) = log2 n if and only if pi = 1/ n for each i, 1 ≤ i ≤ n (that is, all outcomes are equally likely);

• H(X, Y ) ≤ H(X) + H(Y );

• H(X, Y ) = H(X) + H(Y ) if and only if X and Y are independent.

5. The quantity H(X | Y ) measures the amount of uncertainty remaining about X after Y has been observed.

7. If X and Y are random variables, then:

• H(X | Y ) ≥ 0;

• H(X |X) = 0;

• H(X, Y ) = H(Y ) + H(X | Y );

• H(X | Y ) ≤ H(X);

• H(X | Y ) = H(X) if and only if X and Y are independent.

Example:

1. If X is the random variable on the set {x1, x2, x3, x4} with X(x1) = 0.4, X(x2) = 0.3, X(x3) = 0.2, and X(x4) = 0.1, then the entropy of X is

H(X) = −(0.4 log2 0.4 + 0.3 log2 0.3 + 0.2 log2 0.2 + 0.1 log2 0.1) ≈ −1.84644.