A Depth-First Search Technique For The Valuation Of American Path-Dependent Derivatives*

Abstract

Pricing path-dependent American options is difficult since the number of paths through a binomial tree grow exponentially with the number of binomial periods.  In practice even moderately sized trees of 20 to 25 periods can quickly exhaust available memory on most computer systems.  This paper describes a method that can be used to price path dependent American style derivatives where the amount of memory grows linearly, not exponentially, in the number of binomial periods.  The method is applied to pricing Asian options, fixed income derivatives based on the Heath-Jarrow-Morton model, and corporate bonds.