Networks and Population Biology (Part 4)

Today was the last day of the tutorials on discrete mathematics and probability in networks and population biology. Persi Diaconis gave two talks, one on ‘exponential families’ of random graphs and one on ‘exchangeability’. Since there’s way too much to summarize, I’ll focus on explaining ideas from the first talk, leaving you to read about the second here:

• Persi Diaconis and Svante Janson, Graph limits and exchangeable random graphs.

Susan Holmes also gave two talks. The first was on metagenomics and the human microbiome—very cool stuff. Did you know that your body contains 100 trillion bacteria, and only 10 trillion human cells? And you’ve got 1000 species of bacteria in your gut? Statistical ecologists are getting very interested in this.

Her second talk was about doing statistics when you’ve got lots of data of different kinds that need to be integrated: numbers, graphs and trees, images, spatial information, and so on. This is clearly the wave of the future. You can see the slides for this talk here:

• Susan Holmes, Heterogeneous data challenge: combining complex data.

The basic idea of Persi Diaconis’ talk was simple and shocking. Suppose you choose a random graph in the most obvious way designed to heighten the chance that it contains a triangle, or some other figure. Then in fact all you’ve done is change the chance that there’s an edge between any given pair of vertices!

But to make this precise—to make it even true—we need to say what the rules are.

For starters, let me point you back to part 2 for Persi’s definitions of ‘graph’ and ‘graph homomorphism’. If we fix a finite set , there will be a big set of graphs with exactly these vertices. To define a kind of ‘random graph’, we first pick a probability measure on each set . Then, we demand that these probability measures converge in a certain sense as .

However, we can often describe random graphs in a more intuitive way! For example, the simplest random graphs are the Erdős–Rényi random graphs. These depend on a parameter . The idea here is that we take our set of vertices and for each pair we flip a coin that lands heads up with probability . If it lands heads up, we stick in an edge between those vertices; otherwise not. So, the presence or absence of each edge is an independent random variable.

Here’s a picture of an Erdős–Rényi random graph drawn by von Frisch, with a 1% chance of an edge between any two vertices. But it’s been drawn in a way so that the best-connected vertices are near the middle, so it doesn’t look as random as it is:

People have studied the Erdős–Rényi random graphs very intensively, so now people are eager to study random graphs with more interesting correlations. For example, consider the graph where we draw an edge between any two people who are friends. If you’re my friend and I’m friends with someone else, that improves the chances that you’re friends with them! In other words, friends tend to form ‘triangles’. But in an Erdős–Rényi random graph there’s no effect like that.

‘Exponential families’ of random graphs seem like a way around this problem. The idea here is to pick a specific collection of graphs and say how commonly we want these to appear in our random graph. If we only use one graph , and we take this to be two vertices connected by an edge, we’ll get an Erdős–Rényi random graph. But, if we also want our graph to contain a lot of triangles, we can pick to be a triangle.

More precisely, remember from part 2 that is the fraction of functions mapping to vertices of that are actually graph homomorphisms. This is the smart way to keep track of how often shows up inside . So, we pick some numbers and define a probability measure on as follows: the probability of any particular graph should be proportional to

If you’re a physicist you’ll call this a ‘Gibbs state’, and you’ll know this is the way to get a probability distribution that maximizes entropy while holding the expected values of constant. Statisticians like to call the whole family of Gibbs states as we vary the number an ‘exponential family’. But the cool part, for me, is that we can apply ideas from physics—namely, statistical mechanics—to graph theory.

So far we’ve got a probability measure on our set of graphs with vertices. These probability measures converge in a certain sense as . But Diaconis and Chatterjee proved a shocking theorem: for almost all choices of the graphs and numbers , these probability measures converge to an Erdős–Rényi random graph! And in the other cases, they converge to a probabilistic mixture of Erdős–Rényi random graphs.

In short, as long as the numbers are positive, exponential families don’t buy us much. We could just work with Erdős–Rényi random graphs, or probabilistic mixtures of these. The exponential families are still very interesting to study, but they don’t take us into truly new territory.

The theorem is here:

