Home » Uncategorized » Counting Binomial Lattice Paths

This is not an academic or financial post, but a fun look at the large number of possible paths available in the binomial lattice used in certain types of financial models. Although there is a small model in the accompanying spreadsheet, this post is mostly concerned with calculating the number of paths and the probability of randomly choosing a particular path. One way to count the paths is to start with Pascal’s Triangle. Pascal’s Triangle is defined as a triangular array of binomial coefficients. Below is Pascal’s triangle from rows zero to 10:

Spreadsheet – Lattice          Sheet – “Pascal’s 10X10 Vertical”

To construct the triangle, start by entering the number one in the cell at the top (zero) row. Then enter the number 1, one cell to the left and one down. Continue this down to the last row. Then do the same on the right hand side. Then, wherever there is a cell inside the triangle with numbers to the upper left and upper right cells, add those two numbers together in that cell.

Pascal’s Triangle has a number of interesting mathematical uses, however for purposes this post we will only be concerned with combinations. Take a look at the 6th row and the 5th column and you will see the number 20. The number 20 tells you that starting from the top of the triangle and moving either left or right, and only down, there are 20 paths that can be taken to get to that cell. That is true of any cell in the triangle with a number.

Sheet – “Pascal’s 10X10 Horizontal”

This is the 10X10 triangle, turned Horizontally. Instead of the paths going from top to bottom, this version goes from left to right. This is the way many lattice models look. It also makes it easier for me to add descriptions and analytics to the triangle on the right hand side. You will notice that this triangle only has the number of paths in the 10th row. It shows that you don’t need to calculate each row’s values before the last row. It can be done mathematically, however Excel provides an easier way. The function  =COMBIN(Number,Number_chosen). For example, to get the center column at row 10 (number 252), enter =COMBIN(10,5). Remember that the triangle is turned on it’s side so 10 is the row and 5 is the column.

Now we will expand the triangle to 60 rows and 120 columns (see chart below). Obviously there are many more paths to be taken to get to row 60. The green and red cells represent a path that is derived from starting with the top cell and randomly choosing if the next cell going down  is going right or left. The letter “D” means go to the left, and “U” means go to the right. There is a 50/50 chance of going either direction. Each time you push the F9 key it calculates a new path. You can push the F9 key all day long and never get a path that goes all the way down the left or right had side of the triangle. We will see why later in the post.

Sheet – “Vertical 60 Rows”

The triangle below has the same 60 rows as the one above, but turned on its side.  It makes it easier to show the very large number of paths and probabilities.

Sheet -“Vertical 60 Rows”

Now we get to the subject of the title of this post. Below is the data for the above chart that is on the right hand side in the spreadsheet, enlarged to see the paths and probabilities. Remember when I said you could push F9 all day and never get the path all the way to the left or right of the triangle? That is because there is only one path on each side of the triangle. The probability of getting one of the two path on the sides of the triangle is .000000000000000008674% or 1 in 1,152,921,504,606,850,000.

Think of a 60 row triangle as rolling over a one month investment (CD, Treasury bill, etc.) for five years. Each month the investment rolls over and has a 50/50 chance of rolling into higher or lower rate.  The number of paths that could get you to the center cell after rolling over each month for five years is 118,264,581,564,861,000 with a 10.26% chance of that happening. The number of paths and the probability of ending up on or near the center of the triangle is extremely high. The total number of paths to all cells at row 60 is 1.15 quintillion.

Sheet “Horizontal 60 Months”

This is a small model that shows the average rate of rolling over a one month investment each month for five years. This model uses random paths by pushing the F9 key. The triangle is horizontal and zooms in on the center path. There are two yellow input cells on this sheet. The increment cell at the top has the change in rate at each rollover (I used 5 basis points). The other yellow input cell is the starting interest rate (I used 5.00%). The number in the orange cell is the average interest rate the path landed on over the 5 years.

 

This is not meant to be a sophisticated model, but a fun game that shows the extreme amount of paths that are possible to take in a random up or down, 50/50 chance, 60 row Pascal’s Triangle.

p.s.

I also threw in a sheet that shows a 360 row triangle (think of a monthly mortgage for 30 years). The possible number of paths for a 360 row triangle is 2.35E+108, or 2.35 with 108 zeros to the right.

Download Spreadsheet: Lattice

 

Leave a Reply

Your email address will not be published. Required fields are marked *

*
*