Information entropy

Entropy is a concept in thermodynamics (see thermodynamic entropy) and information theory. The two concepts do actually have something in common, although it takes a thorough understanding of both fields for this to become apparent.

Claude E. Shannon defined a measure of entropy (H = - Σ p_i log p_i) that, when applied to an information source, could determine the capacity of the channel required to transmit the source as encoded binary digits. Shannon's measure of entropy came to be taken as a measure of the information contained in a message, as opposed to the portion of the message that is strictly determined (hence predictable) by inherent structures, like for instance redundancy in the structure of languages or the statistical properties of a language relating to the frequencies of occurrence of different letter or word pairs, triplets etc. See Markov chains.

Entropy as defined by Shannon is closely related to thermodynamic entropy as defined by physicists and many chemists. Boltzmann and Gibbs did considerable work on statistical thermodynamics. This work was the inspiration for adopting the term entropy in information theory. There are deep relationships between entropy in the thermodynamic and informational senses. For instance, Maxwell's demon needs information to reverse thermodynamic entropy and getting that information exactly balances out the thermodynamic gain that the demon would otherwise achieve.

In information theory, entropy is conceptually the actual amount of (information theoretic) information in a piece of data. Entirely random byte data has an entropy of about infinity, since you never know what the next character will be. A long string of A's has an entropy of 0, since you know that the next character will always be an 'A'. The entropy of English text is about 1.5 bits per character (Try compressing it with the PPM compression algorithm!) The entropy rate of a data source means the average number of bits per symbol needed to encode it.

Many of the bits in the data may not be conveying any information. For instance it is often the case that data structures store information redundantly, or have sections that are always the same regardless of the information in the data structure.
The amount of entropy is not always an integer number of bits.

Entropy is effectively the strongest non-lossy compression possible, which can be realised in theory by the use of the typical set or in practise using Huffman, Lempel-Ziv or Arithmetic coding. The definition of entropy is based on the Markov model of text. For an order-0 source (each character is selected independent of the last characters), the entropy is:

Where is the probability of . For a second-order Markov source (one in which probabilities are dependent on the preceding character), the entropy rate is:

Where is a state (certain preceding characters) and is the probability of given as the previous character (s).