• Sourav Chatterjee and Persi Diaconis, Estimating and understanding random graph models.

To reach new territory, we can try letting some be negative. The paper talks about this too. Here many questions remain open!

Networks and Population Biology (Part 3)

I think today I’ll focus on one aspect of the talks Susan Holmes gave today: the space of phylogenetic trees. Her talks were full of interesting applications to genetics, but I’m afraid my summary will drift off into a mathematical daydream inspired by what she said! Luckily you can see her actual talk uncontaminated by my reveries here:

• Susan Holmes, Treespace: distances between trees.

It’s based on this paper:

• Louis Billera, Susan Holmes and Karen Vogtmann, Geometry of the space of phylogenetic trees, Advances in Applied Mathematics 27 (2001), 733-767.

As I mentioned last time, a phylogenetic tree is something like this:

More mathematically, what we see here is a tree (a connected graph with no circuits), with a distinguished vertex called the root, and vertices of degree 1, called leaves, that are labeled with elements from some -element set. We shall call such a thing a leaf-labelled rooted tree.

Now, the tree above is actually a binary tree, meaning that as we move up an edge, away from the root, it either branches into two new edges or ends in a leaf. (More precisely: each vertex that doesn’t have degree 1 has degree 3.) This makes sense in biology because while species often split into two as they evolve, it is less likely for a species to split into three all at once.

So, the phylogenetic trees we see in biology are usually leaf-labeled rooted binary trees. However, we often want to guess such a tree from some data. In this game, trees that aren’t binary become important too!

Why? Well, each edge of the tree can be labeled with a number saying how much evolution occurred along that edge: for example, how many DNA base pairs changed. But as this number goes to zero, we get a tree that’s not binary anymore. So, we think of non-binary trees as conceptually useful ‘intermediate cases’ between binary trees.

This idea immediately leads us to consider a topological space consisting of phylogenetic trees which are not necessarily binary. And at this point in the lecture I drifted off into a daydream about ‘operads’, which are a nice piece of mathematics that’s closely connected to this idea.

So, I will deviate slightly from Holmes and define a phylogenetic tree to be a leaf-labeled rooted tree where each edge is labeled by a number called its length. This length must be positive for every edge except the edge incident to the root; for that edge any nonnegative length is allowed.

Let’s write for the set of phylogenetic trees with leaves. This becomes a topological space in a fairly obvious way. For example, there’s a continuous path in that looks like this:

Moreover we have this fact:

Theorem. There is a topological operad called the phylogenetic operad, or whose space of n-ary operations is for and the empty set for .

If you don’t know what an operad is, don’t be scared. This mainly just means that you can glue a bunch of phylogenetic trees to the top of another one and get a new phylogenetic tree! More precisely, suppose you have a phylogenetic tree with leaves, say . And suppose you have more, say . Then you can glue the roots of to the leaves of to get a new phylogenetic tree called . Furthermore, this gluing operation obeys some rules which look incredibly intimidating when you write them out using symbols, but pathetically obvious when you draw them using pictures of trees. And these rules are the definition of an operad.

I would like to know if mathematicians have studied the operad It’s closely related to Stasheff’s associahedron operad, but importantly different. Operads have ‘algebras’, and the algebras of the associahedron operad are topological spaces with a product that’s ‘associative up to coherent homotopy’. I believe algebras of the phylogenetic operad are topological spaces with a commutative product that’s associative up to coherent homotopy. Has someone studied these?

In their paper Holmes and her coauthors discuss the associahedron in relation to their own work, but they don’t mention operads. I’ve found another paper that mentions ‘the space of phylogenetic trees’:

• David Speyer and Bernd Sturmfels, The tropical Grassmannian, Adv. Geom. 4 (2004), 389–411.

but they don’t seem to study the operad aspect either.

Perhaps one reason is that Holmes and her coauthors deliberately decide to ignore the labellings on the edges incident to the leaves. So, they get a space of phylogenetic trees with leaves whose product with is the space I’m calling . As they mention, this simplifies the geometry a bit. However, it’s not so nice if you want an operad that accurately describes how you can build a big phylogenetic tree from smaller ones.

They don’t care about operads; they do some wonderful things with the geometry of their space of phylogenetic trees. They construct a natural metric on it, and show it’s a CAT(0) space in the sense of Gromov. This means that the triangles in this space are more skinny than those in Euclidean space—more like triangles in hyperbolic space:

They study geodesics in this space—even though it’s not a manifold, but something more singular. And so on!

There’s a lot of great geometry here. But for Holmes, all this is just preparation for doing some genomics— for example, designing statistical tests to measure how reliable the phylogenetic trees guessed from data actually are. And for that aspect, try this:

• Susan Holmes, Statistical approach to tests involving phylogenies, in O. Gascuel, editor, Mathematics of Evolution and Phylogeny, Oxford U. Press, Oxford, 2007.

Networks and Population Biology (Part 2)

Yesterday I was too sick to attend this conference:

• Tutorials on discrete mathematics and probability in networks and population biology, Institute of Mathematical Sciences, National University of Singapore, 2-6 May 2011. Organized by Andrew Barbour, Malwina Luczak, Gesine Reinert and Rongfeng Sun.

But today I bounced back, and I want to tell you about the first lectures by Persi Diaconis and his wife Susan Holmes, both statisticians at Stanford University.

Since Persi Diaconis is one of those people who make it really obvious that being a mathematician is more fun than any other profession, I should say a bit about him. He left home at the age of 14 to become a professional stage magician, and only returned to school so that he could learn all the math needed to understand Feller’s famous book An Introduction to Probability Theory and Its Applications. Since then he has worked on the mathematics of shuffling cards and the physics of flipping coins. He also works on random matrix theory, the statistics of Riemann zeta zeroes, applications of Hopf algebras to probability theory, and all sorts of other things that don’t sound fun unless you know enough to realize that yes, they are.

In my last blog post on this conference Tim van Beek asked if Persi could really flip a coin and have it land with whatever side up he wanted. So, I asked him about that. He said yes, he could. He didn’t demonstrate it at the time, since we were just about to go to a talk. But he said you can see videos of other people doing it on the web.

Unfortunately, the videos I’ve found so far mainly convince me, not that there are people who have mastered the physical skill of controlling a coin flip, but that there are lots of tricksters out there! Here are two:

• Derrin Brown, The system – coin toss.

• EricSurf6, How to win a coin toss.

Can you figure out how they do it? If you don’t get the second one, you can watch this.

So, I have to wonder: can Persi really flip a coin and have it land the way he wants, or is just fooling people into thinking he can? Mind you, I wouldn’t consider the latter a bad thing, at least insofar as he’s still a practicing stage magician: a basic part of the craft is trickery of this sort. I should ask if he’s sworn the Magician’s Oath:

“As a magician I promise never to reveal the secret of any illusion to a non-magician, unless that one swears to uphold the Magician’s Oath in turn. I promise never to perform any illusion for any non-magician without first practicing the effect until I can perform it well enough to maintain the illusion of magic.”

Anyway, he is giving a series of talks on “Graph limits and exponential models”. There are lots of very large graphs in biology, so he plans to talk about ways to study large graphs by taking limits where the graphs become infinite. He began by describing a result so beautiful that I would like to state it here.

‘Graph’ means many things, but in his talk a graph is simple (no self-loops or multiple edges between vertices), undirected and labeled. In other words, something like this:

A graph homomorphism

is a map sending vertices of to vertices of , such that whenever vertices of have an edge between them, the vertices have an edge between them in .

Given this, we can define to be the fraction of the functions from vertices of to vertices of that are actually graph homomorphisms.

The famous graph theorist Lovasz said that a sequence of graphs converges if converges for all graphs .

Using this definition, we have:

Theorem (Aldous-Hoover, Lovasz et al). There is a compact metric space such that each graph gives a point in , and a sequence of graphs converges iff

for some point .

The space is called the space of graph limits, and the important thing is that one can construct it rather explicitly! Persi explained how. For a written explanation, see:

• Miklos Racz, Dense graph limits, 31 October 2010.

