<![CDATA[The Mathematical Origin of Irreversibility]]>

<![CDATA[The Mathematical Origin of Irreversibility]]>guest post by Matteo Smerlak

Introduction

Thermodynamical dissipation and adaptive evolution are two faces of the same Markovian coin!

Consider this. The Second Law of Thermodynamics states that the entropy of an isolated thermodynamic system can never decrease; Landauer’s principle maintains that the erasure of information inevitably causes dissipation; Fisher’s fundamental theorem of natural selection asserts that any fitness difference within a population leads to adaptation in an evolution process governed by natural selection. Diverse as they are, these statements have two common characteristics:

1. they express the irreversibility of certain natural phenomena, and

2. the dynamical processes underlying these phenomena involve an element of randomness.

Doesn’t this suggest to you the following question: Could it be that thermal phenomena, forgetful information processing and adaptive evolution are governed by the same stochastic mechanism?

The answer is—yes! The key to this rather profound connection resides in a universal property of Markov processes discovered recently in the context of non-equilibrium statistical mechanics, and known as the ‘fluctuation theorem’. Typically stated in terms of ‘dissipated work’ or ‘entropy production’, this result can be seen as an extension of the Second Law of Thermodynamics to small systems, where thermal fluctuations cannot be neglected. But it is actually much more than this: it is the mathematical underpinning of irreversibility itself, be it thermodynamical, evolutionary, or else. To make this point clear, let me start by giving a general formulation of the fluctuation theorem that makes no reference to physics concepts such as ‘heat’ or ‘work’.

The mathematical fact

Consider a system randomly jumping between states $a, b,\dots$ with (possibly time-dependent) transition rates $\gamma_{a b}(t)$ where $a$ is the state prior to the jump, while $b$ is the state after the jump. I’ll assume that this dynamics defines a (continuous-time) Markov process, namely that the numbers $\gamma_{a b}$ are the matrix entries of an infinitesimal stochastic matrix, which means that its off-diagonal entries are non-negative and that its columns sum up to zero.

Now, each possible history $\omega=(\omega_t)_{0\leq t\leq T}$ of this process can be characterized by the sequence of occupied states $a_{j}$ and by the times $\tau_{j}$ at which the transitions $a_{j-1}\longrightarrow a_{j}$ occur $(0\leq j\leq N)$ :

$\omega=(\omega_{0}=a_{0}\overset{\tau_{0}}{\longrightarrow} a_{1} \overset{\tau_{1}}{\longrightarrow}\cdots \overset{\tau_{N}}{\longrightarrow} a_{N}=\omega_{T}).$

Define the skewness $\sigma_{j}(\tau_{j})$ of each of these transitions to be the logarithmic ratio of transition rates:

$\displaystyle{\sigma_{j}(\tau_{j}):=\ln\frac{\gamma_{a_{j}a_{j-1}}(\tau_{j})}{\gamma_{a_{j-1}a_{j}}(\tau_{j})}}$

Also define the self-information of the system in state $a$ at time $t$ by:

$i_a(t):= -\ln\pi_{a}(t)$

where $\pi_{a}(t)$ is the probability that the system is in state $a$ at time $t$ , given some prescribed initial distribution $\pi_{a}(0)$ . This quantity is also sometimes called the surprisal, as it measures the ‘surprise’ of finding out that the system is in state $a$ at time $t$ .

Then the following identity—the detailed fluctuation theorem—holds:

$\mathrm{Prob}[\Delta i-\Sigma=-A] = e^{-A}\;\mathrm{Prob}[\Delta i-\Sigma=A] \;$

where

$\displaystyle{\Sigma:=\sum_{j}\sigma_{j}(\tau_{j})}$

is the cumulative skewness along a trajectory of the system, and

$\Delta i= i_{a_N}(T)-i_{a_0}(0)$

is the variation of self-information between the end points of this trajectory.

This identity has an immediate consequence: if $\langle\,\cdot\,\rangle$ denotes the average over all realizations of the process, then we have the integral fluctuation theorem:

$\langle e^{-\Delta i+\Sigma}\rangle=1,$

which, by the convexity of the exponential and Jensen’s inequality, implies:

$\langle \Delta i\rangle=\Delta S\geq\langle\Sigma\rangle.$

In short: the mean variation of self-information, aka the variation of Shannon entropy

