In the binomial tree model, we provide efficient algorithms for computing an accurate lower bound for the value of a European-style Asian option with either a fixed or a floating strike. These algorithms are inspired by the continuous-time analysis of Rogers and Shi. Specifically we consider lower bounds on the option value that are given by the expectation of the conditional expectation of the payoff conditioned on some random variable Z. For a specific Z, Rogers and Shi estimate this conditional expectation numerically in continuous time, and show experimentally that their lower bound is very accurate. We consider a modified random variable Z that gives a strictly better lower bound. In addition, we show that this lower bound can be computed exactly in the n-step binomial tree model in time proportional to n⁷. We show that computing the approximation is equivalent to counting paths of various types, and that this can be done efficiently by a dynamic programming technique. We present other choices of Z that yield accurate and efficiently-computable lower bounds. We also show algorithms to compute a bound on the error of these approximations, so that we can compute an upper bound on the option value as well.

15 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]