The Entropy of A Markov Chain

A more explicit example

Clausius (1865)¹ defines a quantity called entropy. By decomposing physical processes as a chain of engines, he shows that entropy always increases for irreversible processes. For reversible processes like Carnot's ideal engine, the change in entropy is zero. But when an irreversible process occurs, entropy can never decrease unless energy is applied to a system. This is what is known as the second law of thermodynamics.

And whilst entropy itself may not be measurable with a thermometer or ruler, it is still a useful concept since we can calculate derived quantities from it that are directly measurable.

I've written previously quite vaguely about 'life as entropy'. This was an idea motivated by Schrödinger (1944)² through the concept of negentropy. Through negentropy, life seems to maintain order by feeding on the energy around it, and reducing its local disorder. But up until now, I've been confused about what this actually means in detail.

And so one way I'm trying to understand this is through models. One approach might be to make toy models and then figure out a mathematically consistent way to define entropy in those systems. Then, you could simulate the model and have a better idea of how the entropy evolves.

One such toy model that is useful to get an intuition is Dyson's toy model of a cell. Dyson's toy model of a cell is a Markov chain that settles into one of three equilibrium states, two of which are the 'life' and 'death' states. But if we care about the vague concept of 'life as entropy', then we should be able to make a definition of entropy to apply to the Markov chain.

But the concept of entropy as originally defined by Clausius was a function of work and temperature

\(\mathrm{d}S \;=\; \frac{\delta Q_{\text{rev}}}{T}\)

And so it is unclear how to relate the two ideas together. Is there a different way to define entropy in the context of Markov chains that gives you the same result, consistent with physical ideas?

Well, one way to attack this is by looking at the work of Boltzmann, who quantified the relationship between entropy and the number of possible states in a system.

Suppose you take a system and then observe a system's state variables, like temperature, pressure and volume, using various instruments. Presumably, there are a number of different configurations of the physical system that are compatible with it being in that state. And if entropy is related to the concept of order and disorder, then presumably entropy would be higher if there were more possible states.

Here is a vague example. If you have a gas of identical molecules at absolute zero, fixed in position, with each at zero velocity at zero temperature, you have fewer possibilities for what the system could be for the gas to be in that state. Whereas if we had a heated gas at a hot temperature, there are many configurations that a state might be in as a result.

Temperature is higher, entropy is higher. Is it any coincidence that the number of possible states increases too?

It turns out there is a way to make these ideas rigorous. Boltzmann showed that entropy can be written as a function of the number of states that a system can be in, if we fixed what the macro state variables were. That means if we could count all the states that were possible in a system at fixed temperature, pressure and volume, then we could calculate the entropy.

This is written in the legendary equation below, which is also surprisingly simple — that the entropy of a system is the logarithm of the number of states, multiplied by a fixed constant called the Boltzmann constant.

\(S \;=\; k_B \ln W, \qquad W \;=\; \#\{\text{microstates consistent with the macrostate}\}\)

Whilst the result is simple it's completely non-obvious. Boltzmann creates a model of gas where each particle only can be in a set of finite velocities and positions and then tries to take the limit. The proof is not easy and mathematicians are still figuring out how to properly rigourise the work of Boltzmann.

But anyway!

To make this example even more concrete, let's try to compute the entropy of a basic system, given we know what the energy (macrostate) is. Consider Curie's model of a magnet. In this model, our physical space consists of a finite number of electrons, which can either be spin up or spin down. In models of magnets, energy (or work) is done when the spins are misaligned with the direction of the magnetic field that the metal is placed in.

And so this suggests that if we had a collection of atoms, the energy is a function of how many atoms are aligned with spin up vs spin down.

\(E \;=\; n_\uparrow - n_\downarrow\)

Ok, so suppose we had a very, very small system of 5 atoms. And suppose that we measured the energy as E = 1. First, we need to figure out how many atoms need to be spin up and spin down to have this configuration. The obvious answer is three spin up and two spin down because

\(E \;=\; 3 - 2 \;=\; 1\)

We could also trivially solve this using the constraint that

n↑+n↓=5, so

\(E \;=\; 2n_\uparrow - 5\)

And the configurations we could have are the following. Each configuration has three up spins and two down spins, but you can arrange this in 10 ways. The diagram below lists all of the possibilities.

This is 5 choose 3 combinations, which is 10.

\(W \;=\; \binom{5}{3} \;=\; \frac{5!}{3!\,2!} \;=\; 10.\)

Those ten configurations are the entire content of the macrostate "E = 1".

This means that Boltzmann would label the entropy of the system as

\(S \;=\; k_B \ln W \;=\; k_B \ln 10 \;=\; 2.3026\,k_B,\)

or log₂ 10 = 3.32 bits. And so in this case we can see the entropy as a function of energy. If we plot out entropy as a function of the energies we get this graph:

So now we've learnt how to compute entropy from the total number of microstates that a system can have. Ok, so how do we count the entropy of a Markov chain process like in Dyson's cell model?

In Dyson’s toy model that we have N sites, and each site could be in one of three states — empty, active, or inactive. Given some rules, in my last post I showed that this converges to an equilibrium. The equilibrium values are a complicated function of fixed points, but they do exist, and the probability of being empty, inactive or active does converge to a fixed value.

This equilibrium point allows us to define the entropy of a Markov chain through a counting argument. Say we had an equilibrium case where we had a 1/2 chance that a state is empty, a 1/4 chance that a state is active, and a 1/4 chance that a state is inactive.

This means if we had 8 sites, then we would have 4 that were empty, 2 that were active, and 2 that were inactive. So to measure the entropy, we now need to count all of the configurations of this happening. This is shown below, with all of the arrangements.

Counting them is the multinomial coefficient — choose which 4 of the 8 sites are empty, then which 2 of the remaining 4 are active, and the last 2 are inactive. This can be calculated by taking the factorial of the number of spaces there are, and dividing it by the factorials of the number in each distinct state. So in this case, since we have 4 empty, 2 active and 2 inactive, we divide by 96.

\(W \;=\; \frac{8!}{4!\,2!\,2!} \;=\; \frac{40320}{24\cdot 2\cdot 2} \;=\; 420.\)

And so the entropy of this is the logarithm of the number of states multiplied by the Boltzmann constant.

\(S \;=\; k_B \ln W \;=\; k_B \ln 420 \;=\; 6.0403\,k_B.\)

The next natural question is how the entropy evolves in the system. It turns out we can make some cool general statements about entropy based on the topology of the graph, which I'll explain in a later post, and also write down the conditions for which entropy increases.

Thanks to David Pfau for discussions and help, all mistakes are mine.

References

¹ R. Clausius, Ueber verschiedene für die Anwendung bequeme Formen der Hauptgleichungen der mechanischen Wärmetheorie, Annalen der Physik 201(7), 353–400 (1865).

² E. Schrödinger, What is Life? The Physical Aspect of the Living Cell, Cambridge University Press (1944), ch. 6.