User:TheObtuseAngleOfDoom/Temp/Information entropy

In information theory, entropy is a measure of the randomness of an information source. Information entropy is distinct from thermodynamic entropy, although these two concepts are not unrelated.

Basic concept

The basic concept of entropy in information theory has to do with how much randomness there is in an information source. A signal, a computer file, and English text are all examples of information sources.

As an example consider some English text, encoded as a string of letters, spaces and punctuation (so our signal is a string of characters). Since some characters are not very likely (e.g. 'z') while others are very common (e.g. 'e') the string of characters is not really as random as it might be. On the other hand, since we cannot predict with absolute certainty what the next character will be, it does have some 'randomness'. Entropy is a measure of this randomness. It is important to note that a measure of randomness is equivalent to a measure of information. Returning to our example, if we were able to predict perfectly the next character, we would not gain any information from being told the next character. In such a case there is no randomness and no information gained and so we would expect the entropy to be 0, and indeed it is.

Formal definition

Let X be a discrete random variable with probability mass function $p(x)$ whose support is a finite set $\mathbb {X}$ . Shannon^[1] defined the entropy $H(X)$ of X as

H(X)=-\sum _{x\in \mathbb {X} }p(x)\log p(x)=\mathrm {E} \left({\frac {1}{\log p(X)}}\right),

where E is the expectation operator. The logarithm is usually taken to base 2, in which case the unit of entropy is the bit. Since entropy depends not on the values of X but only the probabilities, it H(X) can also be refered to as H(f). It is important to notice from the expression of the definition as an expectation that entropy is in fact the expected value of the self-information or surprisal of X.

Example: Bernoulli trial

Entropy of a Bernoulli trial as a function of success probability.

The Bernoulli trial is useful in illustrating the properties of entropy. If X is a Bernoulli trial, X takes value 1 with probability $\theta$ and value 0 with probability $1-\theta$ . If $\theta$ is 0, X will always take value 0, and thus be no longer random. In this case, its entropy would be

H(X)=-1\log 1=0\,

bits.

NB: The term corresponding to $X=1$ was not included in the sum because it happens with probability 0 and so is not in the support set of X, which we are summing over.

A similar result is achieved when $\theta =1$ .

Another case of particular interest in this example is when $\theta =0.5$ . Then $X=0$ with probability '0.5' and $X=1$ with probability '0.5', i.e. X follows a uniform distribution on {0,1}. Here, $H(x)=-0.5\log _{2}0.5-0.5\log _{2}0.5=1$ bit. In this case, the each outcome of X is equiprobable, and it is impossible to make an "educated guess" as to its outcome. We expect H(X) to be maximum here, and the graph confirms this. In fact, it can be proven that the uniform distribution over N outcomes has the greatest entropy out of all distributions over N outcomes.

That is, the entropy of the event x is the sum, over all possible outcomes i of x, of the product of the probability of outcome i times the log of the probability of i (which is also called s's surprisal - the entropy of x is the expected value of its outcome's surprisal). We can also apply this to a general probability distribution, rather than a discrete-valued event.

Shannon shows that any definition of entropy satisfying his assumptions will be of the form:

-K\sum _{i=1}^{n}p(i)\log p(i).\,\!

where K is a constant (and is really just a choice of measurement units).

Shannon defined a measure of entropy (H = − p₁ log₂ p₁ − … − p_n log₂ p_n) that, when applied to an information source, could determine the minimum channel capacity required to reliably transmit the source as encoded binary digits. The formula can be derived by calculating the mathematical expectation of the amount of information contained in a digit from the information source. Shannon's entropy measure came to be taken as a measure of the uncertainty about the realization of a random variable. It thus served as a proxy capturing the concept of information contained in a message as opposed to the portion of the message that is strictly determined (hence predictable) by inherent structures. For example, redundancy in language structure or statistical properties relating to the occurrence frequencies of letter or word pairs, triplets etc. See Markov chain.

