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.