Entropy is a big topic, both in science and in the popular gestalt. I wrote about it in one of my very first blog posts here, back in 2011. I’ve written about it a number of other times since. Yet, despite mentioning it in posts and comments, I’ve never laid out the CD collection analogy from that 2011 post in full detail.
Recent discussions suggest I should. When I mentioned entropy in a post most recently, I made the observation that its definition has itself suffered entropy. It has become more diffuse. There are many views of what entropy means, and some, I feel, get away from the fundamentals.
The CD collection analogy, though, focuses on only the fundamentals.
In fact, those who already have a defining view of entropy can find it confusing because it’s such a simplified abstraction. Hopefully it works better for those unfamiliar with the concept — they (you? hello!) are the intended audience.
The CD collection analogy has two goals: It seeks to illustrate the formula Boltzmann devised for quantifying entropy. It also seeks to explain why entropy is often explained as “disorder.” Some disdain disorder as a description, but I think seen through analogies like this it makes more sense.
I’ll start by quoting myself from a post last year:
Entropy defines differently depending on the domain. In communications (information theory), it focuses on errors in data. In computer science, it can refer to randomness for cryptography.
Those are specialized views. The most general English-based definition is that entropy is a measure of disorder. This definition is so general it drives most physicists a little crazy (because: define “disorder” … and “measure”).
A more precise English-based definition is more opaque: Entropy is the number of indistinguishable micro-states consistent with the observed macro-states.
That last one is the (non-mathematical) definition. It’s the most accurate and fundamental way to state what entropy is as expressed in Boltzmann’s formula:
Where S is the entropy, K is a constant (Boltzmann’s constant), and Ω (Omega) is the number of micro-states grouped as “indistinguishable” under some set of (view-defined) macro-states.
This obviously requires both explaining and applying to examples. (Analogies such as the CD collection try to do the former.)
Everything centers on the dual notions of macro-states and micro-states. In Boltzmann’s formula, the latter is explicit in the quantity Omega. The former is implicit in a given value of Omega.
From that same post:
A macro-state is a property we can measure in a system. A macro-state is an overall property of the whole system, such as its temperature, pressure, or color. In the example of the CD collection, how well it’s sorted is a property of the whole collection.
A micro-state is a property of a piece of the system — usually, as the name implies, a small, even tiny, piece. The molecules of a gas or liquid all have individual properties, such as location and energy…
We say that micro-states are indistinguishable when different arrangements of micro-states have no effect on a given macro-state.
The micro-states of a system are usually obvious. They’re the smallest meaningful building blocks comprising the system. The granularity depends on the system. A quantum system has quantum micro-states, but in a gas system the micro-states involve gas molecules. (In information systems, the micro-states involve bits.)
The macro-states are not obvious, in part because they depend on what properties of the overall system interest us. The gas system has temperature and pressure macro-states as well as macro states involving the arrangements of its molecules. Macro-states depend on how we choose to view the system as a whole.
Macro-states are also complicated because of partitioning. Many systems are continuous, so their behavior at a macro-level must be partitioned into groups. For instance, temperature is measured in degrees (or down to some fractions of degrees), but that temperature number includes all the temperatures closer to that number than the next. So how we partition macro-states affects Omega.
However, given we’ve finally defined the macro-state, Omega is the number of permutations of the micro-states that result in that same macro-state. The entropy behavior (or curve) of a given system is the set of Omega values for all its macro-states. In real systems, Omega easily becomes astronomically astronomical (hence using the log of Omega to tame it a bit).
For instance, the vast number of possible arrangements of air molecules in a room that result in the same temperature or pressure. That number is the factorial of number of molecules. It’s big beyond our sensibility.
With those definitions and observations, let’s get to the CD collection analogy. The name announces the basic image: a collection of CDs. We’ll imagine it’s a very large collection — at least 5,000.
A key point here is that the CD collection is a concrete image of the abstract idea of an ordered set. Brian Greene uses the pages of the novel War and Peace to illustrate the same thing in his book The Fabric of the Cosmos. A box of index cards with serial numbers on them is another example. So is a library of books sorted by Dewey Decimal number.
In all cases, we care about two things: That each member of the collection has a property that uniquely identifies it. And that property must allow the collection to be perfectly sorted. (In essence, it is always true that either a<b or a>b.) Our entropy abstraction can use any collection with such a property.
Crucially, exactly how the CD collection is ordered doesn’t matter. It could be date purchased; order added to collection; ISBN number; or some code number we randomly assign. A more natural order might be by Artist, Release Date, and Title, but it could be anything. All that matters is that we have a definition that allows a perfect sort.
I said the micro-states of a system are obvious, and here — in the context of a sorted collection — they’re obviously the positions of each CD. The information in micro-states generally comprises a full description of the system. In the context of an ordered collection, the positions of each CD do comprise a full description of the collection.
The macro-states are a more complicated proposition, and it turns out that’s true on at least two levels. Firstly, for all the usual reasons, but here also for a reason I hadn’t anticipated.
I’ll refine this more as we go, but to start with a casual definition, the macro-state of the collection is “how sorted” the collection is. This, as with temperature and pressure, is a single value expressing an overall property of the system. It seems, however, four+ decades of computer science blinded me to a “how sorted” property being a foreign idea outside that realm.
I’ll unpack it below, but for now take it on faith the CD collection has a “how sorted” property — a single number that quantifies the degree to which the collection is sorted. We’ll call this the sort degree. For now, assume it exists and is our macro-state. Imagine we have a device that, as does a thermometer or pressure gauge, sums over the collection and returns a single number: temperature, pressure, or “how sorted.”
Given this (for now magical) macro-state, we can calculate Omega and, thus, the entropy of a given macro-state. Natural systems are extremely challenging, but the CD collection gives us some chance at actual quantification.
We can, for instance, easily quantify the zero-entropy state. Natural systems can’t have zero entropy, but abstractions can, and it makes a good first illustration of Boltzmann’s formula.
There is only one arrangement (permutation) of the CD collection that is perfectly sorted, and log(1)=0. We’ll define the sort degree here as zero, too, but don’t confuse sort degree with entropy. They just happen to both be zero in this case.
In fact, there are three numbers to keep straight: The sort degree, which is a macro-state quantifying “how sorted” the collection is; Omega, which is the number of micro-states matching a given sort degree; and the entropy, which is the log of Omega times a constant.
The next sort degree after zero is one, which means one CD out of place. In fact, the sort degree is defined as the minimum number of moves required to restore the collection to perfectly sorted. This usually tracks the number of CDs out of place.
The number of permutations with one CD out of place is: N×(N-1), where N is the number of CDs (because each of N CDs can misplaced in N-1 places).
If we have 5,000 CDs:
And that is just the first jump in entropy after zero. The numbers get much bigger as more and more CDs are out of order and the number of permutations rises.
Since Boltzmann’s constant is a constant, I’ll ignore it from now on (it just brings the actual value we get into better synch with thermodynamics). I’ll also mention here that we’re using the natural log function, not the base-10 or base-2 log.
Let’s get back to the question of macro-states and the “how sorted” property. One possibility is constructing the macro-states based on permutations. Unfortunately, that approach results in duplicates, confusion, and the end of the universe.
Consider a simple example given the ordered collection [ABCDEF]. Is the permutation [CDEFAB] four items out of place (CDEF) or two (AB)? Naively generating permutations based on X-many CDs misplaced results in patterns that should belong to other macro-states.
We could mitigate the problem by filtering out permutations that occur in lower sort degrees, but there’s a small problem. Or, rather, a big one. A really big one. The total number of permutations is N! — the factorial of N. For 5,000 CDs, that number has 16,326 digits. (It starts off: 4228577926…) There isn’t enough memory in the universe to store the permutations.
The punchline here is that it’s an NP-hard problem (read: currently effectively impossible) to accurately calculate sort degree from a random permutation. The “accurately” is important. It’s always possible to come up with a sort degree by just sorting the permutation and counting the moves, but it’s NP-hard to find the minimum one.
For our abstraction we declare a magic measuring “thermometer” that scans the collection and returns that accurate (minimum) sort degree.
There are ways to track the sort degree over time, but that gets into indexes, which I think is worth a separate post. There is also the matter of how the CD collection evolves — what makes its entropy go up or down.
All that and more next time.
Note that I haven’t so far said a single word about energy or work. That’s because entropy is a more abstract concept than its application in thermodynamics (even though it sprang from there). Physical systems using energy and doing work are applications for which entropy can be a useful measure (or at least a useful concept).
Stay entropic, my friends! Go forth and spread beauty and light.