In this tutorial we will be implementating a simple slow and fast binomial pricing model in python. We will treat binomial tree as a network with nodes (i,j) with i representing the time steps and j representing the number of ordered price outcome, lowest, or bottom of tree, to highest.
– binomial_tree_slow
– binomial_tree_fast
We will be using a generic timing wrapper function to judge the time performance of using numpy arrays over for loops to iterate over j nodes in each time step i. Please note if you do not want to use the timing wrapper, please still import numpy!
import numpy as np from functools import wraps from time import time def timing(f): @wraps(f) def wrap(*args, **kw): ts = time() result = f(*args, **kw) te = time() print('func:%r args:[%r, %r] took: %2.4f sec' % \ (f.__name__, args, kw, te-ts)) return result return wrap
Binomial Tree Representation
Stock tree can be represented using nodes \((i,j)\) and intial stock price \(S0\)
\(S_{i,j} = S_0u^{j}d^{i-j}\)
\(C_{i,j}\) represents contract price at each node \((i,j)\). Where \(C_{N,j}\) represents final payoff function that we can define.
For this tutorial will will price a European Call, so \(C_{N,j} = max(S_{N,j}-K,0)\)
# Initialise parameters S0 = 100 # initial stock price K = 100 # strike price T = 1 # time to maturity in years r = 0.06 # annual risk-free rate N = 3 # number of time steps u = 1.1 # up-factor in binomial models d = 1/u # ensure recombining tree opttype = 'C' # Option Type 'C' or 'P'
Binomial Tree Slow
For the binomial tree slow, we will use for loops to iterate through nodes j at each time step i.
@timing def binomial_tree_slow(K,T,S0,r,N,u,d,opttype='C'): #precompute constants dt = T/N q = (np.exp(r*dt) - d) / (u-d) disc = np.exp(-r*dt) # initialise asset prices at maturity - Time step N S = np.zeros(N+1) S[0] = S0*d**N for j in range(1,N+1): S[j] = S[j-1]*u/d # initialise option values at maturity C = np.zeros(N+1) for j in range(0,N+1): C[j] = max(0, S[j]-K) # step backwards through tree for i in np.arange(N,0,-1): for j in range(0,i): C[j] = disc * ( q*C[j+1] + (1-q)*C[j] ) return C[0] binomial_tree_slow(K,T,S0,r,N,u,d,opttype='C')
Binomial Tree Fast
Now we will vectorise out code using numpy arrays instead of for loops through j nodes.
@timing def binomial_tree_fast(K,T,S0,r,N,u,d,opttype='C'): #precompute constants dt = T/N q = (np.exp(r*dt) - d) / (u-d) disc = np.exp(-r*dt) # initialise asset prices at maturity - Time step N C = S0 * d ** (np.arange(N,-1,-1)) * u ** (np.arange(0,N+1,1)) # initialise option values at maturity C = np.maximum( C - K , np.zeros(N+1) ) # step backwards through tree for i in np.arange(N,0,-1): C = disc * ( q * C[1:i+1] + (1-q) * C[0:i] ) return C[0] binomial_tree_fast(K,T,S0,r,N,u,d,opttype='C')
Binomial Tree Slow vs Fast
Now we will compare runtimes for slow vs fast. Ignore option price changes as this is impacted with changing the time steps and keeping the u and d factors the same.
for N in [3,50, 100, 1000, 5000]: binomial_tree_slow(K,T,S0,r,N,u,d,opttype='C') binomial_tree_fast(K,T,S0,r,N,u,d,opttype='C')