One solution to this is the forward shooting grid method(FSGM), which I believe was first established by John Hull and Alan White in this following paper: Efficient Procedures for Valuing European and American Path-dependent Options.
The FSGM is a local binomial model, or should we say that it has a tree structure for stock price, within each notes, a range of path information should be given.
I will illustrate this approach using John and Alan's example which is to calculate the prices of European and American options on the arithmetic average of the stock price. In this case, F is used to represent the arithmetic average value of stock price from time 0 to the note.
- The first step is to expand the binomial trees which gives the stock price as usual.
- The second step is to choose the F value for which the option value will be calculated. Consider the following representations of discretised state variable, where p is the quantization parameter affecting the spacing of F value.
- Now we have a modified binomial tree with each notes contains a range of F values, then for each F value, there is a corresponding option value, saying the option value at the stock price St and the average value F.
- What we do next is just the same way as a normal binomial tree, we use risk neutral pricing to calculate the option value at time t with the t+1 time information. $$V(S_{n-1},F_{n-1},t_{n-1}) = e^{-r\Delta t}[pV(S_n^u,F_n^u,t_n)+(1-p)V(S_n^d,F_n^d,t_n)]$$ Then question rises as how can we decide the up-movement and down-movement of the F value, i.e. which F values as well as its corresponding option values should we choose to calculate the previous time option value. Then we introduce the Arithmetic Asian option shooting function: $$F^u = \frac{F*n + S^u}{n+1}$$ $$F^d = \frac{F*n + S^d}{n+1}$$ Another issue is that by these shooting function, the shooting F value may not exactly lie in the mesh we generated in the second step, then interpolation is needed. $$V(S_{n-1},F_{n-1},t_{n-1}) = e^{-r\Delta t}[p\Pi(S_n^u,F_n^u,t_n)+(1-p)\Pi(S_n^d,F_n^d,t_n)]$$
function lookbackCall = FSG_EurAsianCall_FixStrikeArithmetic(S0, X, sigma, r, q, T, N)
tic;
% BTM and FSG parameters
dt = T / N;
dX = sigma * sqrt(dt);
rho = 0.1; % test this simplest one first
dY = rho * dX;
u = exp(dX);
d = 1 / u;
p = (exp((r- q) * dt) - d) / (u - d);
q = 1 - p;
df = exp(-r * dt); % discounting factor
% vector store stock and f value
S = S0 * exp(dX * (-N : N)');
F = S0 * exp(dY * (-N / rho : N / rho));
% terminal condition
V = max(repmat(F, 2 * N + 1, 1) - X, 0);
% backward step to generate the option value, in time step n, the F value we need to calculate is from -n to n
for n = N : -1 : 1
% row value to update in V matrix, remember the rho value -> the F_value steps
F_range = (N - n + 1) / rho + 1 : (N + n) / rho -1;
% column value to update in V matrix
S_range = N - n + 2 : 2 : N + n;
% next is the shooting function
for i = S_range
spot = S(i);
% shooting function
F_up = (n * F(F_range) + spot * u) / (n + 1);
F_down = (n * F(F_range) + spot * d) / (n + 1);
md_up = floor(log(F_up / S0) / dY) + N / rho + 1;
mu_up = md_up + 1;
md_down = floor(log(F_down / S0) / dY) + N / rho + 1;
mu_down = md_down + 1;
inter_up_value = V(i + 1, md_up) + (F_up - F(md_up)) ./ (F(mu_up) - F(md_up)) .* (V(i + 1, mu_up) - V(i + 1,md_up));
inter_down_value = V(i - 1, md_down) + (F_down - F(md_down)) ./ (F(mu_down) - F(md_down)) .* (V(i - 1, mu_down) - V(i - 1,md_down));
V(i, F_range) = df * (p * inter_up_value + q * inter_down_value);
end
end
lookbackCall = V(N + 1, N / rho + 1);
toc;
end