Binomial Tree Option Pricer

Worked Solution

How to Think About It: A binomial tree discretizes the continuous stock price process into $N$ time steps. At each step, the stock goes up by factor $u$ or down by factor $d$. Under risk-neutral pricing, you discount expected payoffs at the risk-free rate, using the risk-neutral probability $q$ (not the real-world probability). The tree is recombining ($u \\cdot d = 1$), so after $N$ steps there are only $N+1$ distinct stock prices instead of $2^N$ -- this is what makes $O(N^2)$ possible. For the American option, at each node you check whether exercising early beats the continuation value. The key trick for $O(N)$ memory: keep one array of option values, updated backwards from expiry.

CRR Parameters (with $\\Delta t = T/N$):

$$u = e^{\\sigma \\sqrt{\\Delta t}}, \\quad d = e^{-\\sigma \\sqrt{\\Delta t}} = 1/u, \\quad q = \\frac{e^{r \\Delta t} - d}{u - d}$$

The risk-neutral probability $q$ ensures $q \\cdot u + (1-q) \\cdot d = e^{r \\Delta t}$.

Backward Induction:

1. Compute the $N+1$ terminal stock prices $S_j = S_0 \\cdot u^{2j - N}$ and their payoffs ($\\max(S_j-K,0)$ for a call, $\\max(K-S_j,0)$ for a put). 2. Step backwards from $i = N-1$ to $0$: continuation value $C_j = e^{-r\\Delta t}(q V_{j+1} + (1-q) V_j)$. - European: $V_j = C_j$. - American: $V_j = \\max(C_j, \\text{exercise value at node }(i,j))$. 3. The price is $V_0$.

Signature: binomial_price(S0, K, r, sigma, T, N, option_type, exercise) where option_type is 'call' or 'put' and exercise is 'european' or 'american'. It returns the present value at the root as a float.

Code:

```python import math

def binomial_price(S0, K, r, sigma, T, N, option_type, exercise): dt = T / N u = math.exp(sigma * math.sqrt(dt)) d = 1.0 / u q = (math.exp(r * dt) - d) / (u - d) disc = math.exp(-r * dt)

# Terminal stock prices and payoffs V = [0.0] * (N + 1) for j in range(N + 1): S = S0 * (u ** (2 * j - N)) if option_type == 'call': V[j] = max(S - K, 0.0) else: V[j] = max(K - S, 0.0)

# Backward induction for i in range(N - 1, -1, -1): for j in range(i + 1): V[j] = disc * (q * V[j + 1] + (1 - q) * V[j]) if exercise == 'american': S = S0 * (u ** (2 * j - i)) if option_type == 'call': V[j] = max(V[j], S - K) else: V[j] = max(V[j], K - S)

return V[0]

```

Convergence: Compare against the closed-form Black-Scholes price for a European call, running $N = 50, 100, 200, 500, 1000$. The binomial price oscillates around Black-Scholes (even/odd $N$ effect) with error decreasing as $O(1/N)$; convergence follows from the CLT applied to the log-return distribution.

Complexity: Time $O(N^2)$ (triangle of nodes), space $O(N)$ (single reused array of size $N+1$).