Information, Entropy and a Demon

The Bit and the Molecule: A Journey Through Entropy

Why a coin flip has an appetite for bits

Flip a coin once. You’ll get heads or tails: one bit of information, which can be encoded as 0 or 1. Now, flip a biased coin, one that lands heads 80% of the time. Something strange happens. Each flip still gives you one symbol, but that symbol carries less surprise than a fair coin's flip would. You already expected heads. The rare tails, when it shows up, tells you something interesting that you didn’t expect.

The insight of Claude Shannon (after whom the AI was named) was to make this feeling precise. Defining the self-information of an outcome with probability $p$ as

A completely certain outcome ($p=1$) carries zero information. A rare outcome carries a lot. The average amount of information you get per symbol, across the whole distribution, is the entropy:

For our biased coin with $P\left(\text{heads}\right)=0.8$:

Entropy describes the “average number of bits required per symbol”. But how can a single coin flip need only 0.7219 bits to describe, when a bit is supposed to be the atomic, indivisible unit of information? You can’t send three quarters of a bit down a wire!

Fractional bits are a rate, not a size

No scheme can encode a single flip of our biased coin in less than one bit. Two symbols, heads or tails, need two distinct codewords, and the shortest possible codewords for two symbols are one bit each. Entropy of 0.7219 is not telling you that one flip needs 0.7219 bits. It is telling you the long run average, achievable only once you stop encoding flips one at a time and start encoding them in blocks.

Let’s take three flips together. There are eight possible sequences, but they are wildly unequal in probability. HHH happens with probability ${0.8}^{3}=0.512$, while TTT happens with probability ${0.2}^{3}=0.008$, sixty four times rarer. If you hand out short codewords to likely sequences and long codewords to rare ones, using the Huffman algorithm, for example, you get a code like this:

The expected number of bits spent per block of three flips is

which comes out to $2.184/3\approx 0.728$ bits per flip. This is already much better than the naive one bit per flip, and already quite close to the theoretical floor of 0.7219. Increasing the block size further closes the gap with the theoretical minimum. This convergence, is what the entropy formula actually predicts, and it is stated rigorously by Shannon's source coding theorem:

where $L\left(n\right)$ is the expected code length for optimally encoding blocks of $n$ symbols. The gap between what you achieve and the theoretical minimum shrinks no slower than $1/n$. Double your block size, and you roughly halve your wasted bits. Try it yourself in the block size slider above: watch bits per flip descend toward the dashed line at 0.7219, occasionally wobbling as it goes, since integer codeword lengths cannot follow the theoretical curve with perfect smoothness at every $n$, only in the limit.

What we can understand is that entropy is the rate, in bits per symbol, that becomes achievable only once you are willing to encode many symbols jointly, in the limit of arbitrarily long sequences.

From bits to molecules: the same equation wearing a different coat

In statistical mechanics, developed by Ludwig Boltzmann, entropy is derived from observing a macrostate – which is a general property of a system, like its temperature, for example, and considering how many microstates correspond to it. A microstate is a certain arrangement of the positions and velocities of each particle in a system. The basic idea is that entropy increases as the number of microstates for a given macrostate does. Calling that number of configurations $\Omega$, we can say that entropy is:

where ${k}_{B}$ is Boltzmann's constant. Comparing this with the entropy of a uniform distribution over $\Omega$ equally likely microstates, using Shannon's own formula:

These are the same expression! Converting the logarithm base and folding in the physical constant, $S={k}_{B}\text{ln}(2)\cdot H$. This is not a loose analogy or a poetic parallel. It is a mathematical identity between two formulas built from the same three axioms, the grouping property in particular, applied once to blocks of coin flips and once to arrangements of gas molecules. Boltzmann's entropy is Shannon's entropy, computed over the distribution of microstates consistent with what you know about a system, and scaled to carry units of joules per kelvin instead of bits.

This identity has a striking consequence. Entropy, in physics as much as in information theory, is not a property of "how messy" a system looks. It is a measure of an observer's ignorance about which exact microstate the system is in, given only a coarse, macroscopic description. A neatly stacked deck of cards has one arrangement consistent with "sorted," so it carries almost no uncertainty and almost no entropy. A shuffled deck has $52!$ arrangements consistent with "shuffled," so it carries enormous uncertainty and high entropy. "Disorder" is simply what a state with very high multiplicity, and therefore very high ignorance, tends to look like to a human eye. It is a convenient visual proxy, not the actual quantity being measured.

Maxwell's demon, and the bill it can't avoid paying