Shannon's definition of entropy is closely related to thermodynamic entropy as defined by physicists and many chemists. Boltzmann and Gibbs did considerable work on statistical thermodynamics, which became the inspiration for adopting the word entropy in information theory. There are relationships between thermodynamic and informational entropy. In fact, in the view of Jaynes (1957), thermodynamics should be seen as an application of Shannon's information theory: the thermodynamic entropy is interpreted as being an estimate of the amount of further Shannon information (needed to define the detailed microscopic state of the system) that remains uncommunicated by a description solely in terms of the macroscopic variables of classical thermodynamics. (See article: MaxEnt thermodynamics). Similarly, Maxwell's demon reverses thermodynamic entropy with information; but if it is itself bound by the laws of thermodynamics, getting rid of that information exactly balances out the thermodynamic gain the demon would otherwise achieve.

It is important to remember that entropy is a quantity defined in the context of a probabilistic model for a data source. Independent fair coin flips have an entropy of 1 bit per flip. A source that always generates a long string of A's has an entropy of 0, since the next character will always be an 'A'.

The entropy rate of a data source means the average number of bits per symbol needed to encode it. Empirically, it seems that entropy of English text is between 1.1 and 1.6 bits per character, though clearly that will vary from text source to text source. Experiments with human predictors show an information rate of 1.1 or 1.6 bits per character, depending on the experimental setup; the PPM compression algorithm can achieve a compression ratio of 1.5 bits per character.

From the preceding example, note the following points:

The amount of entropy is not always an integer number of bits.
Many data bits may not convey information. For example, data structures often store information redundantly, or have identical sections regardless of the information in the data structure.

Entropy effectively bounds the performance of the strongest lossless (or nearly lossless) compression possible, which can be realized in theory by using the typical set or in practice using Huffman, Lempel-Ziv or arithmetic coding. The performance of existing data compression algorithms is often used as a rough estimate of the entropy of a block of data.

A common way to define entropy for text is based on the Markov model of text. For an order-0 source (each character is selected independent of the last characters), the binary entropy is:

H({\mathcal {S}})=-\sum p_{i}\log _{2}p_{i},\,\!

where p_i is the probability of i. For a first-order Markov source (one in which probabilities are dependent on the immediately preceding character but not on older history except through the immediately preceding character), the entropy rate is:

H({\mathcal {S}})=-\sum _{i}p_{i}\sum _{j}\ p_{i}(j)\log _{2}p_{i}(j),\,\!

where i is a state (certain preceding characters) and $p_{i}(j)$ is the probability of $j$ given $i$ as the previous character (s).

For a second order Markov source, the entropy rate is

H({\mathcal {S}})=-\sum _{i}p_{i}\sum _{j}p_{i}(j)\sum _{k}p_{i,j}(k)\ \log \ p_{i,j}(k).\,\!

In general the b-ary entropy of a source ${\mathcal {S}}$ = (S,P) with source alphabet S = {a₁, …, a_n} and discrete probability distribution P = {p₁, …, p_n} where p_i is the probability of a_i (say p_i = p(a_i)) is defined by:

H_{b}({\mathcal {S}})=-\sum _{i=1}^{n}p_{i}\log _{b}p_{i}\,\!

Note: the b in "b-ary entropy" is the number of different symbols of the "ideal alphabet" which is being used as the standard yardstick to measure source alphabets. In information theory, two symbols are necessary and sufficient for an alphabet to be able to encode information, therefore the default is to let b = 2 ("binary entropy"). Thus, the entropy of the source alphabet, with its given empiric probability distribution, is a number equal to the number (possibly fractional) of symbols of the "ideal alphabet", with an optimal probability distribution, necessary to encode for each symbol of the source alphabet. Also note that "optimal probability distribution" here means a uniform distribution: a source alphabet with n symbols has the highest possible entropy (for an alphabet with n symbols) when the probability distribution of the alphabet is uniform. This optimal entropy turns out to be $log_{b}\,n$ .

Another way to define the entropy function H (not using the Markov model) is by proving that H is uniquely defined (as earlier mentioned) iff H satisfies 1) - 3):

