8.4 Multi-period trees: Cox–Ross–Rubinstein

Motivation

A one-period model has two terminal prices. Real expiries have a continuum. Chaining one-period models gives a lattice with $n+1$ terminal prices; with the right $u,d$ the terminal distribution converges to the lognormal and the tree price converges to Black–Scholes. Trees remain the workhorse for American options, which have no closed form.

The CRR lattice#

Setup

Divide $[0,T]$ into $n$ steps of $\Delta t=T/n$ . Cox, Ross and Rubinstein (1979) choose

u=e^{\sigma\sqrt{\Delta t}},\qquad d=1/u, \tag{8.11}

so the tree recombines (an up then a down returns to the same node) and each step's log return is $\pm\sigma\sqrt{\Delta t}$ , whose variance per unit time is $\sigma^2$ . After $j$ ups and $n-j$ downs the price is $S_0u^jd^{n-j}$ . The risk-neutral probability $p$ is (8.10) at every node, and Lemma 8.3.1 requires $d<e^{(r-q)\Delta t}<u$ , which holds once $\Delta t$ is small enough that $|r-q|\sqrt{\Delta t}<\sigma$ .

Backward induction#

Algorithm 8.4.1backward induction

Terminal values $V_{n,j}=h(S_0u^jd^{n-j})$ , $j=0,\dots,n$ , with $h$ the payoff.
For $i=n-1,\dots,0$ and $j=0,\dots,i$ : $V_{i,j}=e^{-r\Delta t}\,[pV_{i+1,j+1}+(1-p)V_{i+1,j}]$ .
For an American option replace step 2 by $V_{i,j}=\max\big(h(S_0u^jd^{i-j}),\ e^{-r\Delta t}[pV_{i+1,j+1}+(1-p)V_{i+1,j}]\big)$ .
Return $V_{0,0}$ .

Each step is the one-period replication of 8.3 applied locally, so the tree price is the cost of a self-financing strategy that rebalances $n$ times. For the American case, step 3 is the dynamic programming principle: at each node the holder takes the better of exercising and continuing.

Closed form and convergence#

Proposition 8.4.2closed form for the European call

Let $a$ be the smallest integer with $S_0u^ad^{n-a}>K$ and $p'=pue^{-(r-q)\Delta t}$ . Then

c_n = S_0e^{-qT}\sum_{j=a}^{n}\binom nj p'^j(1-p')^{n-j}\;-\;Ke^{-rT}\sum_{j=a}^{n}\binom nj p^j(1-p)^{n-j}. \tag{8.12}

Proof

Iterating the one-step recursion $n$ times gives $c_n=e^{-rT}\sum_j\binom nj p^j(1-p)^{n-j}(S_0u^jd^{n-j}-K)^+$ . The terms with $j<a$ vanish. For the stock term, $e^{-rT}p^j(1-p)^{n-j}u^jd^{n-j}=e^{-qT}\,[pue^{-(r-q)\Delta t}]^j[(1-p)de^{-(r-q)\Delta t}]^{n-j}$ , and $(1-p)de^{-(r-q)\Delta t}=1-p'$ because $pu+(1-p)d=e^{(r-q)\Delta t}$ .∎

