Network Theory (Part 9)

jointly written with Brendan Fong

Last time we reviewed the rate equation and the master equation. Both of them describe processes where things of various kinds can react and turn into other things. But:

• In the rate equation, we assume the number of things varies continuously and is known precisely.

• In the master equation, we assume the number of things varies discretely and is known only probabilistically.

This should remind you of the difference between classical mechanics and quantum mechanics. But the master equation is not quantum, it’s stochastic: it involves probabilities, but there’s no uncertainty principle going on.

Still, a lot of the math is similar.

Now, given an equilibrium solution to the rate equation—one that doesn’t change with time—we’ll try to find a solution to the master equation with the same property. We won’t always succeed—but we often can! The theorem saying how was proved here:

• D. F. Anderson, G. Craciun and T. G. Kurtz, Product-form stationary distributions for deficiency zero chemical reaction networks.

To emphasize the analogy to quantum mechanics, we’ll translate their proof into the language of annihilation and creation operators. In particular, our equilibrium solution of the master equation is just like what people call a ‘coherent state’ in quantum mechanics.

So, if you know about quantum mechanics and coherent states, you should be happy. But if you don’t, fear not!—we’re not assuming you do.

The rate equation

To construct our equilibrium solution of the master equation, we need a special type of solution to our rate equation. We call this type a ‘complex balanced solution’. This means that not only is the net rate of production of each species zero, but the net rate of production of each possible bunch of species is zero.

Before we make this more precise, let’s remind ourselves of the basic setup.

We’ll consider a stochastic Petri net with a finite set S of species and a finite set T of transitions. For convenience let’s take S = \{1,\dots, k\}, so our species are numbered from 1 to k. Then each transition \tau has an input vector m(\tau) \in \mathbb{N}^k and output vector n(\tau) \in \mathbb{N}^k. These say how many things of each species go in, and how many go out. Each transition also has rate constant r(\tau) \in [0,\infty), which says how rapidly it happens.

The rate equation concerns a vector x(t) \in [0,\infty)^k whose ith component is the number of things of the ith species at time t. Note: we’re assuming this number of things varies continuously and is known precisely! This should remind you of classical mechanics. So, we’ll call x(t), or indeed any vector in [0,\infty)^k, a classical state.

The rate equation says how the classical state x(t) changes with time:

\displaystyle{  \frac{d x}{d t} = \sum_{\tau \in T} r(\tau)\, (n(\tau)-m(\tau)) \, x^{m(\tau)} }

You may wonder what x^{m(\tau)} means: after all, we’re taking a vector to a vector power! It’s just an abbreviation, which we’ve seen plenty of times before. If x \in \mathbb{R}^k is a list of numbers and m \in \mathbb{N}^k is a list of natural numbers, we define

x^m = x_1^{m_1} \cdots x_k^{m_k}

We’ll also use this notation when x is a list of operators.

Complex balance

The vectors m(\tau) and n(\tau) are examples of what chemists call complexes. A complex is a bunch of things of each species. For example, if the set S consists of three species, the complex (1,0,5) is a bunch consisting of one thing of the first species, none of the second species, and five of the third species.

For our Petri net, the set of complexes is the set \mathbb{N}^k, and the complexes of particular interest are the input complex m(\tau) and the output complex n(\tau) of each transition \tau.

We say a classical state c \in [0,\infty)^k is complex balanced if for all complexes \kappa \in \mathbb{N}^k we have

\displaystyle{ \sum_{\{\tau : m(\tau) = \kappa\}} r(\tau) c^{m(\tau)} =\sum_{\{\tau : n(\tau) = \kappa\}} r(\tau) c^{m(\tau)}  }

The left hand side of this equation, which sums over the transitions with input complex \kappa, gives the rate of consumption of the complex \kappa. The right hand side, which sums over the transitions with output complex \kappa, gives the rate of production of \kappa . So, this equation requires that the net rate of production of the complex \kappa is zero in the classical state c .

Puzzle. Show that if a classical state c is complex balanced, and we set x(t) = c for all t, then x(t) is a solution of the rate equation.

Since x(t) doesn’t change with time here, we call it an equilibrium solution of the rate equation. Since x(t) = c is complex balanced, we call it complex balanced equilibrium solution.

The master equation

We’ve seen that any complex balanced classical state gives an equilibrium solution of the rate equation. The Anderson–Craciun–Kurtz theorem says that it also gives an equilibrium solution of the master equation.

The master equation concerns a formal power series

\displaystyle{ \Psi(t) = \sum_{n \in \mathbb{N}^k} \psi_n(t) z^n }

where

z^n = z_1^{n_1} \cdots z_k^{n_k}

and

\psi_n(t) = \psi_{n_1, \dots,n_k}(t)

is the probability that at time t we have n_1 things of the first species, n_2 of the second species, and so on.

Note: now we’re assuming this number of things varies discretely and is known only probabilistically! So, we’ll call \Psi(t), or indeed any formal power series where the coefficients are probabilities summing to 1, a stochastic state. Earlier we just called it a ‘state’, but that would get confusing now: we’ve got classical states and stochastic states, and we’re trying to relate them.

The master equation says how the stochastic state \Psi(t) changes with time:

\displaystyle{ \frac{d}{d t} \Psi(t) = H \Psi(t) }

where the Hamiltonian H is:

\displaystyle{ H = \sum_{\tau \in T} r(\tau) \, \left({a^\dagger}^{n(\tau)} - {a^\dagger}^{m(\tau)} \right) \, a^{m(\tau)}  \label{master} }

The notation here is designed to neatly summarize some big products of annihilation and creation operators. For any vector n \in \mathbb{N}^k, we have

a^n = a_1^{n_1} \cdots  a_k^{n_k}

and

\displaystyle{  {a^\dagger}^n = {a_1^\dagger }^{n_1} \cdots  {a_k^\dagger}^{n_k} }

