Phorgy Phynance

Network Theory and Discrete Calculus – The Binary Tree

with 2 comments

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 (i,j), where the first integer i denotes the “spatial” position, i.e. its location at a given time, and the second integer j denotes the “temporal” position.

Discrete Forms

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

\begin{aligned} \psi = \sum_{(i,j)} \psi(i,j) \mathbf{e}^{(i,j)},\end{aligned}

where the sum is only over nodes of the binary tree and not over all integers. For instance, if (i,j) is in the binary tree, then (i+1,j) and (i,j+1) 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

\begin{aligned} \alpha = \sum_{(i,j)} \left [ \overleftarrow{\alpha_+}(i,j) \mathbf{e}^{(i,j),(i+1,j+1)} + \overleftarrow{\alpha_-}(i,j) \mathbf{e}^{(i,j),(i-1,j+1)} \right] \end{aligned}

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

\begin{aligned} \alpha = \sum_{(i,j)} \left [ \overrightarrow{\alpha_+}(i,j) \mathbf{e}^{(i-1,j-1),(i,j)} + \overrightarrow{\alpha_-}(i,j) \mathbf{e}^{(i+1,j-1),(i,j)} \right] \end{aligned}

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

\overleftarrow{\alpha_+}(i,j) = \overrightarrow{\alpha_+}(i+1,j+1)

and

\overleftarrow{\alpha_-}(i,j) = \overrightarrow{\alpha_-}(i-1,j+1) .

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

\mathbf{e}^{(i,j),(i+1,j+1)} = \overleftarrow{\mathbf{e}^+}(i,j) = \overrightarrow{\mathbf{e}^+}(i+1,j+1)

and

\mathbf{e}^{(i,j),(i-1,j+1)} = \overleftarrow{\mathbf{e}^-}(i,j) = \overrightarrow{\mathbf{e}^-}(i-1,j+1)

and define a pair of basis 1-forms

\begin{aligned} \mathbf{e}^+ = \sum_{(i,j)} \overleftarrow{\mathbf{e}^+}(i,j) = \sum_{(i,j)} \overrightarrow{\mathbf{e}^+}(i,j) \end{aligned}

and

\begin{aligned} \mathbf{e}^- = \sum_{(i,j)} \overleftarrow{\mathbf{e}^-}(i,j) = \sum_{(i,j)} \overrightarrow{\mathbf{e}^-}(i,j). \end{aligned}

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

\begin{aligned} \overleftarrow{\alpha_\pm} = \sum_{(i,j)} \overleftarrow{\alpha_\pm} \mathbf{e}^{(i,j)}\end{aligned}

and

\begin{aligned} \overrightarrow{\alpha_\pm} = \sum_{(i,j)} \overrightarrow{\alpha_\pm} \mathbf{e}^{(i,j)}\end{aligned}

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

\begin{aligned} \alpha = \overleftarrow{\alpha_+} \mathbf{e}^+ + \overleftarrow{\alpha_-} \mathbf{e}^- = \sum_{(i,j)} \left[\overleftarrow{\alpha_+}(i,j) \overleftarrow{\mathbf{e}^+}(i,j) + \overleftarrow{\alpha_-}(i,j) \overleftarrow{\mathbf{e}^-}(i,j)\right] \end{aligned}

or equivalently in right-component form as

\begin{aligned} \alpha = \mathbf{e}^+ \overrightarrow{\alpha_+} + \mathbf{e}^- \overrightarrow{\alpha_-} = \sum_{(i,j)} \left[\overrightarrow{\mathbf{e}^+}(i,j) \overrightarrow{\alpha_+}(i,j) + \overrightarrow{\mathbf{e}^-}(i,j) \overrightarrow{\alpha_-}(i,j)\right] \end{aligned}

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 \psi on a binary tree is given in left-component form as

\begin{aligned} d\psi = \sum_{(i,j)} \left[\psi(i+1,j+1)-\psi(i,j)\right] \mathbf{e}^{(i,j),(i+1,j+1)} + \left[\psi(i-1,j+1)-\psi(i,j)\right] \mathbf{e}^{(i,j),(i-1,j+1)}. \end{aligned}

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

\begin{aligned} \overleftarrow{\partial_+ \psi} = \sum_{(i,j)} \left[\psi(i+1,j+1)-\psi(i,j)\right] \mathbf{e}^{(i,j)}\end{aligned}

and

\begin{aligned} \overleftarrow{\partial_- \psi} = \sum_{(i,j)} \left[\psi(i-1,j+1)-\psi(i,j)\right] \mathbf{e}^{(i,j)}\end{aligned}

