Network Theory and Discrete Calculus – The Binary Tree

This post is part of a series

Network Theory and Discrete Calculus

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.

Written by Eric

December 30, 2011 at 11:48 pm

Posted in Directed Graphs, Discrete Calculus, Network Theory

2 Responses

Subscribe to comments with RSS.

[...] 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 Phynance

January 8, 2012 at 11:20 pm

Reply
[...] 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 Phynance

February 19, 2012 at 2:17 pm

Reply

Phorgy Phynance