## Archive for the ‘**Directed Graphs**’ Category

## Network Theory and Discrete Calculus – The Discrete Master Equation

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

where is a discrete 0-form representing the states of a Markov chain (at all times), is a discrete 1-form representing transition probabilities, and 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 to be associated to nodes and the transition probabilities 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 at time is considered a different node than the state at time . 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

*

*

*

*

For 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

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

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

The boundary of a directed edge is given by

Now for some gymnastics, we can compute

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

or

Since is right stochastic, we have

so that

In other words, when is right stochastic and , we get the usual master equation from stochastic mechanics

### Parting Thoughts

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

does this imply

for some discrete 2-form ?

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

gives the same dynamics because 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…

## Network Theory and Discrete Calculus – Introduction

I’ve enjoyed applying discrete calculus to various problems since Urs Schreiber and I wrote our paper together back in 2004

**Discrete differential geometry on causal graphs**

Shortly after that, I wrote an informal paper applying the theory to finance in

**Financial modeling using discrete stochastic calculus**

From there I wrote up some private notes laying the foundations for applying a higher-dimensional version of discrete calculus to interest rate models. However, life intervened, I went to work on Wall Street followed by various career twists leading me to Hong Kong where I am today. The research has laid fairly dormant since then.

I started picking this up again recently when my friend, John Baez, effectively changed careers and started the Azimuth Project. In particular, I’ve recently developed a discrete Burgers equation with corresponding discrete Cole-Hopf transformation, which is summarized – including numerical simulation results – on the Azimuth Forum here:

**Discrete Burgers equation revisited**

Motivated by these results, I started looking at a reformulation of the Navier-Stokes equation in

**Towards Navier-Stokes from noncommutative geometry**

This is still a work-in-progress, but sorting this out is a necessary step to writing down the discrete Navier-Stokes equation.

Even more recently, John began a series of very interesting Azimuth Blog posts on network theory. I knew that network theory and discrete calculus should link up together naturally, but it took a while to see the connection. It finally clicked one night as I laid in bed half asleep in one of those rare “Eureka!” moments. I wrote up the details in

There is much more to be said about the connection between network theory and discrete calculus. I intend to write a series of subsequent posts in parallel to John’s highlighting how his work with Brendan Fong can be presented in terms of discrete calculus.

## Currency exchange rates, directed graphs, and quivers

I always enjoy working with currency exchange rates because it gives me excuses to draw directed graphs. For example, an exchange rate EURUSD = 1.4 can be thought of as a directed edge from EUR to USD as shown below.

A fact of life when you work in finance is that you rarely have any say in the data available to you for analysis. When working with three currencies, e.g. USD, EUR, and KRW, it would be great if someone handed you a complete FX Matrix with all exchange rates filled in like

Instead, what is usually available is a list of exchange rates such as

With a little patience, you can usually figure out all the cross terms, e.g. it is obvious that from the given data we have

but we’d like to find a systematic way to do this that can be programmed.

So the thing I want to talk about here is starting with a list of exchange rates, i.e. FX Vector, we want to fill in as much of the FX Matrix as possible systematically. It turns out this process is identical to constructing a free category, i.e. quiver, from a directed graph.

In other words, we want to reinterpret the exchange rate as a morphism

Then, “filling in” the FX Matrix means finding all compositions of morphisms, e.g.

How would you do this? Here is what I did…

First, you take the given FX Vector and form an adjacency matrix. In the example above with EUR, USD, and KRW, the adjacency matrix looks like

but in general there will be more zeros.

We can also form an initial FX Matrix

This FX Matrix can be thought of as the currency exchanges that can occur in a single transaction.

An interesting property of the adjacency matrix is that when you raise it to the nth power, the matrix entries represent the number of paths between any two objects in the quiver that require n steps, i.e.

where is the number of paths of length or the number of ways to convert EUR to USD in transactions.

To fill out FX Matrix, we incrementally take powers of and find entries whose value is 1. Since it is getting late and I’m running out of energy, I’ll just write the procedure as a simple pseudo Matlab code:

FXMatrix = Zeros(Size(A)); For n = 1:NumCurrencies FXMatrix(A^n == 1) = FXMatrix1^n(A^n == 1); end

Although the explanation may seem a bit arduous, the final procedure is quite simple and easy to program.

Can you find a better way?

As a side note, this provides an algorithm for generating a quiver from a directed graph, i.e. it gives an adjoint functor to the forgetful functor .