After a break, Susan Holmes began her series of talks on “Phylogeny, trees and the human microbiome”. I can’t easily summarize all she said, but here are the slides for the first talk:

• Susan Holmes, Molecular evolution: phylogenetic tree building.

Her basic plan today was to teach us a little genomics, a little statistics, and a little bit about Markov chains, so that we could start to understand how people attempt to reconstruct phylogenetic trees from DNA data.

A phylogenetic tree is something like this:

or something less grand where, for example, you only consider species of frogs, or even HIV viruses in a single patient. These days there are programs to generate such trees given copies of the ‘same gene’ in the different organisms you’re considering. These programs have names like PhyML, FastML, RaxML and Mr. Bayes. In case you’re wondering, ‘ML’ stands for ‘maximum likelihood’ a standard technique in statistics, while Bayes was the originator of some very important ideas in statistical reasoning.

But even though there are programs to do these things, there are still lots of fascinating problems to solve in this area! And indeed, even understanding the programs is a bit of a challenge.

Since we were talking about the genetic code here recently, I’ll wrap up by mentioning one thing learned about this from Susan’s talk.

It’s common to describe the accumulation of changes in DNA using substitution models. These are continuous time Markov chains where each base pair has a given probability of mutating to another one. Often people assume this probability for each base pair is independent of what its neighbors do. The last assumption is known to be false, but that’s another story for another day! What I wanted to say is that there are two famous models. The simplest is the Jukes-Cantor model, where each of the four bases—A, T, C, and G—has an equal probability of mutating into any other. But a somewhat better model is the Kimura model, where the transitions

A ↔ T
C ↔ G

have a different rate of occuring than all the remaining possibilities. If you look at the pictures of the A, T, C, and G molecules here you’ll instantly see why:

Since I’m busy learning about continuous-time Markov chains, it’s nice to see more good examples!

Moore’s Law for Solar Power?

Here are two items that were forwarded to me by friends—Mike Stay and Greg Egan. First:

• Ramez Naam, The Moore’s Law of solar energy, Scientific American guest blog, 16 March 2011.

Executive summary: solar cost per watt is dropping on an exponential curve, and will drop below coal by 2020. As usual we see some graphs where the past is fairly wiggly:

while the future is a smooth and mathematically simple, starting tomorrow:

Both these graphs show the price per watt of photovoltaic solar modules (not counting installation), measured in 2009 dollars. Both graphs are logarithmic, so an exponential decline in price per watt would show up as a straight line.

Of course, anyone can draw a curve through points. The question is whether experts can see a way to keep the trend going!

On this, the author writes:

While in the earlier part of this decade prices flattened for a few years, the sharp decline in 2009 made up for that and put the price reduction back on track. Data from 2010 (not included above) shows at least a 30 percent further price reduction, putting solar prices ahead of this trend.

He also writes:

We should always be careful of extrapolating trends out, of course. Natural processes have limits. Phenomena that look exponential eventually level off or become linear at a certain point. Yet physicists and engineers in the solar world are optimistic about their roadmaps for the coming decade. The cheapest solar modules, not yet on the market, have manufacturing costs under $1 per watt, making them contenders – when they reach the market – for breaking the 12 cents per Kwh mark.

The exponential trend in solar watts per dollar has been going on for at least 31 years now. If it continues for another 8-10, which looks extremely likely, we’ll have a power source which is as cheap as coal for electricity, with virtually no carbon emissions. If it continues for 20 years, which is also well within the realm of scientific and technical possibility, then we’ll have a green power source which is half the price of coal for electricity.

What do you think? Is this for real?

By the way, Naam’s blog post has a chart showing efficiencies of various solar cell technologies. It’s unreadably small, but here’s a version you can click to enlarge:

What I want to caution you about is that some of the more efficient solar cells use expensive materials for which the world supply is limited. For more on this see

• Photovoltaic solar power, Azimuth Wiki: efficiency and physics of solar cells.

Here’s another article:

• Kevin Bullis, More Power from Rooftop Solar: A startup says technology inspired by RAID hard drives can boost power output by up to 50 percent, Technology Review, 29 April 2011.

Immediately below the headline they tone down the claim slightly, saying “25 to 50 percent”. But that’s still a lot. The idea sounds nice, too:

Solar cells have become more efficient in recent years, but much of the improvement has gone to waste because of the way solar cells are put together in solar panels, the way the panels are wired together, and the way the electricity is converted into AC power for use in homes or on the grid. Typically, the power output from a string of solar cells is limited by the lowest-performing cell. So if a shadow falls on just one cell in a panel, the power output of the whole system drops dramatically. And failure at any point in the string can shut down the whole system.

TenKsolar has opted for a more complex wiring system—inspired by a reliable type of computer memory known as RAID (for “redundant array of independent disks”), in which hard disks are connected in ways that maintain performance even if some fail. TenKsolar’s design allows current to take many different paths through a solar-panel array, thus avoiding bottlenecks at low-performing cells and making it possible to extract far more of the electricity that the cells produce.

Networks and Population Biology (Part 1)

There are some tutorials starting today here:

• Tutorials on discrete mathematics and probability in networks and population biology, Institute of Mathematical Sciences, National University of Singapore, 2-6 May 2011. Organized by Andrew Barbour, Malwina Luczak, Gesine Reinert and Rongfeng Sun.

Rick Durrett is speaking on “Cancer modelling”. For his slides, see here, here and here. But here’s a quick taste:

Back in 1954, Armitage and Doll noticed that log-log plots of cancer incidence as a function of age are close to linear, except for breast cancer, which slows down in older women. They suggested an explanation: a chain of independent random events have to occur before cancer can start. A simple model based on a Markov process gives a simple formula for how many events it must take—see the first batch of slides for details. This work was the first of a series of ever more sophisticated multi-stage models of carcinogenesis.

One of the first models Durrett explained was the Moran process: a stochastic model of a finite population of constant size in which things of two types, say and are competing for dominance. I believe this model can be described by a stochastic Petri net with two states, and , and two transitions:

and

Since I like stochastic Petri nets, I’d love to add this to my collection.

Chris Cannings is talking about “Evolutionary conflict theory” and the concept of ‘evolutionary stable strategies’ for two-party games. Here’s the basic idea, in a nutshell.

Suppose a population of animals roams around randomly and whenever two meet, they engage in some sort of conflict… or more generally, any sort of ‘game’. Suppose each can choose from some set of strategies. Suppose that if one chooses strategy and the other chooses strategy , the expected ‘payoff’ to the one is , while for the other it’s .

More generally, the animals might choose their strategies probabilistically. If the first chooses the ith strategy with probability and the second chooses it with probability then the expected payoff to the first player is

where the angle brackets are the usual inner product in I’m saying this in an overly fancy way, and making it look like quantum mechanics, in the hope that some bright kid out there will get some new ideas. But it’s not rocket science; the angle bracket is just a notation for this sum:

Let me tell you what it means for a probabilistic strategy to be ‘evolutionarily stable’. Suppose we have a ‘resident’ population of animals with strategy and we add a few ‘invaders’ with some other strategy, say . Say the fraction of animals who are invaders is some small number , while the fraction of residents is .

If a resident plays the game against a randomly chosen animal, its expected payoff will be

Indeed, it’s just as if the resident was playing the game against an animal with probabilistic strategy ! On the other hand, if an invader plays the game against a randomly chosen animal, its expected payoff will be

The strategy is evolutionarily stable if the residents do better:

for all probability distributions and sufficiently small .

Canning showed us how to manipulate this condition in various ways and prove lots of nice theorems. His slides will appear online later, and then I’ll include a link to them. Naturally, I’m hoping we’ll see that a dynamical model, where animals with greater payoff get to reproduce more, has the evolutionary stable strategies as stable equilibria. And I’m hoping that some model of this sort can be described using a stochastic Petri net—though I’m not sure I see how.

On another note, I was happy to see Persi Diaconis and meet his wife Susan Holmes. Both will be speaking later in the week. Holmes is a statistician who specializes in “large, messy datasets” from biology. Lately she’s been studying ant networks! Using sophisticated image analysis to track individual ants over long periods of time, she and her coauthors have built up networks showing who meets who in ant ant colony. They’ve found, for example, that some harvester ants interact with many more of their fellows than the average ant. However, this seems to be due to their location rather than any innate proclivity. They’re the ants who hang out near the entrance of the nest!

That’s my impression from a short conversation, anyway. I should read her brand-new paper:

• Noa Pinter-Wollman, Roy Wollman, Adam Guetz, Susan Holmes and Deborah M. Gordon, The effect of individual variation on the structure and function of interaction networks in harvester ants, Journal of the Royal Society Interface, 13 April 2011.

She said this is a good book to read:

• Deborah M. Gordon, Ant Encounters: Interaction Networks and Colony Behavior, Princeton U. Press, Princeton New Jersey, 2010.

There are also lots of papers available at Gordon’s website.

Time to Wake Up?

Read this:

• Jeremy Grantham, Time to wake up: days of abundant resources and falling prices are over forever, The Oil Drum, 29 April 2011. Original in PDF.

Jeremy Grantham is the chief investment officer of GMO Capital, a big investment firm. His essay is so readable that there’s no point in trying to outdo it. I’ll just include his summary, which you won’t find on The Oil Drum.

Also, this graph is worth staring at (click to expand):

Many claim that human ingenuity will always keep the price of resources dropping. That was true from 1900 to 2002, with average price decline of 1.2% per year in constant dollars. There were upward spikes for world wars… but the inflationary oil shock of the 1970s was something new: I remember the puzzled, upset mood in the US. But since 2002, according to Grantham, we’ve started seeing something even bigger.

If he’s right, this is very important. What do you think?

Personally I agree completely with his general point that exponential growth is always unsustainable in the long term. Even a civilization expanding through the universe at nearly the speed of light will only grow in a roughly cubic way. Exponential growth is ‘transient behavior’ that happens only near the beginning of a process. So to me, the really interesting question is the empirical one of whether we’re seeing, right now, the transition to a world where resources continue to become more expensive. If you think otherwise, you should convince us that this is a temporary glitch that will end when… something happens.

Summary of the Summary

The world is using up its natural resources at an alarming rate, and this has caused a permanent shift in their value. We all need to adjust our behavior to this new environment. It would help if we did it quickly.

Summary

• Until about 1800, our species had no safety margin and lived, like other animals, up to the limit of the food supply, ebbing and flowing in population.

• From about 1800 on the use of hydrocarbons allowed for an explosion in energy use, in food supply, and, through the creation of surpluses, a dramatic increase in wealth and scientific progress.

• Since 1800, the population has surged from 800 million to 7 billion, on its way to an estimated 8 billion, at minimum.

• The rise in population, the ten-fold increase in wealth in developed countries, and the current explosive growth in developing countries have eaten rapidly into our finite resources of hydrocarbons and metals, fertilizer, available land, and water.

• Now, despite a massive increase in fertilizer use, the growth in crop yields per acre has declined from 3.5% in the 1960s to 1.2% today. There is little productive new land to bring on and, as people get richer, they eat more grain-intensive meat. Because the population continues to grow at over 1%, there is little safety margin.

• The problems of compounding growth in the face of finite resources are not easily understood by optimistic, short-term-oriented, and relatively innumerate humans (especially the political variety).

• The fact is that no compound growth is sustainable. If we maintain our desperate focus on growth, we will run out of everything and crash. We must substitute qualitative growth for quantitative growth.

• But Mrs. Market is helping, and right now she is sending us the Mother of all price signals. The prices of all important commodities except oil declined for 100 years until 2002, by an average of 70%. From 2002 until now, this entire decline was erased by a bigger price surge than occurred during World War II.

• Statistically, most commodities are now so far away from their former downward trend that it makes it very probable that the old trend has changed — that there is in fact a Paradigm Shift — perhaps the most important economic event since the Industrial Revolution.

• Climate change is associated with weather instability, but the last year was exceptionally bad. Near term it will surely get less bad.

