Entropy

Summary

Entropy is the average uncertainty in the outcome of an experiment.
It sets the limit, how far data can be compressed.

Introduction

Consider the following game:
We place a bet on a sequence of ten coin throws. If the sequence was predicted correctly, the player wins.
Each throw - heads or tails - adds one bit of uncertainty.
The sequence of throws is described by a random variable

Entropy

can take one out of $2^{10}=1024$ different results that are equally probable, and the chance to guess the correct sequence is $\frac{1}{1024}$ .
The entropy

is 10 bits, as shown in figure 1, boxes representing bits:

Figure 1: Entropy of a sequence of coin throws

Conditional Entropy

The game has changed: Now, the player knows the outcome of the first three coin throws beforehand, denoted as random variable

.
This is shown in figure 2.

Figure 2: Conditional Entropy: The first three coin throws are known

When

is known, the remaining uncertainty - or Entropy - reduces from 10 bits to 7 bits.
This is called Conditional Entropy

(read “Entropy of X given Y”). Only

sequences remain.

Mutual information

A different game:
Two players know different parts of a sequence of coin throws.
Player A knows the first four coin throws, and player B the eight last ones. This is shown in figure 3.

Figure 3: Two players observe different parts of the sequence of coin throws

Player A has 4 bits worth of information by knowing

, and player B 8 bits by knowing

.

Two bits are known by both, and that is the so-called mutual information

between

and

(figure 4).

Figure 4: Mutual information: Overlapping knowledge by both players

The mutual information tells, how much information is known to both players.
In other words, it tells how much player A knows about player B and vice versa.

Mutual information is the loss of uncertainty in

, when

becomes known:

Joint Entropy

Assume we know nothing about

and

. The uncertainty

about player A's sequence is four bits, and

is 8 bits towards player B.
However, the total uncertainty regarding both is only 10 bits (not 12), because two coin throws are known to both.
The total uncertainty is called the Joint Entropy

.
It can never exceed

(figure 5).

Figure 5: Joint Entropy

Redundancy

Player A knows four bits through

, and player B 8 bits through

. Their total knowledge is 12 bits. But it can be reduced to ten bits - two bits are redundant.
Redundancy is calculated as the “compressed amount of data” (10 bits) relative to the “uncompressed amount” (12 bits).
$R(X, Y)=\frac{H(X, Y)}{H(X)+H(Y)}$
Note, that in case of independent

and

, the redundancy is 50 %. One of them could be thrown away, without losing information!

© Markus Nentwig 2007-2008
The content of this page is provided without any warranty and may not be reproduced without permission.

Comments? Questions?

Please send me a mail! mnentwig@elisanet.fi