so that

d\psi = \overleftarrow{\partial_+ \psi} \mathbf{e}^+ + \overleftarrow{\partial_- \psi} \mathbf{e}^-.

Similarly, the right-components are given by

\begin{aligned} \overrightarrow{\partial_+ \psi} = \sum_{(i,j)} \left[\psi(i,j)-\psi(i-1,j-1)\right] \mathbf{e}^{(i,j)}\end{aligned}

and

\begin{aligned} \overrightarrow{\partial_- \psi} = \sum_{(i,j)} \left[\psi(i,j)-\psi(i+1,j-1)\right] \mathbf{e}^{(i,j)}\end{aligned}

so that

d\psi = \mathbf{e}^+ \overrightarrow{\partial_+ \psi} + \mathbf{e}^- \overrightarrow{\partial_- \psi}.

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

\begin{aligned} x = \sum_{i,j} x(i,j) \mathbf{e}^{(i,j)} = \sum_{i,j} i \Delta x \mathbf{e}^{(i,j)}, \end{aligned}

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

\begin{aligned} t = \sum_{i,j} t(i,j) \mathbf{e}^{(i,j)} = \sum_{i,j} j \Delta t \mathbf{e}^{(i,j)}, \end{aligned}

where \Delta t is the temporal spacing between successive temporal nodes.

In this special case, we have

\begin{aligned} \overleftarrow{\partial_+ x} = \overrightarrow{\partial_+ x} = -\overleftarrow{\partial_- x} = -\overleftarrow{\partial_- x} = \Delta x \sum_{(i,j)} \mathbf{e}^{(i,j)}\end{aligned}

and

\begin{aligned} \overleftarrow{\partial_+ t} = \overrightarrow{\partial_+ t} = \overleftarrow{\partial_- t} = \overleftarrow{\partial_- t} = \Delta t \sum_{(i,j)} \mathbf{e}^{(i,j)}\end{aligned}

so that

dx = \Delta x (\mathbf{e}^+ - \mathbf{e}^-).

and

dt = \Delta t (\mathbf{e}^+ + \mathbf{e}^-).

These relations can be inverted resulting in

\mathbf{e}^+ = \frac{1}{2\Delta t} dt + \frac{1}{2\Delta x} dx

and

\mathbf{e}^- = \frac{1}{2\Delta t} dt - \frac{1}{2\Delta x} dx

so that

\begin{aligned} d\psi &= \overleftarrow{\partial_+ \psi} \mathbf{e}^+ + \overleftarrow{\partial_- \psi} \mathbf{e}^- \\ &= \overleftarrow{\partial_t \psi} dt + \overleftarrow{\partial_x \psi} dx \end{aligned}

where

\begin{aligned} \overleftarrow{\partial_t \psi} &= \frac{\overleftarrow{\partial_+ \psi} + \overleftarrow{\partial_- \psi}}{2\Delta t} \\ &= \sum_{(i,j)} \left[\frac{\psi(i+1,j+1)+\psi(i-1,j+1) -2\psi(i,j)}{2\Delta t}\right] \mathbf{e}^{(i,j)} \end{aligned}

and

\begin{aligned} \overleftarrow{\partial_x \psi} &= \frac{\overleftarrow{\partial_+ \psi} - \overleftarrow{\partial_- \psi}}{2\Delta x} \\ &= \sum_{(i,j)} \left[\frac{\psi(i+1,j+1) -\psi(i-1,j+1)}{2\Delta x}\right] \mathbf{e}^{(i,j)} \end{aligned}

and the discrete calculus begins to resemble the continuum calculus.

Commutation Relations

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

x t = t x,

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

[\mathbf{e}^\pm,x] = \pm\Delta x \mathbf{e}^\pm

and

[\mathbf{e}^\pm,t] = \Delta t \mathbf{e}^\pm

from which it follows that

[dx,x] = \frac{(\Delta x)^2}{\Delta t} dt

[dx,t] = [dt,x] = \Delta t dx

[dt,t] = \Delta t dt.

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

\Delta x = c\Delta t, \Delta t\to 0.

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

(\Delta x)^2 = \Delta t, \Delta t\to 0.

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

[dx,x] = dt.

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

(\Delta x)^2 = \Delta t

but keeping \Delta t finite is referred to as discrete stochastic calculus.

Advertisements

Written by Eric

December 30, 2011 at 11:48 pm

2 Responses

Subscribe to comments with RSS.

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

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


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: