The random behavior of financial variables such as stock prices, interest rates, FX rates, credit spreads can be approximated using two-state lattices known as Binomial trees. Binomial trees are useful for a variety of European-style and American-style derivatives.

##### Introduction

Consider an asset with an initial value $$S_{0}$$ at time $$t=0$$. During a time period $$\Delta{t}$$, the asset price can go up to $$Su$$ with probability $$p$$ or down to $$Sd$$ with probability $$q=1-p$$. The asset price $$S$$ is a Bernoulli random variable.

Consider also a call option on this asset that matures at the end of time period $$\Delta{t}$$. The first two branches of a binomial tree starting from its root node which represents today and evolving out in time by one time step.

As with the Black and Scholes model, we can set up a riskless portfolio consisting of the underlying asset and the call option. Consider a long position of $$\Delta$$ units of the asset and a short position of one call option. We want the value of the portfolio to be the same regardless of whether the asset price goes up or down over the period $$\Delta{t}$$:

$$-C_{u}+\Delta{S_{0}}{u}=-C_{d}+\Delta{S_{0}}{d}$$

Rearranging we obtain

$$\Delta=\frac{C_{u}-C_{d}}{(u-d)S_{0}}$$

Since this portfolio is does not have any risk, we assume that investors are risk-neutral and do not demand any additional return – they expect the risk-free rate of return (continuously compounded).

$$-C_{u}+\Delta{S_{0}}u=e^{r\Delta{t}}(-C+\Delta{S_{0}})$$

Substituting into the equation for $$\Delta{S_{0}}$$, we obtain

$$-C_{u}+\Delta{S_{0}}u=e^{r\Delta{t}}(-C+\Delta{S_{0}})\\ -C_{u}+\left(\frac{C_{u}-C_{d}}{u-d}\right)u=e^{r\Delta{t}}\left(-C+\frac{C_{u}-C_{d}}{u-d}\right)\\ C=e^{-r\Delta{t}}C_{u}-e^{-r\Delta{t}}\left(\frac{C_{u}-C_{d}}{u-d}\right)u+\frac{C_{u}-C_{d}}{u-d}$$

Collecting terms in $$C_{u}$$ and $$C_{d}$$ and simplifying,

\begin{align} C&=\frac{e^{-r\Delta{t}}C_{u}u-e^{-r\Delta{t}}C_{u}d-e^{-r\Delta{t}}C_{u}u+e^{-r\Delta{t}}C_{d}u+C_{u}-C_{d}}{(u-d)}\\ &=\frac{(1-e^{-r\Delta{t}}d)C_{u}}{u-d}+\frac{(e^{-r\Delta{t}}u-1)C_{d}}{u-d}\\ &=e^{-r\Delta{t}}\left[\left(\frac{e^{r\Delta{t}}-d}{u-d}\right)C_{u}+\left(\frac{u-e^{r\Delta{t}}}{u-d}\right)C_{d}\right] \end{align}

Defining

$$p=\frac{e^{r\Delta{t}}-d}{u-d}$$

we can re-write the above equation in the simpler form:

$$C=e^{-r\Delta{t}}[pC_{u}+(1-p)C_{d}]$$

This is the price of a call option with one period to maturity. Note that in the same way as Black-Scholes, the real-world probabilities of the stock moving up or down are never used in deriving the option price, the option price is independent of the expected return of the stock. Thus, $$p$$ and $$(1-p)$$ are risk-neutral probabilities.

The above equation can therefore be interpreted as taking discounted expectations of future pay-offs under the risk-neutral probabilities. As seen, risk-neutral probabilities can be easily computed.

###### Extending the model to multiple periods

If we extend this analysis to multiple periods, the price follows a $$binomial(N,p)$$ distribution. Let $$T=N\Delta{t}$$ where $$N$$ is the number of time periods. There are $$N+1$$ nodes at time step $$N$$ and $$N+1$$ different terminal prices and payoffs. Thus, there are $$2^{N}$$ possible price paths from $$(0,S_{0})$$ to $$(T,S_{T})$$.

A binomial tree with $$N=3$$ timesteps would look like this.

Node $$(i,j)$$ denotes the $$j$$th node at the $$i$$th time step. The price $$S_{i,j}$$ at node $$(i,j)$$ is given by:

$$S_{0}u^{j}d^{i-j}$$