$\displaystyle{ S(t):= \sum_{a}\pi_{a}(t)i_a(t) }$

is bounded from below by the mean cumulative skewness of the underlying stochastic trajectory.

This is the fundamental mathematical fact underlying irreversibility. To unravel its physical and biological consequences, it suffices to consider the origin and interpretation of the ‘skewness’ term in different contexts. (By the way, people usually call $\Sigma$ the ‘entropy production’ or ‘dissipation function’—but how tautological is that?)

The physical and biological consequences

Consider first the standard stochastic-thermodynamic scenario where a physical system is kept in contact with a thermal reservoir at inverse temperature $\beta$ and undergoes thermally induced transitions between states $a, b,\dots$ . By virtue of the detailed balance condition:

$\displaystyle{ e^{-\beta E_{a}(t)}\gamma_{a b}(t)=e^{-\beta E_{b}(t)}\gamma_{b a}(t),}$

the skewness $\sigma_{j}(\tau_{j})$ of each such transition is $\beta$ times the energy difference between the states $a_{j}$ and $a_{j-1}$ , namely the heat received from the reservoir during the transition. Hence, the mean cumulative skewness $\langle \Sigma\rangle$ is nothing but $\beta\langle Q\rangle,$ with $Q$ the total heat received by the system along the process. It follows from the detailed fluctuation theorem that

$\langle e^{-\Delta i+\beta Q}\rangle=1$

and therefore

$\Delta S\geq\beta\langle Q\rangle$

which is of course Clausius’ inequality. In a computational context where the control parameter is the entropy variation itself (such as in a bit-erasure protocol, where $\Delta S=-\ln 2$ ), this inequality in turn expresses Landauer’s principle: it impossible to decrease the self-information of the system’s state without dissipating a minimal amount of heat into the environment (in this case $-Q \geq k T\ln2$ , the ‘Landauer bound’). More general situations (several types of reservoirs, Maxwell-demon-like feedback controls) can be treated along the same lines, and the various forms of the Second Law derived from the detailed fluctuation theorem.

Now, many would agree that evolutionary dynamics is a wholly different business from thermodynamics; in particular, notions such as ‘heat’ or ‘temperature’ are clearly irrelevant to Darwinian evolution. However, the stochastic framework of Markov processes is relevant to describe the genetic evolution of a population, and this fact alone has important consequences. As a simple example, consider the time evolution of mutant fixations $x_{a}$ in a population, with $a$ ranging over the possible genotypes. In a ‘symmetric mutation scheme’, which I understand is biological parlance for ‘reversible Markov process’, meaning one that obeys detailed balance, the ratio between the $a\mapsto b$ and $b\mapsto a$ transition rates is completely determined by the fitnesses $f_{a}$ and $f_b$ of $a$ and $b$ , according to

$\displaystyle{\frac{\gamma_{a b}}{\gamma_{b a}} =\left(\frac{f_{b}}{f_{a}}\right)^{\nu} }$

where $\nu$ is a model-dependent function of the effective population size [Sella2005]. Along a given history of mutant fixations, the cumulated skewness $\Sigma$ is therefore given by minus the fitness flux:

$\displaystyle{\Phi=\nu\sum_{j}(\ln f_{a_j}-\ln f_{a_{j-1}}).}$

The integral fluctuation theorem then becomes the fitness flux theorem:

$\displaystyle{ \langle e^{-\Delta i -\Phi}\rangle=1}$

discussed recently by Mustonen and Lässig [Mustonen2010] and implying Fisher’s fundamental theorem of natural selection as a special case. (Incidentally, the ‘fitness flux theorem’ derived in this reference is more general than this; for instance, it does not rely on the ‘symmetric mutation scheme’ assumption above.) The ensuing inequality

$\langle \Phi\rangle\geq-\Delta S$

shows that a positive fitness flux is “an almost universal evolutionary principle of biological systems” [Mustonen2010], with negative contributions limited to time intervals with a systematic loss of adaptation ( $\Delta S > 0$ ). This statement may well be the closest thing to a version of the Second Law of Thermodynamics applying to evolutionary dynamics.

