# How to get all the paths of a binomial tree

I'm trying to implement a pricing method for exotic options based on binomial tree's. The problem i'm having is that i'm not being able to generate all the paths of the tree. I have the following code in python that generates the tree but haven't been able to extract all the paths from it.

import numpy as np
risk_free = 0.1
spot = 50
volatility = 0.4
T = 3/12
steps = 3
dt = T/steps
Up = np.exp(volatility*np.sqrt(dt))
Down = 1 / Up
p = (np.exp(risk_free*dt)-Down)/(Up-Down)
q = 1-p

dpowers = Down ** np.arange(steps,-1,-1)
upowers = Up ** np.arange(0,steps+1)
# steps + 1 because at the end we have steps + 1 prices
W = spot*dpowers*upowers

# backward valuation
for i in np.arange(steps, 0,-1):
Si = spot*dpowers[(steps-i+1):steps+1]*upowers[0:i]
W = np.vstack((np.append(np.repeat(0,steps-i+1),Si),W))
Tree = W.T

• A Path though a binomial tree is just a sequence of letters U or D of length $N$. For example for $N=3$ the possible paths are "DDD, DDU, DUD, DUU, UDD, UDU, UUD, UUU" . There are $2^N$ of them. If you are familiar with the generation of binary numbers, you can program this easily (but here 0 is replaced by D and 1 is replaced by U). Apr 24, 2020 at 13:41
• @noob2 Yeah I new that i had 2^N paths and how they are calculated. To be honest I'm not familiar with generating binary numbers, will look at it. Apr 24, 2020 at 14:05
• By extracting, you mean using the tree generated in Tree? Because the paths I get when running your code look reasonable. Have a look at some of my old code for a working implementation of binomial tree's and the Longstaff Schwarz method. Apr 24, 2020 at 18:46
• @Bob Jansen I now the Tree is correct thats part of the code i have for american options, and yeah would like to extract all the paths from object Tree. as noob2 mentions the 2^N paths and associate each path to all the nodes in the tree Apr 24, 2020 at 20:40
• If you're really interested in the paths, I wouldn't set it up this way but just make all combinations of UD as @noob2 explains. Basically an $2^N \times N$ matrix where the rows are paths. However, this makes more sense if you're doing Monte Carlo where all paths are independent. with the tree your effectively merging paths into nodes, the first node contains all path, the second layer half etc. If you want to get the $n$th path out of your current tree you could just select it from the tree going up or down in every column. Apr 24, 2020 at 20:45

You can create all the moves you want with the following code, (taken from StackOverflow):

import itertools
import numpy as np
risk_free = 0.1
spot = 50
volatility = 0.4
T = 3/12
steps = 3
dt = T/steps
Up = np.exp(volatility*np.sqrt(dt))
Down = 1 / Up

paths = itertools.product([Up, Down], repeat=steps)


You can just loop over this list of list and multiply the current price to get the next price.