• Excellent long-term investment opportunities in resources and resource efficiency are compromised by the high chance of an improvement in weather next year and by the possibility that China may stumble.

• From now on, price pressure and shortages of resources will be a permanent feature of our lives. This will increasingly slow down the growth rate of the developed and developing world and put a severe burden on poor countries.

• We all need to develop serious resource plans, particularly energy policies. There is little time to waste.

Crooks’ Fluctuation Theorem

guest post by Eric Downes

Christopher Jarzynski, Gavin Crooks, and some others have made a big splash by providing general equalities that relate free energy differences to non-equilibrium work values. The best place to start is the first two chapters of Gavin Crooks’ thesis:

• Gavin Crooks, Excursions in Statistical Dynamics, Ph.D. Thesis, Department of Chemistry, U.C. Berkeley, 1999.

Here is the ~1 kiloword summary:

If we consider the work done on a system, Clausius’ Inequality states that

where is the change in free energy. One must perform more work along a non-equilibrium path because of the second law of thermodynamics. The excess work

is dissipated as heat, and is basically the entropy change in the universe, measured in different units. But who knows how large the excess work will be…

One considers a small system for which we imagine there exists a distribution of thermodynamic work values (more on that below) in moving a system through phase space. We start at a macrostate with free energy , and (staying in touch with a thermal reservoir at inverse temperature ) move in finite time to a new non-equilibrium state. When this new state is allowed to equilibriate it will have free energy

You can do this by changing the spin-spin coupling, compressing a gas, etc: you’re changing one of the parameters in the system’s Hamiltonian in a completely deterministic way, such that the structure of the Hamiltonian does not change, and the system still has well-defined microstates at all intervening times. Your total accumulated work values will follow

where the expectation value is over a distribution of all possible paths through the classical phase space. This is the Jarzynski Equality.

It has an analogue for quantum systems, which appears to be related to supersymmetry, somehow. But the proof for classical systems simply relies on a Markov chain that moves through state space and an appropriate definition for work (see below). I can dig up the reference if anyone wants.

This is actually a specific case of a more fundamental theorem discovered about a decade ago by Gavin Crooks: the Crooks fluctuation theorem:

where is the probability of a particular forward path which requires work , and is the probability of its time-reversal dual (see Gavin Crooks’ thesis for more precise definitions).

How do we assign a thermodynamic work value to a path of microstates? At the risk of ruining it for you: It turns out that one can write a first law analog for a subsystem Hamiltonian. We start with:

As with Gibbs’ derivation of the canonical ensemble, we never specify what and are, only that the number of degrees of freedom in is very large, and is a small coupling. You make the observation that work can be associated with changing the energy-levels of the microstates in , while heat is associated with the energy change when the (sub)system jumps from one microstate to another (due to ) with no change in the spectrum of available energies. This implies a rather deep connection between the Hamiltonian and thermodynamic work. The second figure in Gavin’s thesis explained everything for me, after that you can basically derive it yourself.

The only physical applications I am aware of are to Monte Carlo simulations and mesoscopic systems in nano- or molecular biophysics. In that regard John Baez’ recent relation between free energy and Rényi entropy is a nice potential competitor for the efficient calculation of free energy differences (which apparently normally requires multiple simulations at intervening temperaturess, calculating the specific heat at each.)

But the relation to Markov chains is much more interesting to me, because this is a very general mathematical object which can be related to a much broader class of problems. Heat ends up being associated with fluctuations in the system’s state, and the (phenomenological) energy values are kind of the “relative unlikelihood” of each state. The excess work turns out to be related to the Kullback-Leibler divergence between the forward and reverse path-probabilities.

For visual learners with a background in stat mech, this is all developed in a pedagogical talk I gave in Fall 2010 at U. Wisconsin-Madison’s Condensed Matter Theory Seminar; talk available here. I’m licensing it cc-by-sa-nc through the Creative Commons License. I’ve been sloppy with references, but I emphasize that this is not original work; it is my presentation of Crooks’ and Jarzynski’s. Nonetheless, any errors you find are my own. Hokay, have a nice day!