It is really quite remarkable that thermodynamical dissipation and Darwinian evolution can be reduced to the same stochastic mechanism, and that notions such as ‘fitness flux’ and ‘heat’ can arise as two faces of the same mathematical coin, namely the ‘skewness’ of Markovian transitions. After all, the phenomenon of life is in itself a direct challenge to thermodynamics, isn’t it? When thermal phenomena tend to increase the world’s disorder, life strives to bring about and maintain exquisitely fine spatial and chemical structures—which is why Schrödinger famously proposed to define life as negative entropy. Could there be a more striking confirmation of his intuition—and a reconciliation of evolution and thermodynamics in the same go—than the fundamental inequality of adaptive evolution $\langle\Phi\rangle\geq-\Delta S$ ?

Surely the detailed fluctuation theorem for Markov processes has other applications, pertaining neither to thermodynamics nor adaptive evolution. Can you think of any?

Proof of the fluctuation theorem

I am a physicist, but knowing that many readers of John’s blog are mathematicians, I’ll do my best to frame—and prove—the FT as an actual theorem.

Let $(\Omega,\mathcal{T},p)$ be a probability space and $(\,\cdot\,)^{\dagger}=\Omega\to \Omega$ a measurable involution of $\Omega$ . Denote $p^{\dagger}$ the pushforward probability measure through this involution, and

$\displaystyle{ R=\ln \frac{d p}{d p^\dagger} }$

the logarithm of the corresponding Radon-Nikodym derivative (we assume $p^\dagger$ and $p$ are mutually absolutely continuous). Then the following lemmas are true, with $(1)\Rightarrow(2)\Rightarrow(3)$ :

Lemma 1. The detailed fluctuation relation:

$\forall A\in\mathbb{R} \quad p\big(R^{-1}(-A) \big)=e^{-A}p \big(R^{-1}(A) \big)$

Lemma 2. The integral fluctuation relation:

$\displaystyle{\int_{\Omega} d p(\omega)\,e^{-R(\omega)}=1 }$

Lemma 3. The positivity of the Kullback-Leibler divergence:

$D(p\,\Vert\, p^{\dagger}):=\int_{\Omega} d p(\omega)\,R(\omega)\geq 0.$

These are basic facts which anyone can show: $(2)\Rightarrow(3)$ by Jensen’s inequality, $(1)\Rightarrow(2)$ trivially, and $(1)$ follows from $R(\omega^{\dagger})=-R(\omega)$ and the change of variables theorem, as follows,

$\begin{array}{ccl} \displaystyle{ \int_{R^{-1}(-A)} d p(\omega)} &=& \displaystyle{ \int_{R^{-1}(A)}d p^{\dagger}(\omega) } \\ \\ &=& \displaystyle{ \int_{R^{-1}(A)} d p(\omega)\, e^{-R(\omega)} } \\ \\ &=& \displaystyle{ e^{-A} \int_{R^{-1}(A)} d p(\omega)} .\end{array}$

But here is the beauty: if

• $(\Omega,\mathcal{T},p)$ is actually a Markov process defined over some time interval $[0,T]$ and valued in some (say discrete) state space $\Sigma$ , with the instantaneous probability $\pi_{a}(t)=p\big(\{\omega_{t}=a\} \big)$ of each state $a\in\Sigma$ satisfying the master equation (aka Kolmogorov equation)

$\displaystyle{ \frac{d\pi_{a}(t)}{dt}=\sum_{b\neq a}\Big(\gamma_{b a}(t)\pi_{a}(t)-\gamma_{a b}(t)\pi_{b}(t)\Big),}$

and

• the dagger involution is time-reversal, that is $\omega^{\dagger}_{t}:=\omega_{T-t},$

then for a given path

$\displaystyle{\omega=(\omega_{0}=a_{0}\overset{\tau_{0}}{\longrightarrow} a_{1} \overset{\tau_{1}}{\longrightarrow}\cdots \overset{\tau_{N}}{\longrightarrow} a_{N}=\omega_{T})\in\Omega}$

the logarithmic ratio $R(\omega)$ decomposes into ‘variation of self-information’ and ‘cumulative skewness’ along $\omega$ :

$\displaystyle{ R(\omega)=\underbrace{\Big(\ln\pi_{a_0}(0)-\ln\pi_{a_N}(T) \Big)}_{\Delta i(\omega)}-\underbrace{\sum_{j=1}^{N}\ln\frac{\gamma_{a_{j}a_{j-1}}(\tau_{j})}{\gamma_{a_{j-1}a_{j}}(\tau_{j})}}_{\Sigma(\omega)}.}$

