Network Theory (Part 23)

We’ve been looking at reaction networks, and we’re getting ready to find equilibrium solutions of the equations they give. To do this, we’ll need to connect them to another kind of network we’ve studied. A reaction network is something like this:

It’s a bunch of complexes, which are sums of basic building-blocks called species, together with arrows called transitions going between the complexes. If we know a number for each transition describing the rate at which it occurs, we get an equation called the ‘rate equation’. This describes how the amount of each species changes with time. We’ve been talking about this equation ever since the start of this series! Last time, we wrote it down in a new very compact form:

\displaystyle{ \frac{d x}{d t} = Y H x^Y }

Here x is a vector whose components are the amounts of each species, while H and Y are certain matrices.

But now suppose we forget how each complex is made of species! Suppose we just think of them as abstract things in their own right, like numbered boxes:

We can use these boxes to describe states of some system. The arrows still describe transitions, but now we think of these as ways for the system to hop from one state to another. Say we know a number for each transition describing the probability per time at which it occurs:

Then we get a ‘Markov process’—or in other words, a random walk where our system hops from one state to another. If \psi is the probability distribution saying how likely the system is to be in each state, this Markov process is described by this equation:

\displaystyle{ \frac{d \psi}{d t} = H \psi }

This is simpler than the rate equation, because it’s linear. But the matrix H is the same—we’ll see that explicitly later on today.

What’s the point? Well, our ultimate goal is to prove the deficiency zero theorem, which gives equilibrium solutions of the rate equation. That means finding x with

Y H x^Y = 0

Today we’ll find all equilibria for the Markov process, meaning all \psi with

H \psi = 0

Then next time we’ll show some of these have the form

\psi = x^Y

So, we’ll get

H x^Y = 0

and thus

Y H x^Y = 0

as desired!

So, let’s get to to work.

The Markov process of a graph with rates

We’ve been looking at stochastic reaction networks, which are things like this:

However, we can build a Markov process starting from just part of this information:

Let’s call this thing a ‘graph with rates’, for lack of a better name. We’ve been calling the things in K ‘complexes’, but now we’ll think of them as ‘states’. So:

Definition. A graph with rates consists of:

• a finite set of states K,

• a finite set of transitions T,

• a map r: T \to (0,\infty) giving a rate constant for each transition,

• source and target maps s,t : T \to K saying where each transition starts and ends.

Starting from this, we can get a Markov process describing how a probability distribution \psi on our set of states will change with time. As usual, this Markov process is described by a master equation:

\displaystyle{ \frac{d \psi}{d t} = H \psi }

for some Hamiltonian:

H : \mathbb{R}^K \to \mathbb{R}^K

What is this Hamiltonian, exactly? Let’s think of it as a matrix where H_{i j} is the probability per time for our system to hop from the state j to the state i. This looks backwards, but don’t blame me—blame the guys who invented the usual conventions for matrix algebra. Clearly if i \ne j this probability per time should be the sum of the rate constants of all transitions going from j to i:

\displaystyle{ i \ne j \quad \Rightarrow \quad H_{i j} = \sum_{\tau: j \to i} r(\tau) }

where we write \tau: j \to i when \tau is a transition with source j and target i.

Now, we saw in Part 11 that for a probability distribution to remain a probability distribution as it evolves in time according to the master equation, we need H to be infinitesimal stochastic: its off-diagonal entries must be nonnegative, and the sum of the entries in each column must be zero.

The first condition holds already, and the second one tells us what the diagonal entries must be. So, we’re basically done describing H. But we can summarize it this way:

Puzzle 1. Think of \mathbb{R}^K as the vector space consisting of finite linear combinations of elements \kappa \in K. Then show

\displaystyle{ H \kappa = \sum_{s(\tau) = \kappa} r(\tau) (t(\tau) - s(\tau)) }

Equilibrium solutions of the master equation

Now we’ll classify equilibrium solutions of the master equation, meaning \psi \in \mathbb{R}^K with

H \psi = 0

We’ll do only do this when our graph with rates is ‘weakly reversible’. This concept doesn’t actually depend on the rates, so let’s be general and say:

Definition. A graph is weakly reversible if for every edge \tau : i \to j, there is directed path going back from j to i, meaning that we have edges

\tau_1 : j \to j_1 , \quad \tau_2 : j_1 \to j_2 , \quad \dots, \quad \tau_n: j_{n-1} \to i

This graph with rates is not weakly reversible:

but this one is:

The good thing about the weakly reversible case is that we get one equilibrium solution of the master equation for each component of our graph, and all equilibrium solutions are linear combinations of these. This is not true in general! For example, this guy is not weakly reversible:

It has only one component, but the master equation has two linearly independent equilibrium solutions: one that vanishes except at the state 0, and one that vanishes except at the state 2.

The idea of a ‘component’ is supposed to be fairly intuitive—our graph falls apart into pieces called components—but we should make it precise. As explained in Part 21, the graphs we’re using here are directed multigraphs, meaning things like

s, t : E \to V

where E is the set of edges (our transitions) and V is the set of vertices (our states). There are actually two famous concepts of ‘component’ for graphs of this sort: ‘strongly connected’ components and ‘connected’ components. We only need connected components, but let me explain both concepts, in a futile attempt to slake your insatiable thirst for knowledge.

Two vertices i and j of a graph lie in the same strongly connected component iff you can find a directed path of edges from i to j and also one from j back to i.

Remember, a directed path from i to j looks like this:

i \to a \to b \to c \to j

Here’s a path from x to y that is not directed:

i \to a \leftarrow b \to c \to j

and I hope you can write down the obvious but tedious definition of an ‘undirected path’, meaning a path made of edges that don’t necessarily point in the correct direction. Given that, we say two vertices i and j lie in the same connected component iff you can find an undirected path going from i to j. In this case, there will automatically also be an undirected path going from j to i.

For example, i and j lie in the same connected component here, but not the same strongly connected component:

i \to a \leftarrow b \to c \to j

Here’s a graph with one connected component and 3 strongly connected components, which are marked in blue:

For the theory we’re looking at now, we only care about connected components, not strongly connected components! However:

Puzzle 2. Show that for weakly reversible graph, the connected components are the same as the strongly connected components.

With these definitions out of way, we can state today’s big theorem:

Theorem. Suppose H is the Hamiltonian of a weakly reversible graph with rates:

Then for each connected component C \subseteq K, there exists a unique probability distribution \psi_C \in \mathbb{R}^K that is positive on that component, zero elsewhere, and is an equilibrium solution of the master equation:

H \psi_C = 0

Moreover, these probability distributions \psi_C form a basis for the space of equilibrium solutions of the master equation. So, the dimension of this space is the number of components of K.

Proof. We start by assuming our graph has one connected component. We use the Perron–Frobenius theorem, as explained in Part 20. This applies to ‘nonnegative’ matrices, meaning those whose entries are all nonnegative. That is not true of H itself, but only its diagonal entries can be negative, so if we choose a large enough number c > 0, H + c I will be nonnegative.

Since our graph is weakly reversible and has one connected component, it follows straight from the definitions that the operator H + c I will also be ‘irreducible’ in the sense of Part 20. The Perron–Frobenius theorem then swings into action, and we instantly conclude several things.

First, H + c I has a positive real eigenvalue r such that any other eigenvalue, possibly complex, has absolute value \le r. Second, there is an eigenvector \psi with eigenvalue r and all positive components. Third, any other eigenvector with eigenvalue r is a scalar multiple of \psi.

Subtracting c, it follows that \lambda = r - c is the eigenvalue of H with the largest real part. We have H \psi = \lambda \psi, and any other vector with this property is a scalar multiple of \psi.

We can show that in fact \lambda = 0. To do this we copy an argument from Part 20. First, since \psi is positive we can normalize it to be a probability distribution:

\displaystyle{ \sum_{i \in K} \psi_i = 1 }

Since H is infinitesimal stochastic, \exp(t H) sends probability distributions to probability distributions:

\displaystyle{ \sum_{i \in K} (\exp(t H) \psi)_i = 1 }

for all t \ge 0. On the other hand,

\displaystyle{ \sum_{i \in K} (\exp(t H)\psi)_i = \sum_{i \in K} e^{t \lambda} \psi_i = e^{t \lambda} }

so we must have \lambda = 0.

We conclude that when our graph has one connected component, there is a probability distribution \psi \in \mathbb{R}^K that is positive everywhere and has H \psi = 0. Moreover, any \phi \in \mathbb{R}^K with H \phi = 0 is a scalar multiple of \psi.

When K has several components, the matrix H is block diagonal, with one block for each component. So, we can run the above argument on each component C \subseteq K and get a probability distribution \psi_C \in \mathbb{R}^K that is positive on C. We can then check that H \psi_C = 0 and that every \phi \in \mathbb{R}^K with H \phi = 0 can be expressed as a linear combination of these probability distributions \psi_C in a unique way.   █

This result must be absurdly familiar to people who study Markov processes, but I haven’t bothered to look up a reference yet. Do you happen to know a good one? I’d like to see one that generalizes this theorem to graphs that aren’t weakly reversible. I think I see how it goes. We don’t need that generalization right now, but it would be good to have around.

The Hamiltonian, revisited

One last small piece of business: last time I showed you a very slick formula for the Hamiltonian H. I’d like to prove it agrees with the formula I gave this time.

We start with any graph with rates:

We extend s and t to linear maps between vector spaces:

We define the boundary operator just as we did last time:

\partial = t - s

Then we put an inner product on the vector spaces \mathbb{R}^T and \mathbb{R}^K. So, for \mathbb{R}^K we let the elements of K be an orthonormal basis, but for \mathbb{R}^T we define the inner product in a more clever way involving the rate constants:

\displaystyle{ \langle \tau, \tau' \rangle = \frac{1}{r(\tau)} \delta_{\tau, \tau'} }

where \tau, \tau' \in T. This lets us define adjoints of the maps s, t and \partial, via formulas like this:

\langle s^\dagger \phi, \psi \rangle = \langle \phi, s \psi \rangle

Then:

Theorem. The Hamiltonian for a graph with rates is given by

H = \partial s^\dagger

Proof. It suffices to check that this formula agrees with the formula for H given in Puzzle 1:

\displaystyle{ H \kappa = \sum_{s(\tau) = \kappa} r(\tau) (t(\tau) - s(\tau)) }

Here we are using the complex \kappa \in K as a name for one of the standard basis vectors of \mathbb{R}^K. Similarly shall we write things like \tau or \tau' for basis vectors of \mathbb{R}^T.

First, we claim that

\displaystyle{ s^\dagger \kappa = \sum_{\tau: \; s(\tau) = \kappa} r(\tau) \, \tau }

To prove this it’s enough to check that taking the inner products of either sides with any basis vector \tau', we get results that agree. On the one hand:

\begin{array}{ccl} \langle \tau' , s^\dagger \kappa \rangle &=& \langle s \tau', \kappa \rangle \\ \\ &=& \delta_{s(\tau'), \kappa} \end{array}

On the other hand:

\begin{array}{ccl} \displaystyle{ \langle \tau', \sum_{\tau: \; s(\tau) = \kappa} r(\tau) \, \tau \rangle } &=& \sum_{\tau: \; s(\tau) = \kappa} r(\tau) \, \langle \tau', \tau \rangle \\ \\ &=& \displaystyle{ \sum_{\tau: \; s(\tau) = \kappa} \delta_{\tau', \tau} } \\ \\ &=& \delta_{s(\tau'), \kappa} \end{array}

where the factor of 1/r(\tau) in the inner product on \mathbb{R}^T cancels the visible factor of r(\tau). So indeed the results match.

Using this formula for s^\dagger \kappa we now see that

\begin{array}{ccl} H \kappa &=& \partial s^\dagger \kappa \\ \\ &=& \partial \displaystyle{ \sum_{\tau: \; s(\tau) = \kappa} r(\tau) \, \tau } \\ \\ &=& \displaystyle{ \sum_{\tau: \; s(\tau) = \kappa} r(\tau) \, (t(\tau) - s(\tau)) } \end{array}

which is precisely what we want.   █

I hope you see through the formulas to their intuitive meaning. As usual, the formulas are just a way of precisely saying something that makes plenty of sense. If \kappa is some state of our Markov process, s^\dagger \kappa is the sum of all transitions starting at this state, weighted by their rates. Applying \partial to a transition tells us what change in state it causes. So \partial s^\dagger \kappa tells us the rate at which things change when we start in the state \kappa. That’s why \partial s^\dagger is the Hamiltonian for our Markov process. After all, the Hamiltonian tells us how things change:

\displaystyle{ \frac{d \psi}{d t} = H \psi }

Okay, we’ve got all the machinery in place. Next time we’ll prove the deficiency zero theorem!

This entry was posted on Tuesday, August 21st, 2012 at 7:03 am and is filed under chemistry, mathematics, networks, probability. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

9 Responses to Network Theory (Part 23)

  1. Arrow says:
    21 August, 2012 at 9:04 am

    I think H_{ij} explanation has a typo since “the probability per time for our system to hop from the i state to the state j” doesn’t look backwards.

    Reply
    • John Baez says:
      21 August, 2012 at 10:07 am

      Yes, I guess my subconscious just couldn’t stomach the truth: H_{i j} is really the probability per time for our system to hop from the state j to the state i.

      Thanks—fixed!

      Reply
  2. Blake Pollard says:
    21 August, 2012 at 9:16 am

    For the puzzle: For any two vertices i and j in a connected component of a weakly reversible graph we have an undirected path going from i to j, a set of edges or transitions with sources and targets. \{ \tau_{j1} \tau_{jn} \}. Starting with the edge attached to j, \tau_{j1}, if t(\tau_{j1}) = j then move to s(\tau_{j1}), if not then s(\tau_{j1}) = j. Since the graph is weakly reversible there exists a directed path from t(\tau_{j1}) to s(\tau_{j1}) = j, call this directed path \tau'_{j1} (could be a composition of several transitions). Again move on to s(\tau'_{j1}). Repeat until s(\tau_jk)=i and then the set of primed and unprimed transitions

    \tau'_{j1} ... \tau_{jk}

    is a directed path from i to j and since the graph is weakly reversible we have a directed path path back from j to i for every pair of vertices in the connected component, hence it is strongly connected. What you really run into is exactly what you see in your example of an undirected path, namely vertices in the undirected path that are only the source or only the target for two different transitions, using weak reversibility on the one of these that goes with your ordering you end up with an ordered path. It’s interesting you can either choose to go along and use weak reversibility at each vertex to initially create a directed path back from j to i or you can do what I did and use weak reversibility to direct your undirected path and then use weak reversibility again to show that component is strongly connected. Of course you need both for strongly connected.

    Reply
    • Blake Pollard says:
      21 August, 2012 at 9:17 am

      sorry first time latex on here… and you missed a latex right at the end of the post.

      Reply
      • John Baez says:
        21 August, 2012 at 10:14 am

        Thanks for catching that—it’s those last-minute afterthoughts that get me, every time.

        By the way, stuff like \usepackage, or macros don’t work here. You get what you get and that’s all you get. According to WordPress the blog comes pre-equipped with amsmath, amsfonts and amssymb. But they don’t list all the stuff that doesn’t work. All sorts of fancy formatting commands don’t work. So don’t push your luck.

        Reply
    • John Baez says:
      22 August, 2012 at 3:43 am

      If I understand your answer correctly, Blake, it sounds right. Let me say it my way.

      We’ve got a connected component of a weakly reversible graph, and we’re trying to show it’s strongly connected. So, given two vertices v and w, we know there’s an undirected path of edges from v to w, and we’re trying to show there’s a directed one. Look at each edge in this path—say the edge between some vertex x and the next vertex on the path, y. Either it’s pointing the right way—from x to y—or it’s not. If it’s pointing the right way, don’t mess with it. If it’s pointing the wrong way—from y to x—we know by weak reversibility that there’s a directed path going back from x to y. So, replace this edge by that directed path.

      We thus get a directed path from v to w, built from the edges in the original path that we pointing the right direction, and the directed paths we used to replace the edges that were pointing the wrong direction.

      (Look, ma—no subscripts!)

      By the way, maybe it’s time to announce that Blake Pollard is now starting grad school at U.C. Riverside! When are you actually going there, Blake?

      Reply
      • Blake says:
        22 August, 2012 at 9:07 pm

        I’m still working out here in Hawaii for about a month, staying island-side right up until the last minute! So I’ll be getting to Riverside probably the 21st of next month, just before classes start. Looking forward to it.

        As for the puzzle I like your explanation better, I was trying to warm up my confusing math speak since its a bit rusty. The switching of certain edges with directed paths reminds me of time-ordering operators in QFT, except there you just switch the order of terms rather than replacing them with possibly more terms.

        Reply
  3. John Baez says:
    22 August, 2012 at 3:12 am

    Let me record here my guess about equilibria for general Markov processes on finite sets, where we drop the ‘weak reversibility’ assumption. Someone must know this already, and I’d love to see a reference.

    A general directed multigraph looks a bit like this:

    Actually this is just a directed graph: it doesn’t have multiple edges going from one vertex to another. It also doesn’t have edges from a vertex to itself. But as I’ve explained, these features are irrelevant for the Markov process! When studying Markov processes, it’s enough to consider directed graphs with positive numbers labelling their edges.

    The strongly connected components are shaded in blue. If we collapse each strongly connected component to a point, and combine all edges from one component to another into a single edge, we get a directed acyclic graph, meaning a directed graph without any directed cycles.

    What can the equilibria of the Markov process look like? In the terminology of this post, an equilibrium is a probability distribution \psi with

    H \psi = 0

    A directed acyclic graph gives a partial order on the set of vertices, where v ≤ w exactly when there exists a directed path from v to w. Let’s say a vertex v is maximal if there’s no vertex w with v < w.

    So, there's a partial order on the strongly connected components of a directed graph, and we can talk about a 'maximal' strongly connected component. In this picture:

    the strongly connected component containing f and g is maximal.
    If you imagine what happens with a probability distribution as it evolves in time according to a Markov process with the graph, you’ll see that probability will flow into this component, but never leave it.

    In general there could be a bunch of maximal strongly connected components. Probability will flow into these, but never leave.

    For this reason, I think it’s obvious that an equilibrium \psi can only be nonzero on the strongly connected components that are maximal.

    So what are these like? We can write the equilibrium \psi as a sum of pieces, each supported on a different maximal strongly connected component. (By ‘supported on’ I mean that it’s zero outside this component.)

    Each of these pieces will itself be an equilibrium—since no probability can flow out, and none will be flowing in from other maximal strongly connected components, either.

    So, what’s an equilibrium like if it’s supported on just a single maximal strongly connected component?

    Since each strongly connected component is connected and weakly reversible, the theorem I described in this post says there’s exactly one equilibrium probability distribution \psi supported on this component. It’s positive everywhere, and every equilibrium \psi is a scalar multiple of this.

    Conclusion: for a general Markov process on a finite set, we get one equilibrium probability distribution supported on each maximal strongly connected component. Every equilibrium \psi is a linear combination of these. They form a basis.

    Reply

Leave a reply to John Baez Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.