Tag Info

Entropy is a measure of how predictable the outcome of a random process is, or how much uncertainty one has in one's state of knowledge about an unknown piece of information, defined in terms of the probability distribution of possible values of the outcome or piece of information.

Entropy is defined in terms of a probability distribution on the set of possible values, which quantitatively characterizes a state of knowledge about uncertainty. A fair coin toss, with equal probability 1/2 for each outcome, has 1 bit of entropy, either as a property of the process or in the state of knowledge of someone who does not see your hand after you have tossed the coin.

The two most common kinds of entropy, when measured in bits, are:

• Shannon entropy, which is the average or expected number of bits that an optimal compression algorithm tuned for the distribution can compress it into, and is most often what unqualified ‘entropy’ refers to outside cryptography in information theory and coding theory; and
• min-entropy, which is the number of fair coin tosses coming up heads that the best guess for a single outcome has the same probability as, and is most often what unqualified ‘entropy’ refers to in cryptography.

Example. A four-sided die with probability 1/2 of turning up 1, probability 1/4 of turning up 2, and equal probabilities 1/8 of turning up 3 or 4, can be compressed into messages, say for transmission by telegram which costs by the bit, as follows:

• Transmit the face 1 as a 0 bit.
• Transmit 2 as the bit string 10.
• Transmit 3 as 110.
• Transmit 4 as 111.

The average number of bits in this compression scheme, which turns out to be optimal, is the sum of each number of bits weighted by its probability. A straightforward calculation shows that, because the compression scheme is optimal, the Shannon entropy in this case is 1.75 bits.

The most probable outcome, rolling a 1, has the same probability as a single fair coin toss coming up heads, 1/2. Thus the min-entropy is 1 bit.

This example illustrates that the min-entropy is never greater than the Shannon entropy; that is, Shannon entropy is an upper bound on min-entropy.

Thermodynamic entropy is related to Shannon entropy. In a thermodynamic system characterized by macroscopic averages such as temperature, pressure, volume, etc., the (thermodynamic) entropy change of the system is defined in terms of the macroscopic heat transfer into or out of it and its temperature change. A priori, this concept of classical thermodynamics may not be obviously related to information theory or probability distributions.

In the microscopic formulation of statistical mechanics, when a thermodynamic system is described in terms of macroscopic averages, there are many possible microscopic configurations that the system could be in that are compatible with the macroscopic averages. Among the probability distributions on microscopic configurations compatible with the macroscopic averages, the maximum Shannon entropy of any such probability distribution is the (thermodynamic) absolute entropy of the system (with an appropriate choice of logarithm base to make the units commensurate), and a change in entropy coincides with a difference of absolute entropies.

Historically, the term entropy was invented by Rudolf Clausius as a macroscopic property of a thermodynamic system, before Ludwig Boltzmann connected it to microscopic configurations in his H theorem, and J. Willard Gibbs expounded on it in the development of statistical mechanics. Claude Shannon later stumbled upon the same formula as Gibbs, but from the perspective of channel coding and information theory. Inspired by Boltzmann and Gibbs, Shannon adopted the name ‘entropy’ and letter H for the property of any probability distribution.

Rényi entropy is a generalization that covers both Shannon entropy and min-entropy as instances, but it seldom figures into cryptography. Entropy can be measured in other units such as nats, decibans, etc., if computed with base-e, base-10, etc., logarithms instead of base-2 logarithms, but this is seldom seen in cryptography.