Give Me Money: Worked Solutions for the Boltzmann Game

Introduction¹: A Pedagogical Exercise

Consider the following situation (after Michalek and Hanson, 2006): we have $N \in \mathbb{Z}^+$ coins distributed among $M \in \mathbb{Z}^+$ victims students (where $N$ could, but need not, be some integer multiple of $M$). We begin with some initial pseudorandom allocation of coins (e.g. everyone has the same number of coins); then we redistribute the coins “randomly” — in this case, by playing rock-paper-scissors with the following rules:

1. Everyone pairs up
2. Everyone plays RPS at once (“scissors, paper, stone!”)
3. Winner takes a coin from loser unless loser has no coins
4. No tiebreaking
5. This is one round. At the start of the next rounds, new pairings should be formed that are either random, or entirely different from this round.

After every few rounds (say, every $M$ rounds), we ask everyone how many coins they have, and try constructing a histogram from this.

Q: What's going to happen to the series of histograms?
A: They will approach a geometric distribution.

This happens as if by magic, without any apparent external intervention². What's going on here? This little classroom activity is a Monte Carlo³ physical simulation in disguise. But what a simulation! and what a disguise!

Game of Numbers

How many ways are there to achieve a given distribution of coins? Suppose that we are given a list of numbers $\{m_0,m_1, m_2, \ldots m_N\}$ characterising such a distribution, such that there are $m_l$ people with $l$ coins each. For example, with $m_l = 0$ except $m_0 = M-1, m_N = 1$ (one person has all the money), there are obviously $M$ different people who can hang on to all the money, so the number of possible configurations $\Omega$ permitting this distribution is $M$.

With a little bit of work, we can show that the number of possible configurations $\Omega$ permitting any distribution is given, in the general case, by

subject to the additional constraints that

1. $\sum_l^N m_l = M$ (conservation of student), and
2. $\sum_l^N l m_l = N$ (conservation of coin).

Suppose that every configuration was equally likely (in the frequentist sense). Then if we were to randomly select a configuration, the most likely distribution would be the one permitted by the most configurations.

The point of the whole rock-paper-scissors exercise, then, is to redistribute coins in a random fashion (randomness here being introduced by uncertainty in the result of any given game of rock-paper-scissors). If we assume that all such games have equally uncertain events, then we can assure ourselves that it's quite likely we'll end up at this “most probable distribution”, irrespective of the actual identities of who possesses how much money.

Terminology time: let's go back to the example of one guy hanging on to all the money. This is one possible outcome of resource reallocation, and is called a “macrostate,” and corresponds to the functional properties of the physical system — to wit, the fact that one guy happens to have all the money. It doesn't matter who. But if I were the kind of person for whom this information did matter, there would be $M$ different ways to split (or not) the money such that only one person hung on to all of it. These are called “microstates”. There is only one microstate in which, for example, I in particular hang on to all the money.

The expression $\Omega$ then represents the number of microstates corresponding to a macrostate, which is characterised completely by the list of numbers $(m_0,m_1, m_2, \ldots, m_N)$. We can think of this as describing a point in $N+1$-dimensional space (or at least the subset of it that satisfies the above constraint equations.)

The premise in this mathematical game of numbers is that all microstates are equally likely — the most likely macrostate is then obviously the one with the most microstates that permit it. We call this an assumption of equal a priori probability.

Optimisation

Which macrostate is that? For very small $M$ and $N$, there's little that we can do except calculate $\Omega$ exhaustively on the entire configuration space. In the thermodynamic limit, however, there are a bunch of tricks that we can employ. By this, we mean in the limit as $M \to \infty, N \to \infty, \textrm{ and } m_l \to \infty$ (at least, for the important ones).

In this limit, the smallest possible increments in each of $m_l$ are so small compared to the $m_l$ themselves that we may as well approximate them as continuous variables. This allows us to use extremisation methods from multivariable calculus. Moreover, in the asymptotic limit we have $\log N! \sim N (\log N - 1)$ as $N \to \infty$; this is known as Stirling's Formula (the first few terms of the asymptotic series for the $\Gamma$ function).

One more piece of the problem: calculus is much easier when working with sums instead of products. Therefore instead of extremising $\Omega$, we will work instead with a quantity we shall call the Boltzmann entropy⁴ $S = \log \Omega$, thereby turning the product in the denominator into a sum.

Finally, we must remember that our extremal configuration must satisfy both constraints listed above. Thus, instead of extremising the entropy directly, we extremise an auxiliary function with additional variables per the method of Lagrange multipliers as

We extremise this by demanding that the partial derivatives vanish with respect to all $m_l$ as well as both $\alpha$ and $\beta$, yielding a system of $N+3$ equations; the latter two are just the constraints delineated above.

The first $N+1$ of these equations can be written as

This has the immediate implication, for example, that ${m_a \over m_b} = e^{-{\beta(a - b)}}$. This is a geometric distribution. Substituting this into the first constraint equation allows us to eliminate $\alpha$ by introducing a new variable $Z$ (which we call the partition function⁵) as

The second constraint is harder to enforce. However, we note that

In this case, since the expressions for $m_l$ are proportional to powers of $l$, we can sum $Z$ in the thermodynamic limit as $Z \sim {1 \over 1 - e^{-\beta}}, N \to \infty$, yielding an approximate value of $\beta \sim \log \left({1 + {M \over N}}\right)$.

Alright, so we have a formal solution to our numbers game in the limit of large numbers. What's the point of this?