The two sums are binomial tail probabilities: the probability of finishing in the money under two different measures ( $p'$ and $p$ ). Their limits are $N(d_1)$ and $N(d_2)$ (8.7).

Proposition 8.4.3convergence to Black–Scholes; sketch

With CRR parameters, as $n\to\infty$ the tree price of a European put or call converges to the Black–Scholes price (8.23)–(8.24).

Sketch

Under $\mathbb Q$ the log return $\ln(S_T/S_0)=\sum_{i=1}^nX_i$ with i.i.d. $X_i=\pm\sigma\sqrt{\Delta t}$ with probabilities $p,1-p$ . Expand $p$ in $\sqrt{\Delta t}$ . Using $e^{x}=1+x+x^2/2+x^3/6+O(x^4)$ ,

\begin{gathered} e^{(r-q)\Delta t}-e^{-\sigma\sqrt{\Delta t}}=\sigma\sqrt{\Delta t}+\big(r-q-\tfrac12\sigma^2\big)\Delta t+O(\Delta t^{3/2}),\\ u-d=2\sigma\sqrt{\Delta t}+O(\Delta t^{3/2}), \end{gathered}

\Rightarrow\quad p=\tfrac12+\frac{r-q-\sigma^2/2}{2\sigma}\sqrt{\Delta t}+O(\Delta t). \tag{8.13}

So $\mathbb E^{\mathbb Q}[X_i]=\sigma\sqrt{\Delta t}(2p-1)=(r-q-\tfrac12\sigma^2)\Delta t+O(\Delta t^{3/2})$ and $\operatorname{Var}^{\mathbb Q}[X_i]=\sigma^2\Delta t\,[1-(2p-1)^2]=\sigma^2\Delta t+O(\Delta t^2)$ . Summing $n=T/\Delta t$ terms, the mean of $\ln(S_T/S_0)$ tends to $(r-q-\frac12\sigma^2)T$ and the variance to $\sigma^2T$ . The $X_i$ form a triangular array of bounded, independent variables, so the Lindeberg condition holds trivially and the central limit theorem gives $\ln(S_T/S_0)\Rightarrow N\big((r-q-\tfrac12\sigma^2)T,\ \sigma^2T\big)$ . The put payoff $(K-S_0e^x)^+$ is bounded and continuous in $x$ , so weak convergence implies convergence of the discounted expectation to the lognormal integral, which is the Black–Scholes put (8.7). Put–call parity holds exactly on the tree (the payoff identity is model-free), so the call converges too. For the full argument see Cox, Ross and Rubinstein (1979), 4, or Hull, Ch. 13 appendix; Shreve II, Ch. 3, treats the lognormal limit of the binomial model.∎

Rate and oscillation The error is $O(1/n)$ but not monotone. Table 8.1 (computed by m08_binomial.crr_price; the values for $n=10,100,1000$ are checked against the exercise's tests) shows the ATM call with $S=K=100$ , $T=1$ , $r=5\%$ , $\sigma=20\%$ , whose Black–Scholes value is 10.4505835722.

Table 8.1. CRR convergence.

$n$	CRR price	error	$n\times$ error
1	12.162285	+1.711701	1.71
2	9.540501	−0.910082	−1.82
5	10.805934	+0.355350	1.78
10	10.253409	−0.197175	−1.97
11	10.611200	+0.160617	1.77
100	10.430612	−0.019972	−2.00
1000	10.448584	−0.001999	−2.00
2000	10.449584	−0.001000	−2.00

Even $n$ undershoots and odd $n$ overshoots for this ATM option, because the strike sits on a node for even $n$ and between nodes for odd $n$ . Averaging consecutive $n$ , or using a tree that centres a node on the strike (Leisen and Reimer 1996), removes most of the oscillation.

American put on a tree#

Worked example 8.5American put

Hull's example: $S_0=K=50$ , $r=10\%$ , $\sigma=40\%$ , $T=5/12$ , five monthly steps. Then $u=e^{0.4\sqrt{1/12}}=1.1224$ , $d=0.8909$ , $p=0.5073$ . Backward induction with the early-exercise check gives 4.488459 (Hull prints 4.49). The European put on the same tree is 4.319019, and the Black–Scholes European put is 4.075981. The early-exercise premium on this tree is 0.169; the gap between the five-step European tree and Black–Scholes (0.243) is discretisation error, which shrinks as $n$ grows. Both numbers are tests in the code.

Practitioner notes

Use a few hundred steps for a single American option; use Black–Scholes for Europeans. Nifty and Bank Nifty options are European (8.11), so trees are a teaching tool for Indian index options and a pricing tool only for American products elsewhere.
The tree delta at the root, $(V_{1,1}-V_{1,0})/(S_0u-S_0d)$ , is a cheap, accurate delta. Gamma comes from the three nodes at step 2.