Now for a puzzle. The only law in physics determining that time should go forwards is the Second Law of thermodynamics, which states that the total entropy of the universe must increase over time: dS > 0. But violating this law opens up a whole can of worms and leads to plenty of fundamental questions. Would it mean that time isn't necessarily unidirectional, or does time even exist at all? James Clerk Maxwell came up with a thought experiment to investigate a possible, laws-of-physics-defying scenario.

Imagine a box of gas at uniform temperature, split by a wall with a tiny door. A demon watches molecules approach the door and lets fast ones through to one side only, slow ones through to the other. Given enough time, the demon sorts the gas into a hot half and a cold half, decreasing the gas's thermodynamic entropy over time (while also not increasing the entropy of surroundings) without doing any work, which appears to be a violation of the Second Law!

The resolution, worked out fully by Rolf Landauer and Charles Bennett, rests entirely on the identity between physical and informational entropy established above. Watching a molecule and deciding fast or slow is a measurement, and measurement alone, if the demon's memory simply accumulates fresh correlations without ever being reused, can in principle be done reversibly, at no thermodynamic cost. The trouble starts when the demon's memory is finite, which any physically buildable demon's memory must be. To keep operating, the demon must eventually erase old measurements to make room for new ones.

Erasure is fundamentally different from measurement. Resetting a memory cell to a fixed state, "0," regardless of whether it previously held a 0 or a 1, is a many to one operation. Given the final state, you cannot recover what the input was. This logical irreversibility has a physical price, known as Landauer's bound:

per bit erased, dissipated as heat into the surrounding environment. Picture the memory bit as a particle able to sit in either of two wells, left representing 0, right representing 1. Before erasure, both wells are accessible, giving $\Omega=2$ and entropy ${k}_{B}\text{ln}(2)$. Erasure forces the particle into one specific well regardless of where it started, shrinking $\Omega$ down to 1 and the memory's own entropy down to zero. Since the total entropy of memory plus environment cannot decrease, by the second law, the ${k}_{B}\text{ln}(2)$ that vanished from the memory must reappear as heat dissipated into the environment, at a cost of at least ${k}_{B}T\text{ln}(2)$ joules.

Every bit the demon measures and later erases costs at least this much heat. Tally up the full books: the gas's entropy goes down through sorting, but the demon's memory erasure generates at least as much entropy elsewhere, and typically more. The second law survives, once you account for the full physical system, demon included, rather than just the gas in isolation.

Reading the equation two ways at once

It is worth pausing on just how tight this connection really is, because it is easy to read past it as a metaphor when it is really an equality.

The demon's uncertainty about a single molecule's speed, before measuring it, is exactly Shannon's $H\left(p\right)$, the same formula used for the biased coin, with $p$ now standing for the probability a molecule counts as "fast." Measuring the molecule collapses that uncertainty, storing one bit's worth of correlation in the demon's memory. Erasing that memory later costs ${k}_{B}T\text{ln}(2)$ of physical entropy, dumped as heat, per bit stored. The conversion factor between a bit of Shannon entropy and a joule per kelvin of thermodynamic entropy is not an approximation or a rule of thumb. It is ${k}_{B}\text{ln}(2)$, exactly, the same constant that appears when you convert the freely chosen constant $K$ in Shannon's original uniqueness proof into a fixed, physically measured value.

So the full chain reads: a molecule's speed is uncertain, exactly as a coin flip is uncertain, quantified by the same $H\left(p\right)$. Measuring it stores that uncertainty as a correlation in physical memory, at no cost if done reversibly. Reusing that memory, which any finite demon eventually must do, requires erasing the correlation, which is logically irreversible and therefore has an unavoidable thermodynamic price, fixed by Boltzmann's constant and the very same logarithm that defines Shannon's bits. Two branches of physics, one born from telegraph engineering and one from steam engines, turn out to be talking about the same underlying quantity all along.

What this buys you

The clarity we get from taking this connection seriously is that ignorance, not mess, is the right word to reach for whenever entropy comes up. A gas spread evenly across a room is not "more disordered" than a gas crammed in one corner in any fundamental sense. It is a macrostate consistent with vastly more microstates, meaning an observer who only knows the macroscopic description is vastly more ignorant about the exact configuration. The same logic explains why a maximally spread out probability distribution, like a fair coin or a gas at equilibrium, always carries the largest entropy among all distributions with the same constraints: it is the distribution that assumes the least, the one that adds no information beyond what you actually know.

From a biased coin's fractional bits, to the crowd of molecules bouncing inside a box, to a demon's memory forced to pay a thermodynamic toll, one formula keeps reappearing, because one idea keeps reappearing underneath it: entropy measures what you do not know.