American put option pricing by “binomial trees”

Dear MO World,

I'm teaching a financial mathematics course and have found a fascinating (to me) numerical phenomenon and wonder if anyone has studied it, or knows anything similar.

I'll try and give a description of what it means followed by a self-contained description of what I'm doing. First of all: an American put option is a product that gives the right to sell a share for a price $K$ (agreed at the outset) at any time up to the expiry time, $t$, of the option. It's assumed that the underlying share is moving according to a geometric Brownian motion (GBM) with known volatility parameter $\sigma$. The interest rate is $r$ and the initial share price is $s$.

The basic idea is to discretize the GBM to a multiplicative random walk on the "binomial tree" with depth $n$. That is: one assumes that at each of the $n$ stages the price multiplies by $u=\exp(\sigma\sqrt{t/n})$ or $d=1/u$. In this derivation, the "risk-neutral measure" is the measure on the multiplicative random walk where up steps occur independently with probability $p=(\exp(rt/n)-d)/(u-d)$ and down steps occur with probability $q=1-p$. One can then define $V_{j,i}$ to be the value of the option if unexercised by time $jt/n$ and the current share price is $su^id^{j-i}$. The approximate arbitrage-free cost of the option is $V_{0,0}$. The scaling of the multipliers guarantees that the multiplicative random walk converges to a geometric Brownian motion in the appropriate sense. It is assumed (and probably proved somewhere) that this converges to the true arbitrage free cost (computed using the GBM rather than the discrete approximation) as $n\to\infty$. I am interested in the dependence of $V_{0,0}$ on $n$, the number of time steps.

Here is the actual calculation that I'm doing: define $V_{n,i}=(K-su^id^{n-i})^+$. One then does a backwards recursion to populate previous levels of the "tree": $V_{j,i}=\max\big(K-su^id^{j-i},e^{-rt/n}(pV_{j+1,i+1}+qV_{j+1,i})\big)$. [The max here corresponds to either exercising the option now or holding it].

Here is a graph of $V_{0,0}$ versus $n$:

It seems that for odd $n$, the function roughly follows one curve, while for even $n$ it roughly follows another. I have no idea why the graph should look like this...

-
Perhaps it's a rounding issue. –  Kevin Ventullo Apr 4 '13 at 20:32
@Anthony: You get kinks in the graph whenever points on the tree cross the strike and/or optimal exercise boundary. The points on the tree for even n will interleave those for odd n of a similar magnitude (as Kevin noted). Hence you get two curves with the kinks for odd and even n roughly halfway between each other. –  George Lowther Apr 4 '13 at 22:21
The gap between grid points is $O(1/\sqrt{n})$. This actually gives an error of $O(1/n^2)$ in your equation for a single step (assuming smoothness of the values, and ignoring the fact that you are taking a max). This comes from expanding out as a Taylor series to 4th order in u and d and comparing vs a true normal distribution over the time step. Summing this error over the n steps gives order 1/n. Also, at each point where a max is taken, the values V have a sudden change in gradient, so you have a larger error, but this only occurs at a couple of points on the at each time step. –  George Lowther Apr 4 '13 at 23:23
You expect the "bounces" to be roughly symmetric as the situation is roughly symmetric as you increase the number of points or decrease it (keeping n roughly within the same magnitude). As the two curves are almost precisely out of phase, they will have a similar gradient where they cross. Btw, finite difference methods (eg, Crank Nicholson) are usually faster to converge, with $O(1/n^2)$ total error for Europeans, but still $O(1/n)$ for Americans, because the max function is not smooth. There are various rather involved tricks to improve on this. –  George Lowther Apr 4 '13 at 23:30
@George: Thanks very much indeed for the extremely helpful comments. Is there any chance you can package the most relevant ones into an answer so that it can be recorded that the original question is resolved? –  Anthony Quas Apr 4 '13 at 23:38