**Binomial Tree Simulation**

The binomial model is a discrete grid generation method from \(t=0\) to \(T\). At each point in time (\(t+\Delta t\)) we can move up with probability \(p\) and down with probability \((1-p)\). As the probability of an up and down movement remain constant throughout the generation process, we end up with a recombining binary tree, or *binary lattice*. Whereas a balanced binomial tree with height \(h\) has \(2^{h+1}-1\) nodes, a binomial lattice of height \(h\) has \(\sum_{i=1}^{h}i\) nodes.

The algorithm to generate a binomial lattice of \(M\) steps (i.e. of height \(M\)) given a starting value \(S_0\), an up movement \(u\), and down movement \(d\), is:

FOR i=1 to M

FOR j=0 to i

STATE S(j,i) = S(0)*u^j*d^(n-j)

ENDFOR

ENDFOR

We can write this function in R and generate a graph of the lattice. A simple lattice generation function is below:

# Generate a binomial lattice # for a given up, down, start value and number of steps genlattice <- function(X0=100, u=1.1, d=.75, N=5) { X <- c() X[1] <- X0 count <- 2 for (i in 1:N) { for (j in 0:i) { X[count] <- X0 * u^j * d^(i-j) count <- count + 1 } } return(X) }

We can generate a sample lattice of 5 steps using symmetric up-and-down values:

> genlattice(N=5, u=1.1, d=.9) [1] 100.000 90.000 110.000 81.000 99.000 121.000 72.900 89.100 108.900 133.100 65.610 [12] 80.190 98.010 119.790 146.410 59.049 72.171 88.209 107.811 131.769 161.051

In this case, the output is a vector of alternate up and down state values.

We can nicely graph a binomial lattice given a tool like graphviz, and we can easily create an R function to generate a graph specification that we can feed into graphviz:

function(S, labels=FALSE) { shape <- ifelse(labels == TRUE, "plaintext", "point") cat("digraph G {", "\n", sep="") cat("node[shape=",shape,", samehead, sametail];","\n", sep="") cat("rankdir=LR;","\n") cat("edge[arrowhead=none];","\n") # Create a dot node for each element in the lattice for (i in 1:length(S)) { cat("node", i, "[label=\"", S[i], "\"];", "\n", sep="") } # The number of levels in a binomial lattice of length N # is `$\frac{\sqrt{8N+1}-1}{2}$` L <- ((sqrt(8*length(S)+1)-1)/2 - 1) k<-1 for (i in 1:L) { tabs <- rep("\t",i-1) j <- i while(j>0) { cat("node",k,"->","node",(k+i),";\n",sep="") cat("node",k,"->","node",(k+i+1),";\n",sep="") k <- k + 1 j <- j - 1 } } cat("}", sep="") }

This will simply output a dot script to the screen. We can capture this script and save it to a file by invoking:

> x<-capture.output(dotlattice(genlattice(N=8, u=1.1, d=0.9))) > cat(x, file="/tmp/lattice1.dot")

We can then invoke dot from the command-line on the generated file:

$ dot -Tpng -o lattice.png -v lattice1.dot

The resulting graph looks like the following:

If we want to add labels to the lattice vertices, we can add the labels attribute:

> x<-capture.output(dotlattice(genlattice(N=8, u=1.1, d=0.9), labels=TRUE)) > cat(x, file="/tmp/lattice1.dot")