Boltzmann vs. Gibbs

Let's look again at our expression for $m_l \over M$, this time from a frequentist perspective. In the continuum limit, we can treat this as the probability that a given person has $l$ coins (although in this limit the analogy starts to become a little less sensible — one has an infinite number of people with an infinite number of coins, and an infinite number of people with any given number of coins). Under this interpretation, the constraints take on a more fundamental meaning: the first constraint becomes a statement of the conservation of probability: that all probabilities add up to 1. This is seemingly quite trivial, but at the same time is rather important for consistency.

Motivated by this interpretation, we can rewrite our expression for the entropy as $S = - \sum_l p_l \log p_l$, where $p_l \sim {m_l \over M}$ is the probability that a person has $l$ coins, in this frequentist sense. This is called the Gibbs⁶ entropy formula, and potentially describes more interesting situations than just our little experiment with entropic Marxism.

Consider instead an infinitely large bunch (“ensemble”) of functionally identical physical systems, all of which exhibit identical behaviour, characterisable by macrostates indexed by $l$, distinguished only by the energy of each macrostate $E_l$. Suppose furthermore that energy can pass freely between these systems, such that the total energy is conserved. However, the total energy is also infinite, which is inconvenient for bookkeeping. We note, however, that conservation necessarily implies that the average energy $\left<E\right>$ remains constant. Suppose that randomly picking any physical system in this ensemble reveals it to be in the $l$^th macrostate with probability $p_l$. The constraint equations from above can then be rewritten in this context as

1. $\sum_l^N p_l = 1$ (conservation of probability), and
2. $\sum_l^N E_l p_l = \left<E\right>$ (conservation of energy).

Under these idealised assumptions, however, it can be shown⁷ that the Gibbs entropy increases monotonically over time: ${dS \over dt} \ge 0$. The values of $p_l$ that result describe the ensemble at thermodynamic equilibrium — once again, by constrained maximisation of the entropy! Note how subtly this argument differs from before. We had earlier argued that, with the coins, the equlibrium configuration arises because it is the most likely, and we quantified that likelihood with the entropy before extremising it. Here we merely invoke the fact that entropy only increases over time, and conclude that its maximum value must be its equilibrium value.

Also, an even more subtle difference arises: in our example with the coins, we defined the macrostates to be a property of the entire ensemble, made out of many systems (i.e. people), where the analogue of the energy (total monetary value) remains constant throughout. Here, the macrostates are a property of the systems within the ensemble. What's going on here?

Without loss of generality, the situation we have described is equivalent to the same ensemble in contact with a heat bath, such that the average energy of the set of all such system is fixed. What's going on here, then, is that we are allowing for situations where the average energy can change — manifesting in a change in the temperature of the heat bath. The Boltzmann Game with the coins is an example of the microcanonical ensemble — the variable $\beta$ was uniquely defined because $N$ — our analogue to the total energy — was fixed. If the average energy isn't fixed, neither is the temperature of the heat bath, and by extension, of the systems in this, the canonical ensemble.

There is another reason why we want this heat bath. In reality, it's quite hard to manufacture an infinitude of exactly the same physical system — more often than not, we only have one copy of the system. But without loss of generality, if the possible configurations of the system are known, then even if the energy contained in the system is not conserved, the (frequentist) probabilities — and other statistical quanties, like the average energy of the system — adhere to the values returned by analysing the corresponding canonical ensemble — as long as the heat bath of known temperature also remains. This is beyond useful! This is insightful.

In order for this to be true, however, we need to invoke the First and Zeroth Laws of Thermodynamics — and for that, we need to translate the idea of temperature into this formalism. From classical thermodyamics, we know that ${1 \over T} = {dS \over dE}$ — but (jiggling around the entropy formulae a bit) we find that this is exactly the expression for $\beta$! Thus, pursuing a computation analogous to that detailed above, we find that in such an ensemble the ratio of probabilities can be expressed (in physical units) as

where $k_B$ is Boltzmann's constant, and with additional proportionality factors to account for degeneracy. This is the Boltzmann distribution.

Notice, here, that at no point have we actually sought recourse to the true underlying mechanics of what kind of physical system we have in the ensemble. It doesn't matter! The Boltzmann distribution emerges anyway. It describes, well, a broad range of things: photons in lasers, cellular dynamics, planetary atmospheres, fusion in stars. It might even, quite plausibly, describe the vacuum or multiverses (we're not too sure about these, though). Such versatility, from such few initial considerations — such is statistical physics.

Conclusion

Through this article, we have moved rather swiftly over the statistical mechanics of the Boltzmann game, from the microcanonical to the canonical ensemble, from mathematics to physics. From here, we could head either for the lofty heights of the grand canonical ensemble through to more hardcore statistical physics, including phase transitions and universality, or towards more abstract systems, and the fundamental idea of Shannon information entropy that underpins modern notions of computability and abstraction. These paths will cross again once we reach von Neumann entropy and quantum information theory. But, as usual,

verum haec ipse equidem spatiis exclusus iniquis
praetereo atque aliis post me memoranda relinquo.⁸

Calculator

To save time for people who actually are conducting this activity, I provide below a quick calculator for parameters relating to the Boltzmann coin game, in the thermodynamic limit.

References

1. B Michalek, RM Hanson. "Give them money: The Boltzmann game, a classroom or laboratory activity modeling entropy changes and the distribution of energy in chemical systems." Journal of Chemical Education 83, no. 4 (2006):581.