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! :)

score 5 · Accepted Answer · answered Oct 06 '13 at 16:04

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

score 2 · Answer 2 · answered Oct 06 '13 at 16:10

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

score 2 · Answer 3 · answered Oct 06 '13 at 16:35

Another idea is to build a "scaffold" at first, using expand.grid, and fill it next.

    #all possible paths of times (either 1.1. or 0.9) each previous value
    aa <- expand.grid(1, c(1.1,0.9), c(1.1,0.9), c(1.1,0.9), c(1.1,0.9)) 

    aa[,1] <- aa[,1] * 100 # start with 100

    for(i in 2:ncol(aa)) # fill by multiplying value of previous column
     {
      aa[,i] <- aa[,i] * aa[,i-1]
     }

    aa
    #Var1 Var2 Var3  Var4   Var5
    #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

For more periods, expand.grid needs another c(1.1,0.9).

Generate lattice paths in R

3 Answers3