Information Theory

Entropy

Entropy is the fundamental measure of information theory. It is a very broad concept and it is used to measure the uncertainty of a random variable. It is defined as:

Where x is a random variable and P(·) is its probability density function. The angled brackets denote expectation. Depending on the base of the logarithm that is used the units of entropy change. The common units are nats for base e and bits for base 2. Since the material in this thesis is mainly on discrete mathematics we’ll also consider the discrete definition of entropy:

where X is the set that x belongs to. Entropy is bounded from below at 0. An entropy of 0 denotes zero uncertainty which is the case for deterministic processes. From above, the limit is at log(a) for a random variable distributed from 0 to a. This is the case when we have a uniform distribution where uncertainty is maximal. As an example consider the coin toss case. For a fair coin the heads/tails probabilities are:

P(heads) = 0.5

P(heads) = 0.5

So the entropy is: H(coin)=-[P(heads)·lnP(heads)+P(tails)·lnP(tails)] = ln2

So we have maximum uncertainty.

If we had a maximally biased coin (towards heads), then:

P(heads) = 1

P(heads) = 0

and: H(coin)=-[P(heads)·lnP(heads)+P(tails)·lnP(tails)] = 0

(Elaluated at the limit where lim(x*ln(x))=0

)
and if the entropy is 0 we are always certain about the results.

In coding theory entropy has also been used as a measure of the length of the shortest possible description for a random variable sequence.