Generate lattice paths in R

Question

For example, if I have a lattice that looks like this:

          133.1
         /
       121
      /  \
    110   108.9
   /  \  / 
 100   99
   \  /  \
    90    89.1
      \  /
       81
         \
          72.9

Where the lattice starts at 100 and either goes up with a factor 1.1 and goes down with a factor 0.9. This lattice has 3 periods in which it goes up or down. It is clear that this matrix could be filled in for more periods.

The lattice in matrix form looks like this:

     [,1] [,2] [,3]  [,4]
[1,]  100  110  121 133.1
[2,]   NA   90   99 108.9
[3,]   NA   NA   81  89.1
[4,]   NA   NA   NA  72.9

I'm working in R. The code to generate the lattice matrix is as follows:

#Parameters
S0 <- 100 #price at t0
u <- 1.1 #up factor
d <- 0.9 #down factor
n <- 3 #number of periods

#Matrix for the prices
prices <- matrix(data=NA, nrow=(n+1), ncol=(n+1))
prices[1,1] <- S0

#Fill the matrix
for(column in 2:(n+1)){

  for(row in 1:(column-1)){

    prices[row,column] <- u*prices[row,column-1];
  }

  prices[column,column] <- d*prices[column-1,column-1];
}

I would like to create a code that generates a matrix with all possible paths through the lattice. For this example, it would look like this:

     [,1] [,2] [,3]  [,4]
[1,]  100  110  121 133.1
[2,]  100  110  121 108.9
[3,]  100  110   99 108.9
[4,]  100  110   99  89.1
[5,]  100   90   99 108.9
[6,]  100   90   99  89.1
[7,]  100   90   81  89.1
[8,]  100   90   81  72.9

I've been struggling with this piece of code for hours now, so any help would be much appreciated! Thanks in advance! :)

Answer 1

Each path of length n corresponds to a sequence of up and down movements: you just have to enumerate all those sequences. If you already have the sequences of length n-1, as a matrix u, the sequences of length n can be obtained as

rbind( 
  cbind( u,  .9 ), 
  cbind( u, 1.1 ) 
)

You can put it in a function, and call it n times.

n <- 4
up   <- 1.1
down <- .9
m <- Reduce( 
  function(u,v) rbind( cbind( u, up ), cbind( u, down ) ), 
  rep(NA,n), 
  100
)
t(apply(m, 1, cumprod))
#  [1,] 100 110 121 133.1 146.41
#  [2,] 100  90  99 108.9 119.79
#  [3,] 100 110  99 108.9 119.79
#  [4,] 100  90  81  89.1  98.01
#  [5,] 100 110 121 108.9 119.79
#  [6,] 100  90  99  89.1  98.01
#  [7,] 100 110  99  89.1  98.01
#  [8,] 100  90  81  72.9  80.19
#  [9,] 100 110 121 133.1 119.79
# [10,] 100  90  99 108.9  98.01
# [11,] 100 110  99 108.9  98.01
# [12,] 100  90  81  89.1  80.19
# [13,] 100 110 121 108.9  98.01
# [14,] 100  90  99  89.1  80.19
# [15,] 100 110  99  89.1  80.19
# [16,] 100  90  81  72.9  65.61

Answer 2

Similarly, you can do something like this:

next.period<-function(x) rep(x,2)*rep(c(u,d),each=length(x))

next.matrix<-function(x) {
  next.period.col<-next.period(x[,ncol(x)])
  cbind(rbind(x,x),next.period.col)
}

lattice.paths<-t(S0)
for (i in 1:(n-1)) lattice.paths<-next.matrix(lattice.paths)

         next.period.col next.period.col
[1,] 100             110             121
[2,] 100              90              99
[3,] 100             110              99
[4,] 100              90              81