## Network Theory and Discrete Calculus – The Binary Tree

This post is part of a series

So far in this series we’ve touched on a few applications of discrete calculus, but these were still at a fairly high level of abstraction. In this post, we lay some foundations for some very concrete applications that will allow us to actually start calculating things.

### The Binary Tree

A particularly nice directed graph with many applications is the binary tree – a portion of which is illustrated below:

A node in the binary tree is labelled , where the first integer denotes the “spatial” position, i.e. its location at a given time, and the second integer denotes the “temporal” position.

### Discrete Forms

A general discrete 0-form on a binary tree is written as usual as

where the sum is only over nodes of the binary tree and not over all integers. For instance, if is in the binary tree, then and are not.

Due to the special nature of the binary tree, a general discrete 1-form may also be reduced to a single sum over nodes, but in two distinct ways. First, we can group edges directed away from a given node. Second, we can group edges directed toward a given node.

In the first case, we can write

which is referred to as the **left-component form **and in the second case, we can write

which is referred to as the **right-component form**. These are two equivalent ways of expressing the same general discrete 1-form with

and

To see why these are referred to as left- and right-component forms, denote

and

and define a pair of basis 1-forms

and

Next, we can define left- and right-component 0-forms

and

respectively so that a discrete 1-form may be expressed in left-component form as

or equivalently in right-component form as

In other words, the left- and right- component forms of the bases allow us to express a general discrete 1-form form in terms of left- or right-component discrete 0-forms.

### Differentials

The exterior derivative of a general discrete 0-form on a binary tree is given in left-component form as

From this, we can read off the left-components which we’ll denote as

and

so that

Similarly, the right-components are given by

and

so that

### Noncommutative Coordinates

Although, strictly speaking, coordinates (other than node labels) are not necessary for performing computations in discrete calculus, it is helpful when comparing to continuum calculus to introduce coordinate 0-forms to the binary tree

where is the spatial distance between endpoints of a directed edge at successive time steps, and

where is the temporal spacing between successive temporal nodes.

In this special case, we have

and

so that

and

These relations can be inverted resulting in

and

so that

where

and

and the discrete calculus begins to resemble the continuum calculus.

### Commutation Relations

The coordinates and were referred to as “noncommutative” above because although discrete 0-forms commute, i.e.

in general, discrete 0-forms and discrete 1-forms do not commute. A straightforward computation results in the following commutation relations

and

from which it follows that

From here, there are two continuum limits one could consider that lead to different calculi. In the first, we could set

In this case, all commutation relation vanish and the continuum is also a commutative limit, i.e. the coordinates commute in this limit and we’re left with the usual deterministic continuum calculus.

In the second limit, we could set

In this case, the second and third commutation relations vanish, but the first one remains

This limit gives rise to stochastic calculus (or a very close cousin). Motivated by this, the discrete calculus on a binary tree when setting

but keeping finite is referred to as **discrete stochastic calculus**.

[…] the previous post, we introduced discrete calculus on a binary tree. In particular, we introduced two sets of basis […]

Network Theory and Discrete Calculus – Differentiation Rules « Phorgy PhynanceJanuary 8, 2012 at 11:20 pm

[…] the binary tree was presented in the context of discrete calculus, the following small section of the tree was illustrated to […]

Network Theory and Discrete Calculus – Coordinates « Phorgy PhynanceFebruary 19, 2012 at 2:17 pm