Phorgy Phynance

Network Theory and Discrete Calculus – The Discrete Master Equation

with 6 comments

This post is a follow up to

Network Theory and Discrete Calculus – Introduction

To give the result first, the master equation can be expressed in terms of discrete calculus simply as

\partial(\psi P) = 0,

where \psi is a discrete 0-form representing the states of a Markov chain (at all times), P is a discrete 1-form representing transition probabilities, and \partial is the boundary operator, i.e. a kind of graph divergence.

The rest of this post explains the terms in this discrete master equation and how it works.

The State-Time Graph

When working with a finite (or countable) number of states, there is nothing new in considering states \psi_i to be associated to nodes and the transition probabilities P_{i,j} to be associated to directed edges of a bi-directed graph. A simple 2-state example is given below

The directed graphs we work with for discrete stochastic calculus are slightly different and could be referred to as “state-time” graphs, which are supposed to make you think of “space-time”. A state i at time t is considered a different node than the state i at time t+1. An example 2-state, 2-time directed graph is illustrated below:

There are four directed edges in this state-time graph, which will be labelled

* \mathbf{e}^{(i,t)(i,t+1)}
* \mathbf{e}^{(i,t)(j,t+1)}
* \mathbf{e}^{(j,t)(i,t+1)}
* \mathbf{e}^{(j,t)(j,t+1)}

For N states, the state-time graph will look similar but with more states appended horizontally.

The Discrete Master Equation

A discrete 0-form representing the states at all times can be expressed as

\psi = \sum_i \sum_t \psi_i^t \mathbf{e}^{(i,t)}

and a discrete 1-form representing the transition probabilities can be expressed as

P = \sum_{i,j} \sum_t P_{i,j}^t \mathbf{e}^{(i,t)(j,t+1)}.

The product of the 0-form \psi and the 1-form P is given by

\psi P = \sum_{i,j} \sum_t \psi_i^t P_{i,j}^t \mathbf{e}^{(i,t)(j,t+1)}.

The boundary of a directed edge is given by

\partial \mathbf{e}^{(i,t)(j,t+1)} = \mathbf{e}^{(j,t+1)} - \mathbf{e}^{(i,t)}.

Now for some gymnastics, we can compute

\begin{aligned} \partial(\psi P)  &= \sum_{i,j} \sum_t \psi_i^t P_{i,j}^t \left[\mathbf{e}^{(j,t+1)} - \mathbf{e}^{(i,t)}\right] \\  &= \sum_{i,j} \sum_t \left[\psi_j^t P_{j,i}^t \mathbf{e}^{(i,t+1)} - \psi_i^t P_{i,j}^t \mathbf{e}^{(i,t)}\right] \\  &= \sum_i \sum_t \left[\sum_j \left(\psi_j^t P_{j,i}^t - \psi_i^{t+1} P_{i,j}^{t+1}\right)\right] \mathbf{e}^{(i,t+1)}.  \end{aligned}

This is zero only when the last term in brackets is zero, i.e.

\sum_j \left(\psi_j^t P_{j,i}^t - \psi_i^{t+1} P_{i,j}^{t+1}\right) = 0

or

\psi_i^{t+1} \sum_j P_{i,j}^{t+1} = \sum_j \psi_j^t P_{j,i}^t.

Since P is right stochastic, we have

\sum_j P_{i,j}^{t+1} = 1

so that

\psi_i^{t+1} = \sum_j \psi_j^t P_{j,i}^t.

In other words, when P is right stochastic and \partial(\psi P) = 0, we get the usual master equation from stochastic mechanics

\partial(\psi P) = 0\implies \psi_i^{t+1} = \sum_j \psi_j^t P_{j,i}^t.

Parting Thoughts

The master equation is a boundary. This makes me wonder about homology, gauge transformations, sources, etc. For example, since

\partial(\psi P) = 0,

does this imply

\psi P = \partial F

for some discrete 2-form F?

If G is a discrete 2-form whose boundary does not vanish, then

\psi P + \partial G

gives the same dynamics because \partial^2 = 0. This would be a kind of gauge transformation.

There are several directions to take this from here, but that is about all the energy I have for now. More to come…

Advertisements

Written by Eric

October 29, 2011 at 10:04 pm

6 Responses

Subscribe to comments with RSS.

  1. […] applications of discrete calculus to mathematical finance and field theories. For instance, in the The Discrete Master Equation, I introduced a boundary […]

  2. I am new to this field and I am trying to understand how discrete calculus helps with these problems. What I find confusing is that you speak of discrete differential forms as linear combinations of directed edges. As I understand it, the latter are chains and the former are cochains, i.e., functionals on chains. You also refer to the boundary operator, which works with chains, and then say it’s a kind of graph divergence (exterior derivative?), which works with cochains.

    Peter

    November 21, 2011 at 7:46 am

    • Hi Peter,

      Thanks for your comment and question. I’m typing this on my iPhone on my way to the office, so forgive me in advance.

      My paper on discrete stochastic calculus explains things a little more clearly than I have here. In fact, I haven’t been rigorous here at all. For example, I should not refer to discrete 1-forms as linear combinations of edges because they are not. As you pointed out, a discrete 1-form is closest to a 1-cochain. In fact, the product in this noncommutative graded algebra is closest to the cup product of cochains.

      It is also good to point out that it is a bit odd to talk about boundary of cochains when the natural operation is coboundary. The graph divergence is essentially the adjoint of the coboundary under a kind of topogical inner product where edges are all orthonormal. With this metric, we can identify an edge with a “co-edge”.

      If you want to see even more details of the mathematics, you can have a look at the paper on discrete differential geometry on causal graphs I wrote with Urs Screiber. You can find it here in “My Papers” or on the arxiv.

      Gotta run for now. I hope this helps a little.

      Eric

      November 21, 2011 at 8:38 am

    • PS: I don’t know if you read the Azimuth forum, but over there when I announced these two latest posts, I noted that these are warmups for two future posts I plan to write. One of those will be specifically on the graph divergence, graph Laplacian, and graph Dirac operator. I will try to explain things more clearly there as well.

      Eric

      November 21, 2011 at 9:05 am

  3. […] graph divergence was introduced here as a boundary operator, but the relation to divergence was mentioned […]

  4. […] directed graphs associated with discrete stochastic mechanics are described in the post The Discrete Master Equation, where the simple state-time graph example below was […]


Leave a Reply

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

%d bloggers like this: