80
$\begingroup$

I first saw the term "entropy" in a chemistry course while studying thermodynamics. During my graduate studies I encountered the term in many different areas of mathematics. Can anyone explain why this term is used and what it means. What I am looking for is a few examples where the term "entropy" is used to describe some mathematical object/quantity and its meaning there.

$\endgroup$
  • 71
    $\begingroup$ Entropy isn't what it used to be. $\endgroup$ – Vidit Nanda Oct 31 '13 at 0:27
  • 6
    $\begingroup$ This could be an interesting place to start: ncatlab.org/johnbaez/show/Entropy+as+a+functor $\endgroup$ – Todd Trimble Oct 31 '13 at 0:37
  • 7
    $\begingroup$ I read somewhere (Therefore it's true!! Right?) that when Claude Shannon was doing his early work on information theory, he was at first uncertain what word to use to refer to the concept he later called "entropy", when that word had long been used for a different concept in physics (either a related concept or an unrelated one, perhaps depending on your philosophy). Someone (a physicist, maybe?) told him he should call it "entropy" because nobody really knew what entropy is. $\endgroup$ – Michael Hardy Oct 31 '13 at 23:31
  • 8
    $\begingroup$ @MichaelHardy, von Neumann is supposed to be that someone (he was Shannon's advisor, iirc) $\endgroup$ – Mariano Suárez-Álvarez Nov 1 '13 at 1:54
  • 8
    $\begingroup$ Entropy measures our ignorance : It is the logarithm of the phase space volume of macroscopically indistinguishable states. See Roger Penrose, The road to reality, chapter 27.3 . $\endgroup$ – jjcale Nov 1 '13 at 18:15

11 Answers 11

94
$\begingroup$

Here is a simple story one can tell about the entropy

$$H = -\sum_{i=1}^n p_i \log p_i$$

of a discrete probability distribution. Suppose you wanted to describe how surprised you are upon learning that some event $E$ happened. Call your surprise upon learning that $E$ happened $s(E)$, the "surprisal." Here are some plausible conditions that $s$ could satisfy:

  • $s(E)$ is a decreasing function of the probability $\mathbb{P}(E)$. That is, the less likely something it is to happen, the more surprising it is that it ends up happening, and the likelihood of something happening is the only thing determining how surprising it is. For example, flipping $10$ heads in a row is more surprising than flipping $5$ heads in a row.

  • If $E_1$ and $E_2$ are independent, then $s(E_1 \cap E_2) = s(E_1) + s(E_2)$. That is, your surprise at learning that two independent events happened should be the sum of your surprises at learning that each individual event happened. For example, flipping $10$ coins heads in a row is twice as surprising as flipping $5$ coins heads in a row.

Exercise: These conditions imply that $s$ must be a positive scalar multiple of $- \log \mathbb{P}(E)$.

Then the expected surprisal is a positive scalar multiple of the entropy. Note in particular that $H$ is minimized if some $p_i = 1$, which corresponds to the same thing always happening and which is not surprising at all.

$\endgroup$
  • 7
    $\begingroup$ This is really nice, Qiaochu! $\endgroup$ – Jon Bannon Nov 1 '13 at 11:54
  • 7
    $\begingroup$ Nice explanation. So we're reduced to how plausible we find the conditions. The first one seems fine but the second one seems a little arbitrary -- why not weighted sum of powers, for example? I believe there are generalizations of Shannon entropy breaking this condition. So what's missing in this answer is an explanation of why to expect additivity. This is the place where I'd say it's better to put your statistical-mechanics hat on, for then the additivity of entropy as a disorder in the system seems obvious. $\endgroup$ – Marek Nov 1 '13 at 14:50
  • 5
    $\begingroup$ Using the term "information content" rather than "surprise" may make additivity seem more natural (even though this doesn't quite line up with standard terminology). $\endgroup$ – Timothy Chow Nov 2 '13 at 19:20
  • 2
    $\begingroup$ @Qiaochu Yaun, I am wondering if your story originates from undergraduate books in probability, such as Ross. He also explains why the second property is intuitive. $\endgroup$ – Mustafa Said Jul 24 '14 at 7:12
  • 2
    $\begingroup$ In general I see no guarantee that a probability space should provide enough pairs of independent events to constrain the possible "surprise" functions on it all that much. Perhaps the right characterization involves looking at all finite probability spaces at once, though I'm not sure what that characterization would look like. $\endgroup$ – Paul Siegel Feb 19 '17 at 5:34
23
$\begingroup$

From a modern point of view, the paradigmatic definition of entropy is that it is a number associated to a probability distribution over a finite sample space. Let $N$ be the size of your sample space and let $p_1, p_2, \ldots, p_N$ be the probabilities of the events. Then the entropy of the probability distribution is defined to be $$H = \sum_{i=1}^N - p_i \log p_i,$$ where we take $0 \log 0$ to be $0$. I've been purposely vague about the base of the logarithm; the choice of base is a matter of taste or convention. In combinatorics or computer science or information theory, one often deals with strings of binary digits, and then it's convenient to take the base of the logarithm to be 2. With this convention, it's an easy exercise to check that if $N=2^n$ and the probability distribution is uniform, then $H=n$; we can think of this as choosing an $n$-long binary string at random, and we often say that the entropy is "$n$ bits". Similarly you can check that if $p_i=1$ for some $i$ (and $p_j=0$ for $j\ne i$) then $H=0$. These two extreme cases give you some intuition for the idea that $H$ is a measure of "how random" your system is. If your $n$-bit string is deterministic then there's no entropy, and if instead it's totally random then there are $n$ bits of entropy. The closer your probability distribution is to uniform, the more entropy it has.

In physics, entropy was originally defined thermodynamically as $\int dQ/T$ where $Q$ is heat and $T$ is temperature. This doesn't look at all like the "paradigmatic definition" I gave above, but the connection is that Boltzmann showed that from a statistical-mechanics point of view, the thermodynamic entropy can be recovered as $k \sum_i -p_i \ln p_i$ where the sum is over all states $i$ of your system, and $k$ is Boltzmann's constant. (It's traditional to use the natural logarithm in stat mech.)

Entropy may also be thought of as a measure of information content. This can sound confusing at first, since intuitively we tend to think of information as meaningful content, and if something is totally random then how can it carry any meaningful content? An example that may be helpful is to consider compression algorithms. Think of a text document (or photo, or video) as a sequence of bytes. If you take a normal, uncompressed document and look at the frequency distribution of the bytes, you will see that it is far from uniform. Some bytes are much more frequently occurring than others. But if you then run the document through a good (lossless) compression algorithm, then the frequencies will be close to uniform. In the compressed version, each byte contains more information about the document than in the uncompressed version. That's how you're able to convey the same information in fewer bytes. The increased information per byte is reflected in the greater entropy of the uniform distribution, compared to the original uncompressed probability distribution.

$\endgroup$
  • 3
    $\begingroup$ Due to Shannon's theorem, one can make this measure of information content precise: the entropy of a distribution is the expected amount of information you need to transmit in order to tell someone (who knows the distribution and your encoding scheme) a sample from the distribution. This is often a very useful perspective; in particular if you believe your distribution should be close to a product of independent uniform random variables, finding an efficient coding scheme and looking at entropy can often prove this (in a crude form that most of the distributions are close to uniform indept). $\endgroup$ – user36212 May 22 '19 at 9:28
22
$\begingroup$

The explanation of entropy as information content in Shannon's original paper is quite good. On page 10 of A Mathematical Theory of Communication (1948), you can find the following passage:

Page 10 from Shannon's theory of communication

In the following pages, the author points out that such a function is uniquely given by $-\sum p_i \log p_i$ up to rescaling, names the function "entropy", mentions that the very same function appears as entropy in some existing treatments of statistical mechanics, and describes some of its useful properties. There is a very nice discussion of information density of written language, e.g., the existence of crossword puzzles is an indication that English words have relatively low redundancy.

One example of a situation where entropy is considered is in the study of black hole thermodynamics. In this case, one considers states given by a quantum-mechanical density matrix $\rho$, and the von Neumann entropy is defined as $-\text{Tr}(\rho \log \rho)$. Diagonalizing the density matrix produces Shannon's entropy formula. Beckenstein and Hawking showed that, under some simplifying assumptions, the entropy of a black hole is proportional to its surface area. Since black holes reveal essentially no information to outsiders, one can say that the information content (in this case, a choice of internal state among all possible states that look the same from outside) depends only on the surface area. Some people looking for a quantum theory of gravity interpret this as evidence for a holographic principle, i.e., the claim that in our universe, the information contained in any region is encoded somehow in the boundary of that region.

$\endgroup$
  • 1
    $\begingroup$ The last paragraph seems pretty arbitrary. Entropy is omnipresent in physics, simply because of statistics of many particles. What can be surprising in the black hole case, and you forgot to mention, is that according to general theory of relativity, black holes have no degrees of freedom and their entropy should equal zero (black holes have no hair). Of course, this is simply because we did not take quantum effects into account -- microscopically black holes must still be built out of some elementary parts -> therefore they do have entropy (whether proportional to area or not). $\endgroup$ – Marek Nov 1 '13 at 14:59
  • 2
    $\begingroup$ @Marek : The entropy of a black holes is not zero. Instead it is much greater than the entropy of the star that collapsed to the black hole. $\endgroup$ – jjcale Nov 1 '13 at 18:20
  • 2
    $\begingroup$ @jjcale: in reality, the total entropy always increases, of course. But I was explicitly mentioning just classical GTR. There we have en.wikipedia.org/wiki/No-hair_theorem $\endgroup$ – Marek Nov 1 '13 at 19:59
  • $\begingroup$ @Marek My last paragraph was a response to the part of the question that asked: `What I am looking for is a few examples where the term "entropy" is used to describe some mathematical object/quantity and its meaning there.' I agree that my treatment is far from thorough. $\endgroup$ – S. Carnahan Nov 1 '13 at 23:51
12
$\begingroup$

The physicist Edwin T. Jaynes wrote a lot about entropy and its uses in physics and probability theory:

http://bayes.wustl.edu/etj/node1.html some published works

http://bayes.wustl.edu/etj/node2.html some unpublished works

He insisted that the two are very much related. In one of his works he says he had a conversation with Eugene Wigner in the 1950s in which he told Wigner that physical entropy is a measure of information and Wigner thought that was absurd, because the information one person possesses differs from that of another, whereas entropy can be measured with thermometers and calorimeters. Jaynes says he didn't know at the time how to explain to Wigner why that was wrong, but figured it out much later. As nearly as I understand it at this moment, Jaynes thought entropy measures the amount of information delivered by those thermometers and calorimeters.

Jaynes has a sort of cult following, many members of which are professors in the physical sciences who learned everything they know about probability from Jaynes, and they can sometimes come across a bit like religious fanatics.

OK, a short answer: The entropy in a discrete probability distribution is $\displaystyle\sum_k -p_k\log p_k$, where $\{p_k\}$ are the probabilities assigned to atoms in the probability space. The base of the logarithm can be any number $>1$ (or maybe $<1$ in some cases? I haven't thought about that.). There's also relative entropy of one probablity measure $p$ with respect to another, $q$, given by $\displaystyle\sum_k p_k\log(p_k/q_k)$ and cross entropy given by $\displaystyle\sum_k -p_k\log q_k$.

Via Google, you might be able to find notes taken by scribes in Gian-Carlo Rota's probability course at MIT. Somewhere among those, he says the resemblance between entropy of discrete probability distributions (as defined above) and entropy of continuous distributions (done similarly with integrals.) is only superficial. These observations are explored for finite discrete distributions in Section 1.4 of the book "Combinatorics The Rota Way" by Kung, Rota, and Yan. Deeper relationships are speculated upon in Rota's article "Twelve problems in probability no one likes to bring up" in the book Algebraic Combinatorics and Computer Science, Crapo and Senato eds. Those speculations are in the section entitled "Problem 4: entropy."

$\endgroup$
  • 1
    $\begingroup$ Thank you Michael for your explanation. I also found the historical comments interesting. $\endgroup$ – Mustafa Said Nov 1 '13 at 10:16
  • 3
    $\begingroup$ There are physical experiments which demonstrate that Jaynes was right. One involve mixing polymers in a particular sequence, so that they can only be unmixed given a secret key. Another key insight of Jaynes is that entropy is subjective, it's not a measure of a system, it's a measure of the ignorance of an observer about the system. $\endgroup$ – Arthur B Nov 1 '13 at 13:39
  • 1
    $\begingroup$ @ArthurB Do you have a reference for that? I would be very interested in that. $\endgroup$ – jonalm Nov 19 '13 at 0:50
  • 2
    $\begingroup$ @ArthurB : I wonder if calling it "subjective" misses Jaynes's point. Informatoin delivered by thermometers and calorimiters is not subjective. Being a measure of information, and thus of how much information is missing, is not the same as saying it's subjective. $\endgroup$ – Michael Hardy Nov 13 '16 at 17:10
7
$\begingroup$

Entropy is the negative KL divergence of a probability distribution $p$ from a uniform distribution $\lambda$, $H(p) = -D_{KL}(p\parallel\lambda)$. Thus if you have an intuition for the KL divergence then you have an intuition for entropy.

To that end, suppose you draw a large sequence of measurements from a true distribution $p$ and want to see how likely it is that a model distribution $q$ would generate the same histogram counts. The KL divergence is the negative log average likelihood of observing the histogram you got supposing that it was generated by $q$ instead of $p$.

See, http://www.snl.salk.edu/~shlens/kl.pdf

In the entropy case $q$ is uniform, so the entropy measures how likely it is that draws from your distribution could have been generated from a uniform distribution.

$\endgroup$
  • $\begingroup$ And minus the Shannon entropy is the convex generator of the KL divergence, this latter seen as a particular case of Bregman divergence. $\endgroup$ – Avitus Nov 9 '14 at 21:58
  • $\begingroup$ @Nick Alger What type of variables are you discussing? By type I mean discrete or something more general? I'm concerned that if this definition were permitted to describe any type of probability distribution then it might violate the intuitions about entropy described in the other answers. $\endgroup$ – cantorhead Mar 21 '16 at 20:49
  • $\begingroup$ That's a bit of a circular argument, since the KL divergence is defined that way, not the other way round. $\endgroup$ – nbubis Dec 4 '18 at 14:16
5
$\begingroup$

Entropy is a measure of disorder of a configuration. Its converse is information, which is a measure of order. Information theory seeks to understand the influences of different parts of a system on one another by comparing their entropies, or conversely by comparing their informations. One of the goals of information theory is to estimate the likelihood that one event caused another. Transfer entropy, and the closely related Granger Causality, is a tool for doing this.

First, relative entropy. Consider a pair of configutations $A$ and $B$, each with its own entropy. Assume that we know that $B$ is a controlled modification of $A$. Relative entropy, that is the entropy of $A$ minus the entropy of $B$, measures the amount of information added in the transition from $A$ to $B$.

Next, assume that both configurations, $A$ and $B$, are indexed by parameter which gives directionality (e.g. time). To measure the influence of $A$ on $B$, take the difference between the entropy of $B_t$ given its past (that is $B_{t-1}$) and the entropy of $B_t$ given both $B_{t-1}$ and $A_{t-1}$. That difference is the transfer entropy. So if the entropy of $B$ goes down "after the intervention of $A$", then we assume that $A$ causes $B$, and the magnitude of the transfer entropy estimates the likelihood of this causal relationship.

Of course correlation does not imply causation, and strictly interpreted Granger Causality suffers from the post hoc propter hoc logical fallacy. This does not prevent it from being useful.

Edit: Avishy Carmi comments by e-mail:

There is a slight detail to add which ensures the relative entropy is always non-negative.
The relative entropy is not the mere difference of entropies of $A$ and $B$ but rather the difference between the cross entropy $H_{AB}$ and the entropy of $A$, namely $H_{AB} - H_A$. The notion of cross entropy roughly quantifies the amount of disorder in $B$ when described in the "language" or coding scheme of $A$. It is always greater than $H_A$ which, using the same analogy, can be viewed as the disorder in $A$ described in the language of $A$. That is, some information is lost due to incompatibility of a configuration ($B$) and the coding scheme used to describe it (say of $A$).
$\endgroup$
  • $\begingroup$ could you define a "configuration"? $\endgroup$ – cantorhead Mar 21 '16 at 20:34
  • $\begingroup$ @cantorhead A probability distribution. $\endgroup$ – Daniel Moskovich Mar 21 '16 at 21:17
  • $\begingroup$ Okay. Then are you just talking about discrete distributions or all probability distributions? $\endgroup$ – cantorhead Mar 21 '16 at 21:22
5
$\begingroup$

The possible definition of the entropy can be done through the enumeration of permutations.

Let's consider the set of $N$ balls, where $N_i$ is a total amount of the balls of the $i$-th colour. The total amount of unique permutations can be described by the Multinomial Coefficient: $W = {N! \over \prod{N_i!}}$.

All permutations can be enumerated and assigned with a number from 0 to (W - 1). Hence, the string of $\log_2(W)$ bits can be used to encode each permutation. Let's consider the amount of bits per item of the permutation: $S = {\log_2(W) \over N}$.

The more uniform set is (the more balls of same colour are there) - the smaller $S$ is, and vice-versa: the less uniform set is - the higher amount of bits per item of the permutation is needed.

Below provided the brief logic of transformation from this idea to the Shannon entropy.

Let's assume that amount of items is sufficiently large, so we can make use of the Stirling's approximation: $\ln(N!) = N \cdot \ln(N) - N + O(\ln N) \approx N \cdot \ln(N) - N$.

Hence, we can rewrite $S$ as:

$S = {1 \over N} \cdot \left( \log_2(N!) - \log_2(\prod N_i!) \right) \approx$

$ \approx k \cdot {1 \over N} \cdot \left( N \cdot \ln(N) - N - \left(\sum N_i \cdot \ln(N_i) \right) + \sum N_i \right)$

where $k$ - is the transformation coefficient to the natural logarithms.

Taking into account, that $N = \sum N_i$ we can make the further transformations:

$S \approx k \cdot {1 \over N} \cdot \left( (\sum N_i) \cdot \ln(N) - \left(\sum{N_i \cdot \ln(N_i)}\right) \right) =$

$= - k \cdot {1 \over N} \cdot \sum N_i \cdot \ln {Ni \over N} =$

$= -\sum {N_i \over N} \cdot \log_2{Ni \over N}$

As far as the total amount of balls in a set is $N$ and the amount of balls of $i$-th colour is $N_i$ - the probability of selection of the ball with $i$-th colour is: $p_i = {N_i \over N}$

Hence, the entropy can be expressed as: $S = -\sum p_i \cdot \log_2 p_i$

The more tidy derivation could also show that the Shannon entropy is an upper bound of the ${\log_2 W \over N}$, hence its value will be always slightly greater than the value of the latter.

$\endgroup$
  • 3
    $\begingroup$ That is essentially Wallis's derivation of the principle of maximum entropy, as recalled in (more) physical terms in Section 11.4, pp. 351-354 of Jaynes's book Probability - The Logic of Science and also in en.wikipedia.org/wiki/… - a very useful remark you made is that the particular function $\frac{\log_2 W}{N}$ of $W$ is the bit word length per item of the permutation. In both references above, this choice seems arbitrary - any monotone increasing function of $W$ would do. $\endgroup$ – Pedro Lauridsen Ribeiro Nov 13 '16 at 4:33
  • $\begingroup$ Similar stuff can also be seen in the textbook Thermal Physics by Kittel and Kroemer. $\endgroup$ – JP McCarthy Sep 13 '19 at 7:54
  • $\begingroup$ Thanks for the references! In my case I have learnt about this interpretation from the exam-preparation notes to the course "Data presentation and compression", taught by Kovalev Dmitry Sergeyevich (in Novosibirsk State University), which I have found here: github.com/dmitriykovalev/nsu.videosoft.org/blob/master/assets/… (in Russian language). $\endgroup$ – stemm Sep 15 '19 at 17:33
3
$\begingroup$

In dynamical systems, there are two major entropies used, topological and metric. They each quantify, in technically different ways, how complexity of orbits grows as their length is allowed to grow into infinity. To make things slightly more precise, topological entropy measures the number of orbits that can be distinguished if we measured the position of points up to a fixed resolutions, and then let the resolution get finer and finer, and orbit length get longer and longer. A fairly good, not-so-technical introduction to both topological and metric entropies was given by Lai Sang-Young in Entropy in dynamical systems, available here: http://cims.nyu.edu/~lsy/papers/entropy.pdf

$\endgroup$
3
$\begingroup$

If you want to forgett about physical implications / motivations for a second, then you could consider the fact that the Shannon entropy $f(x):=x\ln \frac{1}{x}+(1-x)\ln\frac{1}{1-x}$ is the unique continuous solution of the fundamental equation of information (FEI) $$f(x)+(1-x)f\left(\frac{y}{1-x}\right)=f(y)+(1-y)f\left(\frac{x}{1-y}\right) ~~(*)$$ on $D:=\{(x,y)~|~ x\in [0,1), y\in[0,1), x+y\leq 1\}$. This latter is motivated by quite natural axioms that certain functionals-called information-on a given probability space must satisfy. In other words, the entropy can be defined as the (unique) solution of a functional equation much like the dilogarithm and many other important functions in Mathematics. It can be also seen as the convex generator (up to a sign) of the KL divergence, which plays an important role in information geometry and machine learning.

$\endgroup$
  • $\begingroup$ Does this approach extend to continuous, mixture, or singular variables? I'm interpreting the example shown as for the discrete two-state variable with probabilities $\{x,1-x\}$. $\endgroup$ – cantorhead Mar 21 '16 at 20:54
2
$\begingroup$

Shannon showed that entropy is an natural and useful quantity in information theory. To learn more about this, I recommend the book Elements of Information Theory by Cover and Thomas.

$\endgroup$
  • 5
    $\begingroup$ Actually, Shannon's original paper is quite a masterpiece of exposition. $\endgroup$ – Igor Rivin Oct 31 '13 at 1:17
  • $\begingroup$ actually von Neumann's entropy came before Shannon's but ... :-) $\endgroup$ – Suvrit Oct 31 '13 at 2:08
  • 32
    $\begingroup$ And von Neumann's explanation to Shannon for why he (Shannon) should call his new information-theoretic quantity entropy is amusing. Taken from en.wikipedia.org/wiki/History_of_entropy: "You should call it entropy, for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, nobody knows what entropy really is, so in a debate you will always have the advantage." $\endgroup$ – KConrad Oct 31 '13 at 3:03
  • 1
    $\begingroup$ I remember reading that awesome quote from von Neumann! $\endgroup$ – Suvrit Oct 31 '13 at 19:53
  • $\begingroup$ This is not an answer, would have been better as a comment. $\endgroup$ – Ben Crowell Nov 12 '16 at 22:56
1
$\begingroup$

There are a number of definitions of entropy floating around that are analogous even if they aren't equivalent. For any outsider they should look and feel nearly the same, for an expert you may be incline to choose one over the other.

  • information entropy
  • statistical entropy
  • topological entropy

Exciting new variants in theoretical physics

  • quantum entropy
  • renyi entropy
  • holographic entanglement entropy [1]
  • information cohomology [2]

Please excuse my over-simplified treatment. Also people are still thinking about what entropy to this day. Please also In Search of a Structure, Part I: On Entropy (Gromov, 2012)


Boltzmann defined "entropy" as the number of microstates of a thermodynamic ensemble. And his example is the asymptotics of the multinomial distribution.

A If $m = p\, n$ the binomial coefficients grow as the entropy: $$ \binom{n}{m} = e^{p \log p + (1-p) \log (1-p)} = \mathrm{exp}\, h(X) $$ where $X$ is the random variable which is $X=1$ with probability $p$ and $X=0$ with probability $1-p$.

B What about just the map $T: x \mapsto 2x \mod 1$ on $[0,1]$. How many does a typical point $x$ have?

$$ 2^n x \equiv a \mod 1 $$ This has $2^n$ solutions, so the entropy is $\frac{1}{n}\log |T^{-n}(x)| = \log 2$.


These are the two basic kinds of entropy (probabilistic, topological) and other definitions clarify this.

See also: Information Theory and Statistical Mechanics (Jaynes)

$\endgroup$
  • 4
    $\begingroup$ Boltzmann defined "entropy" as the number of microstates of a thermodynamic ensemble. Don't you mean the log of that quantity? $\endgroup$ – Ben Crowell Nov 12 '16 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.