Fast Fourier Transform with Applications to Pricing Discrete European Barrier Options under Binomial and Trinomial Tree Models

A derivative is a financial instrument which is constructed from other more basic underlying assets, such as bonds or stocks. With the dramatic growth of the derivatives markets, more and more derivatives have been designed and issued by financial institutions. This thesis presents a method that can be used to speed up the pricing of discrete European barrier options under binomial and trinomial tree models. Binomial tree and trinomial tree are two common and efficient models for pricing options. However, in practice, almost all barrier options are discretely monitored and the refection principle no longer works. It seems that the only way to price discrete barrier options is to traverse the whole tree, which takes quadratic time. This thesis gives the first subquadratic-time algorithm for the problem.Contents 1 List of Figures 2 1 Introduction 3 1.1 Structures of the Thesis . . . . . . . . . . . . . . . . . . . . . 3 2 Preliminaries 5 2.1 Option Pricing Basics . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 The Black-Scholes Option Pricing Model . . . . . . . . . . . . 7 2.3 The Binomial Option Pricing Model . . . . . . . . . . . . . . . 8 2.4 Barrier Options: Continuous and Discrete Monitoring . . . . . 8 2.5 Polynomial Multiplication and Discrete Fourier Transform . . 9 3 Pricing European Discrete Barrier Options with n Monitor- ing Days 10 3.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 A Straightforward Solution . . . . . . . . . . . . . . . . . . . . 11 3.3 The Basic Algorithm . . . . . . . . . . . . . . . . . . . . . . . 12 4 The Improved Algorithms 16 4.1 The First Improvement . . . . . . . . . . . . . . . . . . . . . . 16 4.2 The Final Algorithm . . . . . . . . . . . . . . . . . . . . . . . 18 5 Conclusion 22 Bibliography 2