where $$i$$ is the number of time steps to the node $$(i,j)$$ and $$j$$ is the number of up moves to the node $$(i,j)$$. The payoff after $$N$$ periods, denoted by $$C_{N,j}$$, is

$$C_{N,j}=F(S_{0}u^{j}d^{N-j})$$

We can use backward induction to price European options. The price of an option at node $$(i,j)$$ over one period, $$\Delta{t}$$, is given by:

$$C_{i,j}=e^{-r\Delta{t}}(pC_{i+1,j+1}+(1-p)C_{i+1,j})$$

The value of the option at node $$(i,j)$$ is found by taking the expected value of the option at time $$i+1$$. The option will be worth either $$C_{i+1,j+1}$$ with probability $$p$$ or $$C_{i+1,j}$$ with probability $$(1-p)$$. We discount this value back by the risk-free rate since we want the present value of this future expected payoff.

The multiperiod binomial valuation formula for European options is:

$$\displaystyle{C=e^{-rT}\sum_{j=1}^{N}p_{N,j}C_{N,j}}$$

where $$C_{N,j}=F(S_{N,j})=F(S_{0}u^{j}d^{N-j})$$ is the payoff in state $$j$$ at expiration $$N$$ and $$p_{N,j}$$ is the risk-neutral binomial probability to end up in state $$(N,j)$$:

$$\displaystyle{p_{N,j}={{N}\choose{j}}p^{j}(1-p)^{N-j}}$$

##### Binomial Pricer in Python

This is a simple pricer for a European call option using CRR(Cox-Ross-Rubenstein) model.

import numpy as np
import math

def buildCRRBinomialTree(spot, strike, rate, vol, T, N, optionType):
S = np.zeros((N+1,N+1),dtype='float')
C = np.zeros((N+1,N+1),dtype='float')
i,j = 0,0
dt = T/N     #Size of time step
u = 1.1
d = 1/u
disc = math.exp(-rate*dt)

# Risk-neutral probabilities
p = (math.exp(rate*dt)-d)/(u-d)
q = 1-p

S[0][0] = spot

# Initialize all the asset prices
for i in range(N+1):
for j in range(i+1):
S[i][j]=S[0][0]*(u**j)*(d**(i-j))

# Initialize the option values at maturity
for j in range(N+1):
C[N][j] = max(S[N][j]-strike,0)

# Step back through the tree
for i in range(N-1,-1,-1):
for j in range(i+1):
C[i][j]=disc*(p*C[i+1][j+1]+(1-p)*C[i+1][j])

return S, C

When buildBinomialTree() is invoked with the following inputs :

S_array, C_array = buildCRRBinomialTree(100,100,0.06,0.10,1,3,'C')

S_array and C_array will hold the asset price and option price trees. print() the results.

print('=================')

for i in range(4):
print('{:>20}  {:>20}  {:>20}  {:>20}'.format(S_array[0][3-i],
S_array[1][3-i],
S_array[2][3-i],
S_array[3][3-i]))

print("\n")

print(' Call price tree ')
print('=================')
for i in range(4):
print('{:>20}  {:>20}  {:>20}  {:>20}'.format(C_array[0][3-i],
C_array[1][3-i],
C_array[2][3-i],
C_array[3][3-i]))

Output:

Asset price tree
=================
0.0                   0.0                   0.0    133.10000000000005
0.0                   0.0    121.00000000000001    110.00000000000001
0.0    110.00000000000001    100.00000000000001      90.9090909090909
100.0      90.9090909090909     82.64462809917354     75.13148009015777

Call price tree
=================
0.0                   0.0                   0.0     33.10000000000005
0.0                   0.0     22.98013266932449    10.000000000000014
0.0     15.44712277624033    5.7048250806307035                   0.0
10.145735799928826    3.2545029200593065                   0.0                   0.0

##### Convergence of the binomial price process with the Black Scholes process

We now need to link the binomial price process with the Black Scholes geometric brownian motion process, so that the binomial model is consistent with it. We have two models to describe the asset price dynamics, a discrete-time multiplicative binomial model with parameters $$(u,d,p,r)$$ and the continuous time Black-Scholes-Merton model with parameters $$\sigma,r$$. In the limit of infinitesimally small time steps, as $$N\rightarrow\infty$$ and $$\Delta{t}\rightarrow{0}$$, the binomial option pricing formula must converge to the Black-Scholes option pricing formula for the two formulations to be consistent.

This requires the distribution of the terminal stock price in the binomial model to converge to the lognormal distribution as $$\Delta{t}\rightarrow{0}$$.

###### Mean and variance of the asset price process under Black Scholes framework

For a function $$f(W_{t})$$, the Taylor’s formula written at the second order of Brownian motion reads:

$$\displaystyle{d(f(W_{t}))=f'(W_{t})dW_{t}+\frac{1}{2}f^{(2)}(W_{t})dt}$$

Integrating on both sides and using the relation

$$\displaystyle{f(W_{t})=f(W_{0})+\int_{0}^{t}{f'(W_{s})dW_{s}}+\frac{1}{2}\int_{0}^{t}{f^{(2)}(W_{s})ds}}$$

Ito’s formula for Ito Processes. We now turn to general expression of the Ito’s formula which applies to Ito processes of the form,

$$dX_{t}=v_{t}dt+u_{t}dW_{t}$$

or in integral notation,

$$X_{t}=X_{0}+\int_{0}^{t}{v_{s}ds}+\int_{0}^{t}{u_{s}dW_{s}}$$

Given $$(t,x)\rightarrow{f(t,x)}$$ a smooth function of two variables on $$\mathbb{R_{+}}\times\mathbb{R}$$, from now on we let $$\frac{\partial{f}}{\partial{x}}$$ denote partial differentiation with respect to the second variable in $$f(t,x)$$, while $$\frac{\partial{f}}{\partial{t}}$$ denote partial differentiation with respect to the first (time) variable in $$f(t,x)$$.

Theorem. (Ito’s formula for Ito processes). For any Ito process $$(X_{t})_{t\in\mathbb{R_{+}}}$$ and any function $$f(t,X_{t})$$, we have:

\begin{align} f(t,X_{t})&=f(0,X_{0})+\int_{0}^{t}{v_{s}\frac{\partial{f}}{\partial{x}}(s,X_{s})ds}+\int_{0}^{t}{u_{s}\frac{\partial{f}}{\partial{x}}(s,X_{s})dW_{s}}\\ &+\int_{0}^{t}\frac{\partial{f}}{\partial{s}}(s,X_{s})ds+\frac{1}{2}\int_{0}^{t}{u_{s}^{2}\frac{\partial^{2}{f}}{\partial{x^2}}(s,X_{s})ds} \end{align}

or in differential notation,

\begin{align} df(t,X_{t})&=v_{t}\frac{\partial{f}}{\partial{x}}(t,X_{t})dt+u_{t}\frac{\partial{f}}{\partial{x}}(t,X_{t})dW_{t}\\ &+\frac{\partial{f}}{\partial{t}}(t,X_{t})dt+\frac{1}{2}{u_{t}}^{2}\frac{\partial^{2}{f}}{\partial{x^2}}(t,X_{t})dt \end{align}

Example. Apply Ito’s formula to $$f(t,W_{t})={W_{t}}^{2}$$.

Solution.

$$\frac{\partial}{\partial{x}}({x^2})=2x\\ \frac{\partial^{2}}{\partial{x^2}}({x^2})=2\\ \frac{\partial}{\partial{t}}({x^2})=0\\ d(W_{t}^2)=2W_{t}dW_{t}+2dt$$

Stochastic modelling of the asset price.The standard SDE representation of asset price is

$$dS_{t}=rS_{t}dt+\sigma{S_{t}}{dW_{t}}$$

We are interested in the diffusion of the process $$x=f(S)=\ln(S)$$.

$$\frac{\partial}{\partial{x}}({\ln(x)})=\frac{1}{x}\\ \frac{\partial^{2}}{\partial{x^2}}({\ln(x)})=-\frac{1}{x^2}\\ \frac{\partial}{\partial{t}}({\ln(x)})=0\\$$

By Ito’s Lemma, we have:

$$d(\ln(S_{t}))=r{S_{t}}\left(\frac{1}{S_{t}}\right)dt+\sigma{S_{t}}\left(\frac{1}{S_{t}}\right)dW_{t}\\ +\frac{1}{2}\sigma^{2}{S_{t}}^{2}\left(\frac{-1}{{S_{t}}^{2}}\right)dt$$

Simplifying and collecting terms in $$dt$$ and $$dW_{t}$$, we get:

$$d(\ln(S_{t}))=(r-\frac{\sigma^2}{2})dt+\sigma{dW_{t}}$$

or

$$S_{T}=S_{0}e^{(r-\frac{\sigma^2}{2})T+\sigma{W_{t}}}$$

The mean and variance of the log price process is,

$$E\left[\ln{\left(\frac{S_{T}}{S_{0}}\right)}\right]=(r-\frac{\sigma^{2}}{2})T={\nu}T$$

where $$\nu=(r-\frac{\sigma^{2}}{2})$$ and

$$Var\left[\ln{\left(\frac{S_{T}}{S_{0}}\right)}\right]={\sigma^2}T$$

###### Mean and variance of the binomial price process

The distribution of the terminal stock price in the binomial model with parameters $$(u,d,p,r)$$ converges to the Black-Scholes lognormal distribution with parameters $$(\sigma,r)$$ as $$\Delta{t}\rightarrow{0}$$ if and only if:

$$p\ln{\left(\frac{u}{d}\right)}+\ln{d}=\mu\Delta{t}$$

and

$$p(1-p)\left(\ln\left(\frac{u}{d}\right)\right)=\sigma^{2}\Delta{t}$$

Proof. The proof is based on the central limit theorem. In the Black-Scholes model (BSM), the terminal stock price is a random variable

$$\eta=\ln\left(\frac{S_{T}}{S_{0}}\right)=\nu{T}+\sigma\sqrt{T}Z$$

where $$Z$$ is a standard normal random variable. The continuously compounded random return $$\eta$$ over the time period $$T$$ is a normal random variable.

On the other hand, consider a binomial model where $$T$$ is divided into a large number $$N$$ of time steps. The return over the entire period $$T$$ is a sum of the individual single period returns over each time step $$\Delta{t}$$,

$$\eta=\sum_{i=1}^{N}{\eta_{i}}$$

where the $$\eta_{i}$$‘s are i.i.d. random variables that can take two values either $$\ln{u}$$ with probability $$p$$ or $$\ln{d}$$ with probability $$1-p$$. The mean $$m$$ and variance $$s^2$$ of $$\eta_{i}$$ are:

$$m=p\ln{u}+(1-p)\ln{d}$$

and

\begin{align} s^2&=E({\eta_{i}}^2)-E(\eta_{i})^2\\ &=p(\ln{u})^2+(1-p)(\ln{d})^2-(p\ln{u}+(1-p)\ln{d})^2\\ &=p(\ln{u})^2+(1-p)(\ln{d})^2-p^2(\ln{u})^2-(1-p)^2(\ln{d})^2-2p(1-p)\ln{u}\ln{d}\\ &=p(1-p)(\ln{u})^2+p(1-p)(\ln{d})^2-2p(1-p)\ln{u}\ln{d}\\ &=p(1-p)(\ln{u}-\ln{d})^2\\ &=p(1-p)\left(\ln\left(\frac{u}{d}\right)\right)^2 \end{align}

Now, the central limit theorem states that for large $$N$$, the distribution of the sum $$\eta$$ of $$N$$ i.i.d. random variables is approximately normal with mean $$mN$$ and variance $$s^2{N}$$.

Thus, the binomial model will converge to the Black Scholes model, if and only if the below conditions are satisfied:

$${mN}\overset{N\rightarrow\infty}\longrightarrow{\nu{T}}$$

$${s^2}{N}\overset{N\rightarrow\infty}\longrightarrow{\sigma^2{T}}$$

###### Formalization

By starting at the expiration date and working backward, we can find the valuation of a call option at any period $$n$$. Since, we assume the stock price follows a multiplicative binomial probability distribution, we have

$$\displaystyle{ C_{binomial}=r^{-n} \left\{ \sum_{j=0}^{n} {{n}\choose{j}} p^{j}(1-p)^{n-j} \max\left[0,Su^{j}d^{n-j}-K\right] \right\} }$$

Let $$a$$ denote the minimum number of upward moves that the stock must make over the next $$n$$ periods for the call to finish in-the-money. Thus, $$a$$ is the smallest non-negative integer such that $$Su^{a}d^{n-a}\gt{K}$$. Taking the natural logarithms of both sides of the inequality, we get:

\begin{align} Su^{a}d^{n-a}&\gt{K}\\ S\left(\frac{u}{d}\right)^a{d^n}&\gt{K}\\ \left(\frac{u}{d}\right)^{a}&\gt{\frac{K}{Sd^n}}\\ a&\gt{\frac{\ln{\frac{K}{Sd^n}}}{\ln{\frac{u}{d}}}} \end{align}

Thus, $$a$$ is the smallest non-negative integer greater than $$\ln(K/Sd^n)/\ln(u/d)$$. For all $${j}\lt{a}$$, $$\max[0,Su^{j}d^{n-j}-K]=0$$ and for all $$j\ge{a}$$, $$\max[0,Su^{j}d^{n-j}-K]=Su^{j}d^{n-j}-K$$. Therefore,

$$\displaystyle{ C_{binomial}=\frac{1}{r^n} \left\{ \sum_{j=a}^{n}{{n}\choose{j}} p^{j}(1-p)^{n-j} [Su^{j}d^{n-j}-K] \right\} }$$

Note that if $${a}\gt{n}$$, the option contract will finish out-of-the-money even if the stock moves upward every period, so its current value must be zero.

Therefore, we can re-write the above equation as:

\begin{align} C_{binomial}&= S\left( \sum_{j=a}^{n}{{n}\choose{j}} p^{j}(1-p)^{n-j} \left( \frac{u^{j}d^{n-j}}{r^n} \right) \right)\\ &-Xr^{-n} \left( \sum_{j=a}^{n}{{n}\choose{j}} p^{j}(1-p)^{n-j} \right) \end{align}

Let $$p’=(up)/r$$ and $$1-{p’}=(1-p)d/r$$. We express,

$$p^{j}(1-p)^{n-j} \left( \frac{u^{j}d^{n-j}}{r^n} \right) =\left( \frac{pu}{r} \right)^{j} \left( \frac{(1-p)d}{r} \right)^{n-j} ={p’}^{j}{(1-p’)}^{n-j}$$

Consequently, the binomial option pricing formula for a call option contract can be construed as follows.

\begin{align} C_{binomial}&= S\left( \sum_{j=a}^{n}{{n}\choose{j}} {p’}^{j}(1-p’)^{n-j} \right) -Xr^{-n} \left( \sum_{j=a}^{n}{{n}\choose{j}} p^{j}(1-p)^{n-j} \right) \end{align}

Now, in a single-period setting, the expected value of the receipt of the stock contingent on the exercise of the option is:

$$E(S_{T}|S_{T}\gt{K})=(p)(Su)+(1-p)\cdot(0)=p{\cdot}Su$$.

Discounted back to the present yields $$\frac{1}{r}[S{\cdot}up]$$. Therefore, $$S{\cdot}p’=S(up/r)$$ is the expected value of the receipt of the stock contingent upon exercise after $$1$$ period, discounted to the present. Let’s extend this to multiple periods.

The first term,

\begin{align} &S(\sum_{j=a}^{n}{{n}\choose{j}}{p’}^{j}(1-p’)^{n-j})\\ &=\frac{1}{r^n}\left({Su^n}\cdot{p^n}+{n\choose{1}}{Su^{n-1}d}\cdot{p^{n-1}q}+\ldots+{n\choose{a}}{Su^{n-a}d^2}\cdot{p^{n-a}q^{a}}\right) \end{align}

is simply a probability weighted average – the expected binomial value of the receipt of the stock, contingent upon exercise after $$n$$ periods, discounted to the present.

The second term,

$$Xr^{-n} \left( \sum_{j=a}^{n}{{n}\choose{j}} p^{j}(1-p)^{n-j} \right)$$

in a similar fashion is the expectation of the payment of the exercise price, contingent upon exercise after $$n$$ periods, discounted to the present.

In Binomial notation, we can write

$$C=S\Phi[a,n,p’]-Xr^{-n}\Phi[a,n,p]$$

We can now show that the Binomial formula in the above equation converges to the Black Scholes formula and that the multiplicative binomial distribution of the stock price converges to the lognormal distribution. To show the convergence of the distributions, we need to show that

As $$n\rightarrow\infty$$,
$$\Phi[a,n,p’]\rightarrow{N\left(d_{1}\right)}$$ and
$$\Phi[a,n,p]\rightarrow{N\left(d_{2}\right)}$$