Coherent states

Now suppose c \in [0,\infty)^k is a complex balanced equilibrium solution of the rate equation. We want to get an equilibrium solution of the master equation. How do we do it?

For any c \in [0,\infty)^k there is a stochastic state called a coherent state, defined by

\displaystyle{ \Psi_c = \frac{e^{c z}}{e^c} }

Here we are using some very terse abbreviations. Namely, we are defining

e^{c} = e^{c_1} \cdots e^{c_k}

and

e^{c z} = e^{c_1 z_1} \cdots e^{c_k z_k}

Equivalently,

\displaystyle{ e^{c z} = \sum_{n \in \mathbb{N}^k} \frac{c^n}{n!}z^n }

where c^n and z^n are defined as products in our usual way, and

n! = n_1! \, \cdots \, n_k!

Either way, if you unravel the abbrevations, here’s what you get:

\displaystyle{  \Psi_c = e^{-(c_1 + \cdots + c_k)} \, \sum_{n \in \mathbb{N}^k} \frac{c_1^{n_1} \cdots c_k^{n_k}} {n_1! \, \cdots \, n_k! } \, z_1^{n_1} \cdots z_k^{n_k} }

Maybe now you see why we like the abbreviations.

The name ‘coherent state’ comes from quantum mechanics. In quantum mechanics, we think of a coherent state \Psi_c as the ‘quantum state’ that best approximates the classical state c. But we’re not doing quantum mechanics now, we’re doing probability theory. \Psi_c isn’t a ‘quantum state’, it’s a stochastic state.

In probability theory, people like Poisson distributions. In the state \Psi_c, the probability of having n_i things of the ith species is equal to

\displaystyle{  e^{-c_i} \, \frac{c_i^{n_i}}{n_i!} }

This is precisely the definition of a Poisson distribution with mean equal to c_i. We can multiply a bunch of factors like this, one for each species, to get

\displaystyle{ e^{-c} \frac{c^n}{n!} }

This is the probability of having n_1 things of the first species, n_2 things of the second, and so on, in the state \Psi_c. So, the state \Psi_c is a product of independent Poisson distributions. In particular, knowing how many things there are of one species says nothing all about how many things there are of any other species!

It is remarkable that such a simple state can give an equilibrium solution of the master equation, even for very complicated stochastic Petri nets. But it’s true—at least if c is complex balanced.

The Anderson–Craciun–Kurtz theorem

Now we’re ready to state and prove the big result:

Theorem (Anderson–Craciun–Kurtz). Suppose c \in [0,\infty)^k is a complex balanced equilibrium solution of the rate equation. Then H \Psi_c = 0.

It follows that \Psi_c is an equilibrium solution of the master equation. In other words, if we take \Psi(t) = \Psi_c for all times t, the master equation holds:

\displaystyle{ \frac{d}{d t} \Psi(t) = H \Psi(t) }

since both sides are zero.

Proof. To prove the Anderson–Craciun–Kurtz theorem, we just need to show that H \Psi_c = 0. Since \Psi_c is a constant times e^{c z}, it suffices to show H e^{c z} = 0. Remember that

\displaystyle{ H e^{c z} =  \sum_{\tau \in T} r(\tau) \left( {a^\dagger}^{n(\tau)} -{a^\dagger}^{m(\tau)} \right) \, a^{m(\tau)} \, e^{c z} }

Since the annihilation operator a_i is given by differentiation with respect to z_i, while the creation operator a^\dagger_i is just multiplying by z_i, we have:

\displaystyle{ H e^{c z} = \sum_{\tau \in T} r(\tau) \, c^{m(\tau)} \left( z^{n(\tau)} - z^{m(\tau)} \right) e^{c z} }

Expanding out e^{c z} we get:

\displaystyle{ H e^{c z} = \sum_{i \in \mathbb{N}^k} \sum_{\tau \in T} r(\tau)c^{m(\tau)}\left(z^{n(\tau)}\frac{c^i}{i!}z^i - z^{m(\tau)}\frac{c^i}{i!}z^i\right) }

Shifting indices and defining negative powers to be zero:

\displaystyle{ H e^{c z}  = \sum_{i \in \mathbb{N}^k} \sum_{\tau \in T} r(\tau)c^{m(\tau)}\left(\frac{c^{i-n(\tau)}}{(i-n(\tau))!}z^i - \frac{c^{i-m(\tau)}}{(i-m(\tau))!}z^i\right) }

So, to show H e^{c z} = 0, we need to show this:

\displaystyle{ \sum_{i \in \mathbb{N}^k} \sum_{\tau \in T} r(\tau)c^{m(\tau)}\frac{c^{i-n(\tau)}}{(i-n(\tau))!}z^i =\sum_{i \in \mathbb{N}^k} \sum_{\tau \in T} r(\tau)c^{m(\tau)}\frac{c^{i-m(\tau)}}{(i-m(\tau))!}z^i }

We do this by splitting the sum over T according to output and then input complexes, making use of the complex balanced condition:

\displaystyle{ \sum_{i \in \mathbb{N}^k} \sum_{\kappa \in \mathbb{N}^k} \sum_{\{\tau : n(\tau)=\kappa\}}  r(\tau)c^{m(\tau)}\frac{c^{i-n(\tau)}}{(i-n(\tau))!} \, z^i  = }

\displaystyle{ \sum_{i \in \mathbb{N}^k} \sum_{\kappa \in \mathbb{N}^k} \frac{c^{i-\kappa}}{(i-\kappa)!}\, z^i \sum_{\{\tau : n(\tau) = \kappa\}}  r(\tau)c^{m(\tau)} = }

\displaystyle{\sum_{i \in \mathbb{N}^k} \sum_{\kappa \in \mathbb{N}^k} \frac{c^{i-\kappa}}{(i-\kappa)!}\, z^i \sum_{\{\tau : m(\tau) = \kappa\}}  r(\tau)c^{m(\tau)}  = }

\displaystyle{ \sum_{i \in \mathbb{N}^k} \sum_{\kappa \in \mathbb{N}^k} \sum_{\{\tau : m(\tau) = \kappa\}}  r(\tau)c^{m(\tau)}\frac{c^{i-m(\tau)}}{(i-m(\tau))!}\, z^i }

This completes the proof! It’s just algebra, but it seems a bit magical, so we’re trying to understand it better.

I hope you see how amazing this result is. If you know quantum mechanics and coherent states you’ll understand what I mean. A coherent state is the "best quantum approximation" to a classical state, but we don’t expect this quantum state to be exactly time-independent when the corresponding classical state is, except in very special cases, like when the Hamiltonian is quadratic in the creation and annihilation operators. Here we are getting a result like that much more generally… but only given the "complex balanced" condition.

An example

We’ve already seen one example of the theorem, back in Part 7. We had this stochastic Petri net:

We saw that the rate equation is just the logistic equation, familiar from population biology. The equilibrium solution is complex balanced, because pairs of amoebas are getting created at the same rate as they’re getting destroyed, and single amoebas are getting created at the same rate as they’re getting destroyed.

So, the Anderson–Craciun–Kurtz theorem guarantees that there’s an equilibrium solution of the master equation where the number of amoebas is distributed according to a Poisson distribution. And, we actually checked that this was true!

Next time we’ll look at another example.