1) H(p₁, …, p_n) is defined and continuous for all p₁, …, p_n where p_i $\in$ [0,1] for all i = 1, …, n and p₁ + … + p_n = 1. (Remark that the function solely depends on the probability distribution, not the alphabet.)

2) For all positive integers n, H satisfies

H\underbrace {\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)} _{n\ \mathrm {arguments} }<H\underbrace {\left({\frac {1}{n+1}},\ldots ,{\frac {1}{n+1}}\right).} _{n+1\ \mathrm {arguments} }

3) For positive integers b_i where b₁ + … + b_n = n, H satisfies

H\underbrace {\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)} _{n}=H\underbrace {\left({\frac {b_{1}}{n}},\ldots ,{\frac {b_{n}}{n}}\right)} _{n}+\sum _{i=1}^{n}{\frac {b_{i}}{n}}H\underbrace {\left({\frac {1}{b_{i}}},\ldots ,{\frac {1}{b_{i}}}\right)} _{b_{i}}.

Efficiency

A source alphabet encountered in practice should be found to have a probability distribution which is less than optimal. If the source alphabet has n symbols, then it can be compared to an "optimized alphabet" with n symbols, whose probability distribution is uniform. The ratio of the entropy of the source alphabet with the entropy of its optimized version is the efficiency of the source alphabet, which can be expressed as a percentage.

This implies that the efficiency of a source alphabet with n symbols can be defined simply as being equal to its n-ary entropy.

Derivation of Shannon's entropy

Since the entropy was given as a definition, it does not need to be derived. On the other hand, a "derivation" can be given which gives a sense of the motivation for the definition as well as the link to thermodynamic entropy.

Q. Given a roulette with n pockets which are all equally likely to be landed on by the ball, what is the probability of obtaining a distribution (A₁, A₂, …, A_n) where A_i is the number of times pocket i was landed on and

P=\sum _{i=1}^{n}A_{i}\,\!

is the total number of ball-landing events?

A. The probability is a multinomial distribution, viz.

p={\Omega  \over \mathrm {T} }={P! \over A_{1}!\ A_{2}!\ A_{3}!\ \dots \ A_{n}!}\left({\frac {1}{n}}\right)^{P}\,\!

where

\Omega ={P! \over A_{1}!\ A_{2}!\ A_{3}!\ \dots \ A_{n}!}\,\!

is the number of possible combinations of outcomes (for the events) which fit the given distribution, and

\mathrm {T} =n^{P}\

is the number of all possible combinations of outcomes for the set of P events.

Q. And what is the entropy?

A. The entropy of the distribution is obtained from the logarithm of Ω:

H=\log \Omega =\log {\frac {P!}{A_{1}!\ A_{2}!\ A_{3}!\dots \ A_{n}!}}\,\!

=\log P!-\log A_{1}!-\log A_{2}!-\log A_{3}!-\dots -\log A_{n}!\

=\sum _{i}^{P}\log i-\sum _{i}^{A_{1}}\log i-\sum _{i}^{A_{2}}\log i-\dots -\sum _{i}^{A_{n}}\log i\,\!

The summations can be approximated closely by being replaced with integrals:

H=\int _{1}^{P}\log x\,dx-\int _{1}^{A_{1}}\log x\,dx-\int _{1}^{A_{2}}\log x\,dx-\dots -\int _{1}^{A_{n}}\log x\,dx.\,\!

The integral of the logarithm is

\int \log x\,dx=x\log x-\int x\,{dx \over x}=x\log x-x.\,\!

So the entropy is

H=(P\log P-P+1)-(A_{1}\log A_{1}-A_{1}+1)-(A_{2}\log A_{2}-A_{2}+1)-\dots -(A_{n}\log A_{n}-A_{n}+1)

=(P\log P+1)-(A_{1}\log A_{1}+1)-(A_{2}\log A_{2}+1)-\dots -(A_{n}\log A_{n}+1)

=P\log P-\sum _{x=1}^{n}A_{x}\log A_{x}+(1-n)\,\!

Change A_x to p_x = A_x/P and change P to 1 (in order to measure the "bias" or "unevenness", in the probability distribution of the pockets for a single event), then