Pricing Parisian Options: Combinatorics, Simulation, and Parallel Processing

財務工程與金融創新在過去數十年蓬勃發展，設計出許多新金融商品，提供了風險管理所需的避險工具並促進市場效率與完整性。此財務領域的定價問題會嘗試建構數學模型推導公式解，但是由於大部分新奇衍生性金融商品契約複雜無公式能套用，必須借重電腦運算處理數值方法及模擬價格，因此計算機科學在此有其可施展之處。本篇論文探討巴黎選擇權評價方法即包含財務理論、機率統計、離散數學、計算複雜度、演算法設計與分析以及平行處理等議題。巴黎選擇權為路徑相關選擇權，迄今尚無封閉公式解存在，為此我們提出兩種快速財務演算法。首先以Costabile 於2002年建立在離散結構二項樹狀模型下的組合方法為基礎去評價巴黎選擇權，再將此方法稍加修改可把原本的時間複雜度由O(n^3)成功推進至O(n^2)；若是組合數已給定的情況下，空間複雜度亦由O(n^2)減少到O(n)。另外，在蒙地卡羅模擬法方面，我們引進逆高斯機率分配並結合其抽樣，可減少時間切割的期數而縮短計算時間。因為蒙地卡羅法的路徑模擬有各自獨立的特性，很容易使用平行運算處理。今日多核心處理器大行其道這不失為提高效率的方法，對此我們也做了相關的說明並加以應用。我們以C語言實作論文中的財務演算法，執行於自行建構的高效能叢集運算平台。同步處理模擬之計算量，俾能有效使用系統效能。Financial engineering and financial innovation flourished in last decades. We have developed many new financial products to provide hedge instruments for risk management, and promoted market efficiency and completeness. The pricing problems of this financial field will try to build mathematical models and derive analytic pricing formulas. But most exotic derivatives are too complicated to derive formulas. We must use computers to handle numerical methods and simulations, so computer science can give them a favor. This thesis discusses pricing of Parisian options and includes a lot of subjects: financial theory, probability & statistics, discrete mathematics, computational complexity, design & analysis of algorithms, and parallel processing.Parisian options are path-dependent options and their closed-form solutions are not available up to now. We propose two fast financial algorithms to solve it. First we price Parisian options based on a combinatorial approach in binomial tree by Costabile in 2002. To refine Costabile’s algorithm, time complexity O(n^3) can be reduced to O(n^2); If binomial coefficients are given, the space complexity O(n^2) could be reduced to O(n). Second on Monte Carlo simulation, we introduce the inverse Gaussian distribution and its sampling method. To combine simulations and the inverse Gaussian distribution sampling, it can reduce divided time intervals to save computational time. Because the paths generated by Monte Carlo simulation are independent, it is easy to apply parallel processing. Nowadays multi-core processors are very popular, it is also a good idea to enhance computational efficiency. We give some descriptions and applications on it.All financial algorithms in this thesis are implemented in the C programming language. We execute the programs on our high-performance computing clustered platform, and deal with simulation jobs synchronously. Then the system can be fully exploited.Contents. Introduction 1.1 Options 1.2 Barrier and Parisian Options 2.3 Thesis Structure 3. Fundamental Concepts 4.1 Wiener Process 4.2 Black-Scholes Option Pricing Model 4.3 Risk-Neutral Valuation 5.4 Binomial Option Pricing Model 6. Trees with Combinatorial Method in Pricing 9.1 Combinatorial Methods 9.2 Technique for Handling Large Numbers 11.3 Costabile’s Algorithm 11.4 An Improved Algorithm 18.5 General Case 22.6 Numerical Results 23. Monte Carlo Simulation 25.1 Crude Monte Carlo Simulation 25.2 Inverse Gaussian Distribution 27.3 Simulation with the Inverse Gaussian Distribution 30.4 General Case 34.5 Parallel Processing 34.6 Numerical Results 36. Conclusions 37ibliography 3