56 Responses to Network Theory (Part 9)

  1. Many thanks for your very readable exposition.

    I don’t know if you want to be alerted about trivial typos this way, but if you do: In the equation for a complex balanced equilibrium solution the m(\tau) on the right-hand side should be an n(\tau).

    • Ah, I should have done the exercise before guessing what the equation should have been. I am glad this comment is in moderation and hope it stays there until I have actually done the exercise so that perhaps I can avoid the humiliation :-)

    • John Baez says:

      Gustav wrote:

      I don’t know if you want to be alerted about trivial typos this way…

      I definitely do! All these blog entries will eventually become some sort of paper or book—you can find them all in one place here—so I’m very eager for corrections, and also very eager for people to do and even write solutions to the exercises. David Corfield has been the champion at the latter so far.

      Ah, I should have done the exercise before guessing what the equation should have been. I am glad this comment is in moderation and hope it stays there until I have actually done the exercise so that perhaps I can avoid the humiliation :-)

      Sorry, Gustav—I’m so desperate for comments on this rather technical post that I’m going to approve your first comment even if you wish I wouldn’t! No humiliation: just another good exercise for the readers out there. What should the complex balanced condition say, to ensure that the Puzzle can be solved? And why?

  2. Graham says:

    In a Markov process, there is a condition called ‘detailed balance’ (http://en.wikipedia.org/wiki/Detailed_balance). If that holds, the process is time-reversible. If understand this blog correctly, you have a Markov process whose states are all the complexes. Is that right? Anyway, what is the relation between complex balanced and detailed balance? They look similar…

    BTW, in your equation defining complex balanced, there is an m and an n on the rhs, I think it should be two n’s.

    • John Baez says:

      Note, Graham, that your proposed correction is exactly what Gustav proposed, only to recant later.

      Indeed, anyone in tune with the ‘tao of mathematics’ needs to have that sense of symmetry that instinctively rebels against an equation like this:

      \displaystyle{ \sum_{\{\tau : m(\tau) = \kappa\}} r(\tau) c^{m(\tau)} =\sum_{\{\tau : n(\tau) = \kappa\}} r(\tau) c^{m(\tau)}  }

      How come we see m twice at left, but an m and an n only once at right?

      Well, it’s actually got to be that way!

      Remember, the rate equation says

      \displaystyle{  \frac{d x}{d t} = \sum_{\tau \in T} r(\tau)\, (n(\tau)-m(\tau)) \, x^{m(\tau)} }

      Namely: the net rate of production of each species x_i is a sum over transitions \tau \in T. For each transition, we get a term equal to:

      • the rate constant of that transition: r(\tau),

      times

      • the net effect of that transition: the number of items of that species that are outputs of that transition, minus the number that are inputs: n_i(\tau)-m_i(\tau)).

      times

      • the product of numbers of species that show up as inputs: x^{m(\tau)}.

      The last factor arises because how often a transition occurs depends on how many of its inputs are present. There’s an asymmetry built in here: the inputs matter in a way that the outputs don’t!

      We can see this asymmetry in the rate equation:

      \displaystyle{  \frac{d x}{d t} = \sum_{\tau \in T} r(\tau)\, (n(\tau)-m(\tau)) \, x^{m(\tau)} }

      Namely, m shows up twice but n shows up just once.

      Clearly we’ll get an equilibrium solution

      \displaystyle{  \frac{d x}{d t} } = 0

      if and only if we have

      \displaystyle{ \sum_{\tau \in T} r(\tau) m(\tau)  x^{m(\tau)}  = \sum_{\tau \in T} r(\tau) n(\tau)  x^{m(\tau)} }

      If x = c, the Puzzle claims that this equation follows from the complex balanced condition:

      \displaystyle{ \sum_{\{\tau : m(\tau) = \kappa\}} r(\tau) c^{m(\tau)} =\sum_{\{\tau : n(\tau) = \kappa\}} r(\tau) c^{m(\tau)}  }

      which we assume holds for all \kappa \in \mathbb{N}^k.

      So you can see where the asymmetry sneaks in!

  3. Graham, you are asking an interesting question. The particular example of the amoeba model given in the blog post happens to satisfy both complex balance and detailed balance. However that is just an accident. Take for example the rock-paper-scissors model where there are three species which can convert into each other in a cyclic manner, i.e., individuals of species 1 can turn into species 2, 2 into 3 and 3 back into 1. That model has complex balanced states but the corresponding equilibrium solutions do not satisfy detailed balance. It is too late now, but if you like I can supply details of that example tomorrow.

    Detailed balance and complex balance have a very different flavour because detailed balance is about the flow of probability forth and back between two states of the Markov chain, whereas complex balance is about the flow in and out of the species.

    It would be nice to think more about the class of Petri nets that satisfy both detailed balance and complex balance.

    • John Baez says:

      Thanks for your helpful answer, Gustav! I think Graham and I can easily fill in the details.

      If we have three species, say 1, 2, and 3, and three transitions

      1 → 2
      2 → 3
      3 → 1

      with equal reaction rates, then our stochastic Petri net will have an equilibrium solution of the rate equation where there are equal numbers of species 1, 2, and 3. That’s fairly obvious.

      And this equilibrium will be complex balanced. Why? Because only three complexes appear as inputs or outputs of the transitions above—the complexes consisting of a single species. Moreover, in this equilibrium solution each of these three complexes are being produced at a rate equal to the rate their being destroyed. That’s obvious.

      Indeed any equilibrium solution of the rate equation is complex balanced if the only complexes appearing as inputs or outputs are complexes consisting of a single species!

      However, this equilibrium is not ‘detailed balanced’, because we have 1′s turning directly into 2′s but not 2′s turning directly into 1′s.

      I should work this example into the blog entries somehow!

    • Graham says:

      Thanks Gustav and John. I realise now that I had already encountered the difference between detailed balance and complex balance in the context of mutation of DNA where the species are the bases A,C,G,T, which is modelled as a Markov process acting on {A,C,G,T}. John has described the simplest Jukes-Cantor model in some earlier blog. The most complicated model that is commonly used is the general time reversible or GTR model, which satisfies the detailed balance condition. But there is no biological reason to suppose that this condition should hold. So there is some interest in using non-time reversible models. Then, at equilibrium, you can get cycles like A->G->C->A or A->C->G->T->A occuring (though they will typically be a small part of what is going on, not the ‘pure’ cycle on {1,2,3} in the example above).

  4. Peter Morgan says:

    Your references to the relationship between your approach here (and in part 5, where you give a relatively extended description) and ordinary quantum theory don’t seem as clear as they might be. I note particularly that you work with number operators almost exclusively, a^\dagger a, whereas elementary QT often works with only the displacement operator a+a^\dagger. Thus, in QT we obtain the Gaussian characteristic function (probability generating function, or p.g.f.)

    \displaystyle{ e^{\alpha^*\alpha}=e^{-\lambda^2/2+i(\alpha+\alpha^*)\lambda}, \displaystyle}

    whereas to obtain the Poissonian p.g.f. in QT, we use the same quantum state with a different observable,

    \displaystyle{e^{\alpha^*\alpha}=e^{-\alpha^*\alpha(1-e^{i\lambda})}}.

    In part 5, you stated that states in your approach are linear and that states in QT are amplitudes, but in the expressions above the states are linear operators acting on the operator-valued generating functions e^{i\lambda(a+a^\dagger)} and e^{i\lambda a^\dagger a}, both of which can be written as \mathrm{Trace}[\hat A\hat\rho], with

    \displaystyle{ \hat\rho=e^{\alpha a^\dagger}\left|0\right>\left<0\right|e^{\alpha^*a}/e^{\alpha^*\alpha} }.

    I prefer this way to make the connection. Wha'd'ya think? [I hope the LaTeX works out, because I've not tried to embed LaTeX here before, and there's no preview.]

    • Peter Morgan says:

      They *did* parse in LaTeX. I checked before posting it. I hope *you* can fix it, assuming you decide to let the comment stand.

      • John Baez says:

        The comments that didn’t parse began with a command I’ve never seen before:

        \left/

        Maybe it would work if it had a corresponding

        \right/

        but it didn’t. I’ve fixed them. I find that in this fairly crappy setup longish equations are easier to read if they have their own line, and I use

        \displaystyle{ }

        if they’re tall, e.g. contain exponentials or sums or fractions.

        Needless to say—but I’ll say it in case any newbies are reading this—equations must be surrounded by

        $latex $

        to have a chance of working at all. Luckily you knew that!

    • John Baez says:

      Peter wrote:

      Your references to the relationship between your approach here (and in part 5, where you give a relatively extended description) and ordinary quantum theory don’t seem as clear as they might be.

      Unfortunately I don’t really understand your comments either. So, we’re probably coming from different places. But I’ll say a few things.

      I note particularly that you work with number operators almost exclusively, a^\dagger a, whereas elementary QT often works with only the displacement operator a+a^\dagger.

      In quantum theory a+a^\dagger is important because it’s self-adjoint. In quantum physics self-adjoint operators are important for two reasons. First, they are observables. Second, when you multiply them by i you get skew-adjoint operators, which generate one-parameter groups of unitary operators, which describe symmetries. So, any observable O gives a one-parameter unitary group \exp(i t O).

      In stochastic physics neither of these reasons applies. First, our space of states is not a Hilbert space but a space of functions L^1(S), and only real-valued functions on S count as observables. Second, symmetries are described not by unitary operators but by stochastic operators—and one-parameter groups of stochastic operators are generated not by skew-adjoint operators, but by infinitesimal stochastic operators.

      As you note, I explained some of this stuff back in Part 5… but not all of it! For example, I didn’t even mention observables. I’ll try to do a better job of this soon.

      But the executive summary is that a + a^\dagger is not important in the stochastic analogue of Fock space physics, being neither an observable nor infinitesimal stochastic nor stochastic. On the other hand, a^\dagger a is an observable, and we also need its falling powers to construct infinitesimal stochastic operators as in Part 7.

      In part 5, you stated that states in your approach are linear and that states in QT are amplitudes…

      I didn’t say that, and it doesn’t sound right.

      Also, I don’t know what this sort of equation means:

      \displaystyle{ e^{\alpha^*\alpha}=e^{-\lambda^2/2+i(\alpha+\alpha^*)\lambda}, \displaystyle}

      What’s \alpha? A number or an annihilation operator? What’s \lambda, and why are we relating \alpha and \lambda this way?

      • Peter Morgan says:

        The LaTeX was mangled totally by wordpress. Since I can’t preview it and I can’t correct it I won’t try again. Like I say, LaTex parsed what I typed, wordpress didn’t. What you corrected it to is not what I had.

        Overnight it occurs to me to think of what you have as states over a commutative algebra of observables, generated by the number operators. That’s QM. Of course therefore you have a representation on polynomials. That’s not so much QM. One could introduce \left|n\right>\left<n\right|\equiv x^n, in which case the a and a^\dagger would be superoperators on the density matrices. There must be more ways of talking about this.

        • phorgyphynance says:

          Hi Peter. Another option is to skip discussions on the blog and discuss the articles on the discussion forum.

          John probably doesn’t prefer that, but when you have RSS, it is irrelevant where the actual comment appears. The Azimuth forum has a preview feature and the syntax is much closer to latex.

          Here is the thread for this blog post:

          http://www.math.ntnu.no/~stacey/Mathforge/Azimuth/comments.php?DiscussionID=823

          A better solution would be for this blog to adopt itex2mml in order to make it fully compatible with both the Azimuth wiki and the Azimuth blog. Andrew already demonstrated that it works with WordPress, so I’m not sure the hang up.

          If we did that, you could even use the forum to preview a comment and once it renders correctly, copy and paste to the blog if you prefer commenting on the blog.

        • John Baez says:

          Phorgyfinance wrote:

          John probably doesn’t prefer that…

          Right: this blog here is a better place to talk about blog articles after they’re written. Splintering the discussion isn’t good.

          A better solution would be for this blog to adopt itex2mml in order to make it fully compatible with both the Azimuth wiki and the Azimuth blog. Andrew already demonstrated that it works with WordPress, so I’m not sure the hang up.

          Perhaps when we last discussed this it seemed a fair number of readers would need to ‘install fonts’ to read the math if we used itex2html? That would be enough to make me not want to do it, since I don’t want to limit the conversations on the blog to people who can do that sort of stuff.

          In general I’d much rather leave software technology to people who like it better than me! But there’s a catch: for the Azimuth Project, we need a blog that everyone in the world can easily read.

          The problem is, the world has a small number of übergeeks who can easily ‘install fonts’, ‘choose a text filter’ (as required on the n-Category Café), and other such things… and these people have little understanding of people who are stuck on lower levels of the technological ladder. 80-90% of internet users don’t know how to use control-F to search for words on webpages. I’m somewhere in between, so it’s my job to resist the urge to choose the ‘best’ software, when that software isn’t something ordinary folks will use.

          But, I’m always willing to keep revisiting these issues and keep optimizing things as times change. Someday most everyone’s browser will understand MathML. Is that day now?

          Anyway, Peter Morgan easily figured out how to use TeX here, after one misfire.

        • Eric says:

          It probably goes without saying that a discussion forum is better for discussions than a blog. By there nature, blogs are not designed for much more than a single layer of comments with an occasional comment on a comment. Just witness the horrible threading here.

          If you want to keep the comments where the article appears, why not post the article to the forum instead? The forum is grossly under used for the value it adds.

          A blog is for preaching from a soap box. If you want effective discussions, use a discussion forum.

          PS: if someone can read the wiki without installing fonts, they should be able to read the blog without installing fonts. Similarly, if they need to install fonts to read the blog, they’d need to install fonts to read the wiki. I think.

        • John Baez says:

          I’m preaching on a soapbox here, trying to get everyone interested in various things. So, the most important thing is that everyone can read what’s said here.

          If people want a place where everyone can start discussions and use TeX to their heart’s content, yes, the forum is better. Everyone should join the Azimuth Forum! It’s a great place.

        • John Baez says:

          I fixed the typo ‘&uumlbergeek’ above (should have been übergeek), but Blake Stacey had already promoted it to a definition over on Google+:

          &uumlbergeek, noun: 1. A person who has spent so much time dealing with fonts and other typesetting issues that they can parse mistyped TeX or HTML entities in their head. A person you might be happy to have around when you need an obscure question answered, but most decidedly not representative of the general reader population. 2. A person who is so familiar with the ways HTML can be mistyped that they instinctively find jokes about “&uumlbergeeks” funny, cf. those who know Elizabethan slang for syphilis and cuckoldry and find their experience of Shakespeare enhanced thereby.

        • Blake Stacey says:

          Sorry if that came across as harping excessively on a single, simple typo — I just love inadvertent word coinages!

      • Peter Morgan says:

        Gotta not give up. The state I used in my rejected LaTeX was the Trace[\hat A\hat\rho], with the coherent state density operator \hat\rho, that I gave in my original comment. Taking \hat A to be the operator-valued generating functions e^{i\lambda(a+a^\dagger)} and e^{i\lambda a^\dagger a}, respectively, gives the probability generating functions e^{-\lambda^2/2+i(\alpha+\alpha^*)\lambda} and e^{-\alpha^*\alpha(1-e^{i\lambda})}, Gaussian and Poissonian respectively.

        It seems to me that your space of state *vectors* is given by polynomials P(x) (and perhaps a closure in a linear norm). Your space of *states*, maps from the algebra of operators generated by polynomials in the differential operators a^\dagger a to expected values (perhaps closed in the same or in a different linear norm), is given by the zero-degree part of F(a^\dagger a)P(x).

        You use the noncommutative algebra of raising and lowering operators to construct states, *not* to generate observables. We would have to ask questions other than “how many rabbits are there?” Disturbing questions, perhaps?

        • John Baez says:

          I’ll try to answer your questions more carefully after I think about them.

          I have considered the idea that we should generalize the concept of ‘observable’ in stochastic mechanics to include observables that aren’t diagonal in the standard basis. In the case of Fock space, which is what we’re studying now, that means observables that aren’t diagonal in the basis of monomials

          z^n := z_1^{n_1} \cdots z_k^{n_k}

          In other words, that means observables that aren’t just functions of the number operators

          N_i = a_i^\dagger a_i \qquad  i = 1, \dots, k

          As you point out, including these ‘nondiagonal’ observables would make our algebra of observables noncommutative… making stochastic mechanics even more closely resemble quantum mechanics. But these other observables would let us ask questions about that state that aren’t just about the number of species of each type.

          Disturbing questions, perhaps?

          Maybe so! But we should fearlessly explore this possibility.

          If all goes according to plan, Part 11 will include Brendan Fong’s proof of a version of Noether’s theorem for stochastic mechanics. But this particular version only applies to observables that are diagonal in the standard basis. So, that will give us something to think about.

  5. This is excellent turn-paging material, trying to figure out how the saga will resolve, and thinking simultaneously how we can apply the ideas.

    I am always interested in applying the Fokker-Planck version of the master equation in the natural sciences. My hot topic of the moment is trying to figure out CO2 residence times. I think I have a pretty solid argument which works out the deep diffusion in the carbon cycle:
    http://theoilconundrum.blogspot.com/2011/09/missing-carbon.html
    What relates to here is that I computed a detailed balance model using a continuous flow Petri net (i.e. an ideal canonical Markov model) which you can see in the diagram.

    Working the math at such a basic level is so useful on its own that I don’t understand why this kind of explanation is not more widespread.

    I also have my own Part 2 in this story.

    • John Baez says:

      WebHubTel wrote:

      This is excellent turn-paging material, trying to figure out how the saga will resolve, and thinking simultaneously how we can apply the ideas.

      Thanks so much! I’m afraid this part was a bit technical, and the technicalities may have obscured the truly jaw-dropping significance of the result. So, after I posted it, I added a passage which I quote here in case anyone read the article before I got around to it:

      I hope you see how amazing this result is. If you know quantum mechanics and coherent states you’ll understand what I mean. A coherent state is the “best quantum approximation” to a classical state, but we don’t expect this quantum state to be exactly time-independent when the corresponding classical state is, except in very special cases, like when the Hamiltonian is quadratic in the creation and annihilation operators. Here we are getting a result like that much more generally… but only given the “complex balanced” condition.

      As for how the saga will resolve, I’m afraid I have no idea, because it keeps growing faster than we can write it up! We have some more material to present on stochastic Petri nets and more general Markov processes, but then I want to take a sharp turn and discuss electrical circuits made of resistors from an absurdly highbrow point of view… and then discuss how they’re related to Markov processes: that’s pretty cool.

      But this is just the start…

      • Web Hub Tel says:

        For electrical circuits, I hope you talk about holes and electrons and the interesting detailed balance that goes on in semiconductors. The mass action law is essentially
        n p = n_i^2
        This says that the product of the electron concentration and the hole concentration is always equal to the square of the intrinsic carrier concentration. Is the pairing of a hole and an electron considered a complex?

  6. bentleyphysics9 says:

    I thought I’d point out more typos, etc. as I’m still chewing on the content.

    1. You should change “emphasizes” to “emphasize” in the sentence
    “To emphasizes the analogy to quantum mechanics …”
    2. The link to “Part 7″ following the example at the end of the entry appears to be broken.

  7. Ilya Surdin says:

    I’m sorry for the very basic question, but as part of trying to understand the complex balance definition, I’ve tried applying it to the wolf-rabbit example from previous posts.

    As the first complex to try on I’ve decided to take (rabbit, wolf) = (1, 0). So, on the LHS I get that only the birth transition satisfies the condition, and on the RHS we get no transition. Which means that to get a complex balanced state, we should either have r(birth) = 0 or number of rabbits in C should be 0. Which intuitively is incorrect. Where am I wrong?

    • John Baez says:

      That’s an interesting question! But before I answer it, let’s make sure everyone understands it. Solving this kind of problem is good practice, so I hope someone else can do it.

      Let’s look at the wolf-rabbit Petri net:

      Puzzle. Write (i,j) for a complex consisting of i rabbits and j wolves.

      What are al the input complexes of the above Petri net?

      What are the output complexes?

      Is it possible to find solutions of the rate equation in which the each of these complexes is produced (as an output) at the same rate at which it’s destroyed (as an input)? If so, what are these solutions like?

      Of course, the last question is asking about complex balanced equilibria.

      • David Corfield says:

        The complexes with some wolves and no rabbits would require a zero death rate, and the complexes with some rabbits and no wolves would require a zero birth rate.

  8. Matías says:

    In the Agronomy faculty where I study the professors sometimes have problems with us the students accepting models based on differential equations with which you can state ridiculous things for, for example, a population of animals. So it’s quite nice to see a deep and powerful connection between the continuous and deterministic rates equations and some discrete stochastic ones.

    I was spelled by the simplicity of the Petri net for the logistic growth but I have one question about it: Can a state with a single amoeba pass to a state with zero without first passing to state with more amoebas? I hope not to bother you with so basic questions but I’m interested in stochastic models for predicting the probability of (local) extinctions (sometimes wanted, eg: plagues).

    Something particularly nice about this nets is that they provide a bridge between a story (or mechanistic account) of a process to a type of mathematical model (actually two). So please go on with these entries!

    • John Baez says:

      I’m glad you’re enjoying these posts, Matias! If you don’t mind me asking, where do you study?

      I was spelled by the simplicity of the Petri net for the logistic growth but I have one question about it: Can a state with a single amoeba pass to a state with zero without first passing to state with more amoebas?

      Let’s look at this Petri net:

      One amoeba can split into two, and two can fight leaving just one survivor. If you think about it, this means it’s impossible for a state with one amoeba to turn into a state with zero. It can’t do this in one step. It also can’t do it by passing to a state with more amoebas.

      So, this model is not very realistic: it’s impossible for an amoeba to die except through ‘competition’, which requires another amoeba.

      We could, of course, make the model more realistic by including another transition, ‘death’, with one amoeba as input and none as output.

      Here’s a puzzle for everyone:

      Puzzle: Could the rate equation for this new model have a complex balanced equilibrium?

      • Ilya Surdin says:

        Funnily, no, unless death rate is 0, because we’ll get equations:

        r(f)*1+r(d)*1 = r(c)
        r(c)*2 = r(f) * 2
        –> r(d) = 0.

        But we could add a creation transition, which has an amoeba is output an no inputs, which will balance it, but I don’t think this will represent the evolutionary model very well :)

        P.S. If there was a preview button for the comment I’d try latexing this.

        • John Baez says:

          Right! Since “death” takes the complex with 1 amoeba to the complex with 0 amoebas, we can’t have a nontrivial complex balanced equilibrium unless there’s also some way for a complex of 0 amoebas to become a complex with 1.

          This shows that the complex balance condition is quite special, not something we should expect generically!

          By the way: I’m not sure I understand what your complex balance conditions say, but they don’t look right to me. They should involve the number of amoebas, say x. Suppose r(f), r(c), r(d) are the rate constants for fission, competition and death. Then the complex balance conditions should be these:

          • This equation says that the complex consisting of 1 amoeba is created at the same rate it’s destroyed:

          r(c) x^2 = r(f) x + r(d) x

          It’s created by competition at the rate r(c) x^2, and destroyed by fission and death at the rate r(f) x + r(d) x.

          • This equation says that the complex consisting of 2 amoebas is created at the same rate it’s destroyed:

          r(f) x = r(c) x^2

          • This equation says that the complex consisting of 0 amoebas is created at the same rate it’s destroyed:

          r(d) x = 0

          The last equation is the problem: it can only hold in the trivial cases r(d) = 0 (no death) or x = 0 (no amoebas).

          (By the way: there’s no easy ‘instant’ way for me to get a preview button for comments. I can’t get a preview button without paying money and figuring out how to do various things like ‘install plugins’, and I haven’t gotten around to that. I am, however, happy to fix people’s latex. It’s less painful for me to do a little work each day than to spend a whole day doing a boring and frustrating task. This is an example of how people get trapped in suboptimal local maxima.)

        • Ilya Surdin says:

          I’m sorry, it was 6am and I was writing without a draft, so I made a mistake in the process, of remembering what I wrote yesterday at a different place.

      • While I agree with most of what has been written in answer to this puzzle, I still think the answer is yes. The solution c=0 is a complex balanced solution of the model with death and is the correct equilibrium solution that the system will approach in the long-term.

        +Matias, if you are interested in modelling extinction I can recommend reading chapter 6 in the book “Modelling Fluctuating Populations” by Nisbet and Gurney. It shows you in particular how to calculate the mean time to extinction using the concept of a quasi-stationary distribution.

      • John Baez says:

        Gustav wrote:

        While I agree with most of what has been written in answer to this puzzle, I still think the answer is yes. The solution c=0 is a complex balanced solution of the model with death…

        You’re right! I was being sloppy.

        Still, it’s worth noting that c = 0—no species of any kind—is a complex balanced solution for every stochastic Petri net. So, people often count this solution as ‘trivial’ and focus attention on finding nontrivial solutions.

        and is the correct equilibrium solution that the system will approach in the long-term.

        It’s an equilibrium solution, but whether the system will approach it depends on the initial conditions and the rate constants for fission, competition and death. If x(t) is the number of amoebas at time t, the rate equation says

        \displaystyle{ \frac{d x}{d t} = (r(f) - r(d)) x - r(c) x^2 }

        and I think this will always have a stable equilibrium with x > 0 if r(f) \geq r(d) and r(c) \geq 0.

        I don’t mean to be argumentative here, but sometimes it takes a long discussion to find the whole truth and nothing but the truth.

        • I think your discussion about whether or not the state with no amoeba is the state that will be approached in the long run or not is a valuable one because it exhibits nicely a big difference between deterministic and stochastic models. While the deterministic model can indeed have a stable non-zero fixed point, this is not the case with the stochastic model. There will always eventually be a stochastic fluctuation large enough so that the population goes extinct by accident! And because there is no process that creates a new individual from none, it will then stay extinct forever.

        • John Baez says:

          Good point, Gustav! I guess that for stochastic Petri nets with one species, either the expected population goes to +\infty as t \to +\infty, or the population goes extinct with probability one in the t \to +\infty limit. This is just a guess.

          (The problems you had with finding the reply button earlier may be related to the fact that I was busy editing and re-editing my answer—the one you wanted to reply to. I don’t know. Also, note that there’s a limit on how much ‘nesting’ of comments on comments is allowed here: otherwise the columns get too skinny! So, there’s no reply button under this comment, and there never will be. When this happens, you’re just supposed to go up the comment tree until you find the first reply button.)

        • In the language of quantum mechanics the phenomenon that fluctuations can drive you away from classically stable states, is knows as tunneling. However is there also a quantum mechanics analog of the effect that one can get trapped in the extinction state? Presumably not, because a Hermitian Hamiltonian will not allow an asymmetry between creation and annihilation, right? Hence the zero point fluctuations in quantum mechanics. Too bad we don’t have those in ecology.

        • Graham says:

          Sometimes people include immigration in population models. Then there is a transition that takes zero to one or more.

        • John Baez says:

          Gustav wrote:

          Presumably not, because a Hermitian Hamiltonian will not allow an asymmetry between creation and annihilation, right? Hence the zero point fluctuations in quantum mechanics. Too bad we don’t have those in ecology.

          Spontaneous generation as the adjoint of extinction? Interesting idea. You’re making me think of this ‘reciprocity’ principle in quantum mechanics:

          In quantum mechanics the Hamiltonian must be self-adjoint:

          \langle \phi, H \psi \rangle = \overline{ \langle \psi , H \phi \rangle}

          so if we’re allowed to make the approximation

          e^{i t H} \approx 1 + i t H + \cdots

          for small times, we see that if \psi and \phi are orthogonal,

          |\langle \phi, e^{i t H} \psi \rangle |^2 \approx  |\langle \psi, e^{i t H} \phi \rangle |^2

          which says that the probability for the state \psi to evolve to the state \phi is equal to the probability for \phi to evolve to \psi.

          On the other hand, we have nothing like this principle in stochastic mechanics. Only for certain special stochastic Hamiltonians does the ability for one state to become a second state imply the ability for the second to go back to the first!

        • John Baez says:

          Graham wrote:

          Sometimes people include immigration in population models. Then there is a transition that takes zero to one or more.

          Great! A model without any real-world situation it applies to is a lonely, sad thing. But as Polyakov said, any sufficiently beautiful theory is, in some sense, true. It will always wind up applying to some real-world situation.

        • Matías says:

          Oh, I’ve got confused because I thought from the rate equation that the competition depended quadratically on the population size and so still be positive for single amoebas, but after taking a look at the master equation I now think it might be more correct to consider competition proportional to the second ‘falling’ power of the population size (and so, be zero for the single amoeba).

          Besides that, I should point to the fact that c=0 for all species is only an equilibrum for Petri nets that allow no specie to be created from the vacuum (or by migration), which is still a very general class, and easily distinguishable from nets outside that class.

          Baez, of course I don’t mind you asking, I study at the Buenos Aires university.

          Delius, thanks a lot for the recomendation, I have no access to the book now but will keep note for the future. When thinking about extinctions, I frame them under the more general concept of absorbent states (an state space region from which exiting has zero probability), which I picked from somewhere i don’t remember; now the concept of quasi-distribution seems similar, and very useful also, thanks for that too.

        • John Baez says:

          Matías wrote:

          Besides that, I should point to the fact that c=0 for all species is only an equilibrum for Petri nets that allow no specie to be created from the vacuum (or by migration), which is still a very general class, and easily distinguishable from nets outside that class.

          Good point! My mistake. I so rarely consider Petri nets that allow species to be created ‘from nothing’ that I tend to forget that they exist!

          I also made this mistake here:

          I guess that for stochastic Petri nets with one species, either the expected population goes to +\infty as t \to +\infty, or the population goes extinct with probability one in the t \to +\infty limit. This is just a guess.

          If we allow species to be created from nothing, the population can crash to zero due to a random fluctuation but then bounce back. So, I should limit my guess to the class of stochastic Petri nets that don’t let species be created from nothing.

          By the way, the singular form of ‘species’ is ‘species’.

        • Matías says:

          Is there any flaw with the following reasoning?

          The Petri Net of the example has two reactions, both of which take a positive input and leave a positive output, so they should conserve “positiveness” and so the model would predict no extinctions.

        • John Baez says:

          No flaw—that’s right!

    • What I continue to find hard to believe is the use of Logistic growth for oil production. Hydrocarbon molecules don’t reproduce so I have problems with using the Verhulst equation to derive a Logistic curve, and then calling that a Hubbert curve.

      \frac{dP}{dt}=rP\left(1 - \frac{P}{K}\right)

      The other problem with the Logistic argument is it goes toward a steady-state carrying capacity, K. Oil doesn’t reach a carrying capacity, as it keeps on depleting. Therefore it also won’t model extinction.

      • John Baez says:

        Perhaps in applications to oil production the logistic curve is being used merely as an example of a curve that starts near zero, goes up faster and faster for a while, then slows down and approaches a positive constant. Is there any evidence that more is involved than this? The “null hypothesis” could be that nothing more is involved: you can roughly fit any curve of this general sort with a logistic, and that’s all people are doing.

        • I think that is close to it. The fact that the derivative of the Logistic function can be algebraically manipulated in terms of itself holds no meaning by itself.

          Consider that the Fermi-Dirac distribution function also has the exact same form as a Logistic. Yet no one derives the Fermi-Dirac via its differential form. It has a deeper meaning that arises from a statistical distribution of energy levels.

          My own theory as to why the Hubbert Peak has that form has more to do with statistical variations in how fast we extract the oil which is dispersed over the entire world. There are some very simple formulations of dispersion which follow MaxEnt that will get the same Logistic function form and it has little to do with non-linear rate equations. The way I think about it is we are seeing statistical mechanics at a coarse graining scale.

          That is partly why I am fascinated by this topic. There may be some duality at work here.

  9. Last time Brendan showed us a proof of the Anderson-Craciun-Kurtz theorem on equilibrium states. Today we’ll look at an example that illustrates this theorem. This example brings up an interesting ‘paradox’—or at least a puzzle.

  10. Back in Part 9, we explained when an equilibrium solution of the rate equation gives an equilibrium solution of the master equation [...]

  11. Brendan Fong and I have just now finally written up our proof of the Anderson–Craciun–Kurtz theorem: as a self-contained paper:

    • John Baez and Brendan Fong, Quantum techniques for studying equilibria in chemical reaction networks.

You can use HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 2,714 other followers