Monte Carlo Frameworks

DANIEL J. DUFFY has been working with numerical methods in finance, industry and engineering since 1979. He has written four books on financial models and numerical methods and C++ for computational finance and he has also developed a number of new schemes for this field. He is the founder of Datasim Education and has a PhD in Numerical Analysis from Trinity College, Dublin. JÖRG KIENITZ is the head of Quantitative Analysis at Deutsche Postbank AG. He is primarily involved in the developing and implementation of models for pricing of complex derivatives structures and for asset allocation. He is also lecturing at university level on advanced financial modelling and gives courses on ‘Applications of Monte Carlo Methods in Finance’ and on other financial topics including Lévy processes and interest rate models. Joerg holds a Ph.D. in stochastic analysis and probability theory.

• Notation xix Executive Overview xxiii0 My First Monte Carlo Application One-Factor Problems 10.1 Introduction and objectives 10.2 Description of the problem 10.3 Ordinary differential equations (ODE) 20.4 Stochastic differential equations (SDE) and their solution 30.5 Generating uniform and normal random numbers 40.6 The Monte Carlo method 80.7 Calculating sensitivities 90.8 The initial C++ Monte Carlo framework: hierarchy and paths 100.9 The initial C++ Monte Carlo framework: calculating option price 190.10 The predictor-corrector method: a scheme for all seasons? 230.11 The Monte Carlo approach: caveats and nasty surprises 240.12 Summary and conclusions 250.13 Exercises and projects 25PART I FUNDAMENTALS1 Mathematical Preparations for the Monte Carlo Method 311.1 Introduction and objectives 311.2 Random variables 311.3 Discrete and continuous random variables 341.4 Multiple random variables 371.5 A short history of integration 381.6 σ-algebras, measurable spaces and measurable functions 391.7 Probability spaces and stochastic processes 401.8 The Ito stochastic integral 411.9 Applications of the Lebesgue theory 431.10 Some useful inequalities 451.11 Some special functions 461.12 Convergence of function sequences 481.13 Applications to stochastic analysis 491.14 Summary and conclusions 501.15 Exercises and projects 502 The Mathematics of Stochastic Differential Equations (SDE) 532.1 Introduction and objectives 532.2 A survey of the literature 532.3 Mathematical foundations for SDEs 552.4 Motivating random (stochastic) processes 592.5 An introduction to one-dimensional random processes 592.6 Stochastic differential equations in Banach spaces: prologue 622.7 Classes of SIEs and properties of their solutions 622.8 Existence and uniqueness results 632.9 A special SDE: the Ito equation 642.10 Numerical approximation of SIEs 662.11 Transforming an SDE: the Ito formula 682.12 Summary and conclusions 692.13 Appendix: proof of the Banach fixed-point theorem and some applications 692.14 Exercises and projects 713 Alternative SDEs and Toolkit Functionality 733.1 Introduction and objectives 733.2 Bessel processes 733.3 Random variate generation 743.4 The exponential distribution 743.5 The beta and gamma distributions 753.6 The chi-squared, Student and other distributions 793.7 Discrete variate generation 793.8 The Fokker-Planck equation 803.9 The relationship with PDEs 813.10 Alternative stochastic processes 843.11 Using associative arrays and matrices to model lookup tables and volatility surfaces 933.12 Summary and conclusion 963.13 Appendix: statistical distributions and special functions in the Boost library 973.14 Exercises and projects 1024 An Introduction to the Finite Difference Method for SDE 1074.1 Introduction and objectives 1074.2 An introduction to discrete time simulation, motivation and notation 1074.3 Foundations of discrete time approximation: ordinary differential equations 1094.4 Foundations of discrete time approximation: stochastic differential equations 1134.5 Some common schemes for one-factor SDEs 1174.6 The Milstein schemes 1174.7 Predictor-corrector methods 1184.8 Stiff ordinary and stochastic differential equations 1194.9 Software design and C++ implementation issues 1254.10 Computational results 1264.11 Aside: the characteristic equation of a difference scheme 1274.12 Summary and conclusions 1284.13 Exercises and projects 1285 Design and Implementation of Finite Difference Schemes in Computational Finance 1375.1 Introduction and objectives 1375.2 Modelling SDEs and FDM in C++ 1375.3 Mathematical and numerical tools 1385.4 The Karhunen-Loeve expansion 1435.5 Cholesky decomposition 1445.6 Spread options with stochastic volatility 1465.7 The Heston stochastic volatility model 1535.8 Path-dependent options and the Monte Carlo method 1605.9 A small software framework for pricing options 1615.10 Summary and conclusions 1625.11 Exercises and projects 1626 Advanced Finance Models and Numerical Methods 1676.1 Introduction and objectives 1676.2 Processes with jumps 1686.3 Levy processes 1716.4 Measuring the order of convergence 1726.5 Mollifiers, bump functions and function regularisation 1766.6 When Monte Carlo does not work: counterexamples 1776.7 Approximating SDEs using strong Taylor, explicit and implicit schemes 1796.8 Summary and conclusions 1836.9 Exercises and projects 1847 Foundations of the Monte Carlo Method 1897.1 Introduction and objectives 1897.2 Basic probability 1897.3 The Law of Large Numbers 1907.4 The Central Limit Theorem 1917.5 Quasi Monte Carlo methods 1947.6 Summary and conclusions 1987.7 Exercises and projects 198PART II DESIGN PATTERNS8 Architectures and Frameworks for Monte Carlo Methods: Overview 2038.1 Goals of Part II of this book 2038.2 Introduction and objectives of this chapter 2038.3 The advantages of domain architectures 2048.4 Software Architectures for the Monte Carlo method 2078.5 Summary and conclusions 2128.6 Exercises and projects 2139 System Decomposition and System Patterns 2179.1 Introduction and objectives 2179.2 Software development process; a critique 2179.3 System decomposition, from concept to code 2179.4 Decomposition techniques, the process 2209.5 Whole-part 2229.6 Whole-part decomposition; the process 2239.7 Presentation-Abstraction Control (PAC) 2269.8 Building complex objects and configuring applications 2299.9 Summary and conclusions 2399.10 Exercises and projects 23910 Detailed Design using the GOF Patterns 24310.1 Introduction and objectives 24310.2 Discovering which patterns to use 24410.3 An overview of the GOF patterns 25510.4 The essential structural patterns 25710.5 The essential creational patterns 26610.6 The essential behavioural patterns 27010.7 Summary and conclusions 27610.8 Exercises and projects 27611 Combining Object-Oriented and Generic Programming Models 28111.1 Introduction and objectives 28111.2 Using templates to implement components: overview 28111.3 Templates versus inheritance, run-time versus compile-time 28311.4 Advanced C++ templates 28611.5 Traits and policy-based design 29411.6 Creating templated design patterns 30611.7 A generic Singleton pattern 30711.8 Generic composite structures 31011.9 Summary and conclusions 31411.10 Exercises and projects 31412 Data Structures and their Application to the Monte Carlo Method 31912.1 Introduction and objectives 31912.2 Arrays, vectors and matrices 31912.3 Compile-time vectors and matrices 32412.4 Creating adapters for STL containers 33112.5 Date and time classes 33412.6 The class string 33912.7 Modifying strings 34312.8 A final look at the generic composite 34512.9 Summary and conclusions 34812.10 Exercises and projects 34813 The Boost Library: An Introduction 35313.1 Introduction and objectives 35313.2 A taxonomy of C++ pointer types 35313.3 Modelling homogeneous and heterogeneous data in Boost 36113.4 Boost signals: notification and data synchronisation 36713.5 Input and output 36813.6 Linear algebra and uBLAS 37113.7 Date and time 37213.8 Other libraries 37213.9 Summary and conclusions 37413.10 Exercises and projects 374PART III ADVANCED APPLICATIONS14 Instruments and Payoffs 37914.1 Introduction and objectives 37914.2 Creating a C++ instrument hierarchy 37914.3 Modelling payoffs in C++ 38314.4 Summary and conclusions 39214.5 Exercises and projects 39315 Path-Dependent Options 39515.1 Introduction and objectives 39515.2 Monte Carlo – a simple general-purpose version 39615.3 Asian options 40115.4 Options on the running Max/Min 41115.5 Barrier options 41215.6 Lookback options 41815.7 Cliquet Options 42215.8 Summary and conclusions 42415.9 Exercises and projects 42416 Affine Stochastic Volatility Models 42716.1 Introduction and objectives 42716.2 The volatility skew/smile 42716.3 The Heston model 42916.4 The Bates/SVJ model 44116.5 Implementing the Bates model 44316.6 Numerical results – European options 44416.7 Numerical results – skew-dependent options 44616.8 XLL – using DLL within Microsoft Excel 44916.9 Analytic solutions for affine stochastic volatility models 45516.10 Summary and conclusions 45716.11 Exercises and projects 45817 Multi-Asset Options 46117.1 Introduction and objectives 46117.2 Modelling in multiple dimensions 46117.3 Implementing payoff classes for multi-asset options 46517.4 Some multi-asset options 46617.5 Basket options 46917.6 Min/Max options 47117.7 Mountain range options 47517.8 The Heston model in multiple dimensions 48017.9 Equity interest rate hybrids 48217.10 Summary and conclusions 48617.11 Exercises and projects 48618 Advanced Monte Carlo I – Computing Greeks 48918.1 Introduction and objectives 48918.2 The finite difference method 48918.3 The pathwise method 49218.4 The likelihood ratio method 49718.5 Likelihood ratio for finite differences – proxy simulation 50318.6 Summary and conclusions 50418.7 Exercises and projects 50619 Advanced Monte Carlo II – Early Exercise 51119.1 Introduction and objectives 51119.2 Description of the problem 51119.3 Pricing American options by regression 51219.4 C++ design 51319.5 Linear least squares regression 51619.6 Example – step by step 52019.7 Analysis of the method and improvements 52119.8 Upper bounds 52519.9 Examples 52719.10 Summary and conclusions 52819.11 Exercises and projects 52820 Beyond Brownian Motion 53120.1 Introduction and objectives 53120.2 Normal mean variance mixture models 53120.3 The multi-dimensional case 53620.4 Summary and conclusions 53620.5 Exercises and projects 538PART IV SUPPLEMENTS21 C++ Application Optimisation and Performance Improvement 54321.1 Introduction and objectives 54321.2 Modelling functions in C++: choices and consequences 54321.3 Performance issues in C++: classifying potential bottlenecks 55221.4 Temporary objects 56021.5 Special features in the Boost library 56221.6 Boost multiarray library 56321.7 Boost random number library 56421.8 STL and Boost smart pointers: final remarks 56621.9 Summary and conclusions 56821.10 Exercises, projects and guidelines 56922 Random Number Generation and Distributions 57122.1 Introduction and objectives 57122.2 Uniform number generation 57122.3 The Sobol class 57822.4 Number generation due to given distributions 58022.5 Jump processes 58822.6 The random generator templates 59322.7 Tests for randomness 59622.8 Summary and conclusions 59622.9 Exercises and projects 59723 Some Mathematical Background 60123.1 Introduction and objectives 60123.2 A matrix class 60123.3 Matrix functions 60123.4 Functional analysis 60823.5 Applications to option pricing 61023.6 Summary and conclusions 61423.7 Exercises and projects 61424 An Introduction to Multi-threaded and Parallel Programming 61724.1 Introduction and objectives 61724.2 Shared memory models 61724.3 Sequential, concurrent and parallel programming 101 61924.4 How fast is fast? Performance analysis of parallel programs 62324.5 An introduction to processes and threads 62524.6 What kinds of applications are suitable for multi-threading? 62624.7 The multi-threaded application lifecycle 62724.8 Some model architectures 62924.9 Analysing and designing large software systems: a summary of the steps 63324.10 Conclusions and summary 63424.11 Exercises and projects 63425 An Introduction to OpenMP and its Applications to the Monte Carlo Method 63725.1 Introduction and objectives 63725.2 Loop optimisation 63725.3 An overview of OpenMP 64425.4 Threads in OpenMP 64425.5 Loop-level parallelism 64625.6 Data sharing 64625.7 Work-sharing and parallel regions 65125.8 Nested loop optimisation 65425.9 Scheduling in OpenMP 65625.10 OpenMP for the Monte Carlo method 65725.11 Conclusions and summary 66125.12 Exercises and projects 66126 A Case Study of Numerical Schemes for the Heston Model 66526.1 Introduction and objectives 66526.2 Test scenarios 66626.3 Numerical approximations for the Heston model 66726.4 Testing different schemes and scenarios 67226.5 Results 67526.6 Lessons learned 67826.7 Extensions, calibration and more 67926.8 Other numerical methods for Heston 68026.9 Summary and conclusions 68126.10 Exercises and projects 68127 Excel, C++ and Monte Carlo Integration 68527.1 Introduction and objectives 68527.2 Integrating applications and Excel 68627.3 ATL architecture 68627.4 Creating my first ATL project: the steps 69327.5 Creating automation add-ins in Excel 69527.6 Useful utilities and interoperability projects 69627.7 Test Case: a COM add-in and complete code 69727.8 Summary and conclusions 70727.9 Exercises and projects 707References 711Index 719