This is easy to see if one writes the probability of a path explicitly as

$\displaystyle{p(\omega)=\pi_{a_{0}}(0)\left[\prod_{j=1}^{N}\phi_{a_{j-1}}(\tau_{j-1},\tau_{j})\gamma_{a_{j-1}a_{j}}(\tau_{j})\right]\phi_{a_{N}}(\tau_{N},T)}$

where

$\displaystyle{ \phi_{a}(\tau,\tau')=\phi_{a}(\tau',\tau)=\exp\Big(-\sum_{b\neq a}\int_{\tau}^{\tau'}dt\, \gamma_{a b}(t)\Big)}$

is the probability that the process remains in the state $a$ between the times $\tau$ and $\tau'$ . It follows from the above lemma that

Theorem. Let $(\Omega,\mathcal{T},p)$ be a Markov process and let $i,\Sigma:\Omega\rightarrow \mathbb{R}$ be defined as above. Then we have

1. The detailed fluctuation theorem:

$\forall A\in\mathbb{R}, p\big((\Delta i-\Sigma)^{-1}(-A) \big)=e^{-A}p \big((\Delta i-\Sigma)^{-1}(A) \big)$

2. The integral fluctuation theorem:

$\int_{\Omega} d p(\omega)\,e^{-\Delta i(\omega)+\Sigma(\omega)}=1$

3. The ‘Second Law’ inequality:

$\displaystyle{ \Delta S:=\int_{\Omega} d p(\omega)\,\Delta i(\omega)\geq \int_{\Omega} d p(\omega)\,\Sigma(\omega)}$

The same theorem can be formulated for other kinds of Markov processes as well, including diffusion processes (in which case it follows from the Girsanov theorem).

References

Landauer’s principle was introduced here:

• [Landauer1961] R. Landauer, Irreversibility and heat generation in the computing process}, IBM Journal of Research and Development 5, (1961) 183–191.

and is now being verified experimentally by various groups worldwide.

The ‘fundamental theorem of natural selection’ was derived by Fisher in his book:

• [Fisher1930] R. Fisher, The Genetical Theory of Natural Selection, Clarendon Press, Oxford, 1930.

His derivation has long been considered obscure, even perhaps wrong, but apparently the theorem is now well accepted. I believe the first Markovian models of genetic evolution appeared here:

• [Fisher1922] R. A. Fisher, On the dominance ratio, Proc. Roy. Soc. Edinb. 42 (1922), 321–341.

• [Wright1931] S. Wright, Evolution in Mendelian populations, Genetics 16 (1931), 97–159.

Fluctuation theorems are reviewed here:

• [Sevick2008] E. Sevick, R. Prabhakar, S. R. Williams, and D. J. Searles, Fluctuation theorems, Ann. Rev. Phys. Chem. 59 (2008), 603–633.

Two of the key ideas for the ‘detailed fluctuation theorem’ discussed here are due to Crooks:

• [Crooks1999] Gavin Crooks, The entropy production fluctuation theorem and the nonequilibrium work relation for free energy differences, Phys. Rev. E 60 (1999), 2721–2726.

who identified $(E_{a}(\tau_{j})-E_{a}(\tau_{j-1}))$ as heat, and Seifert:

• [Seifert2005] Udo Seifert, Entropy production along a stochastic trajectory and an integral fluctuation theorem, Phys. Rev. Lett. 95 (2005), 4.

who understood the relevance of the self-information in this context.

The connection between statistical physics and evolutionary biology is discussed here:

• [Sella2005] G. Sella and A.E. Hirsh, The application of statistical physics to evolutionary biology, Proc. Nat. Acad. Sci. USA 102 (2005), 9541–9546.

and the ‘fitness flux theorem’ is derived in

• [Mustonen2010] V. Mustonen and M. Lässig, Fitness flux and ubiquity of adaptive evolution, Proc. Nat. Acad. Sci. USA 107 (2010), 4248–4253.

Schrödinger’s famous discussion of the physical nature of life was published here:

• [Schrödinger1944] E. Schrödinger, What is Life?, Cambridge University Press, Cambridge, 1944.

]]>