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 xxiii

0 My First Monte Carlo Application One-Factor Problems 1

0.1 Introduction and objectives 1

0.2 Description of the problem 1

0.3 Ordinary differential equations (ODE) 2

0.4 Stochastic differential equations (SDE) and their solution 3

0.5 Generating uniform and normal random numbers 4

0.6 The Monte Carlo method 8

0.7 Calculating sensitivities 9

0.8 The initial C++ Monte Carlo framework: hierarchy and paths 10

0.9 The initial C++ Monte Carlo framework: calculating option price 19

0.10 The predictor-corrector method: a scheme for all seasons? 23

0.11 The Monte Carlo approach: caveats and nasty surprises 24

0.12 Summary and conclusions 25

0.13 Exercises and projects 25

PART I FUNDAMENTALS

1 Mathematical Preparations for the Monte Carlo Method 31

1.1 Introduction and objectives 31

1.2 Random variables 31

1.3 Discrete and continuous random variables 34

1.4 Multiple random variables 37

1.5 A short history of integration 38

1.6 σ-algebras, measurable spaces and measurable functions 39

1.7 Probability spaces and stochastic processes 40

1.8 The Ito stochastic integral 41

1.9 Applications of the Lebesgue theory 43

1.10 Some useful inequalities 45

1.11 Some special functions 46

1.12 Convergence of function sequences 48

1.13 Applications to stochastic analysis 49

1.14 Summary and conclusions 50

1.15 Exercises and projects 50

2 The Mathematics of Stochastic Differential Equations (SDE) 53

2.1 Introduction and objectives 53

2.2 A survey of the literature 53

2.3 Mathematical foundations for SDEs 55

2.4 Motivating random (stochastic) processes 59

2.5 An introduction to one-dimensional random processes 59

2.6 Stochastic differential equations in Banach spaces: prologue 62

2.7 Classes of SIEs and properties of their solutions 62

2.8 Existence and uniqueness results 63

2.9 A special SDE: the Ito equation 64

2.10 Numerical approximation of SIEs 66

2.11 Transforming an SDE: the Ito formula 68

2.12 Summary and conclusions 69

2.13 Appendix: proof of the Banach fixed-point theorem and some applications 69

2.14 Exercises and projects 71

3 Alternative SDEs and Toolkit Functionality 73

3.1 Introduction and objectives 73

3.2 Bessel processes 73

3.3 Random variate generation 74

3.4 The exponential distribution 74

3.5 The beta and gamma distributions 75

3.6 The chi-squared, Student and other distributions 79

3.7 Discrete variate generation 79

3.8 The Fokker-Planck equation 80

3.9 The relationship with PDEs 81

3.10 Alternative stochastic processes 84

3.11 Using associative arrays and matrices to model lookup tables and volatility surfaces 93

3.12 Summary and conclusion 96

3.13 Appendix: statistical distributions and special functions in the Boost library 97

3.14 Exercises and projects 102

4 An Introduction to the Finite Difference Method for SDE 107

4.1 Introduction and objectives 107

4.2 An introduction to discrete time simulation, motivation and notation 107

4.3 Foundations of discrete time approximation: ordinary differential equations 109

4.4 Foundations of discrete time approximation: stochastic differential equations 113

4.5 Some common schemes for one-factor SDEs 117

4.6 The Milstein schemes 117

4.7 Predictor-corrector methods 118

4.8 Stiff ordinary and stochastic differential equations 119

4.9 Software design and C++ implementation issues 125

4.10 Computational results 126

4.11 Aside: the characteristic equation of a difference scheme 127

4.12 Summary and conclusions 128

4.13 Exercises and projects 128

5 Design and Implementation of Finite Difference Schemes in Computational Finance 137

5.1 Introduction and objectives 137

5.2 Modelling SDEs and FDM in C++ 137

5.3 Mathematical and numerical tools 138

5.4 The Karhunen-Loeve expansion 143

5.5 Cholesky decomposition 144

5.6 Spread options with stochastic volatility 146

5.7 The Heston stochastic volatility model 153

5.8 Path-dependent options and the Monte Carlo method 160

5.9 A small software framework for pricing options 161

5.10 Summary and conclusions 162

5.11 Exercises and projects 162

6 Advanced Finance Models and Numerical Methods 167

6.1 Introduction and objectives 167

6.2 Processes with jumps 168

6.3 Levy processes 171

6.4 Measuring the order of convergence 172

6.5 Mollifiers, bump functions and function regularisation 176

6.6 When Monte Carlo does not work: counterexamples 177

6.7 Approximating SDEs using strong Taylor, explicit and implicit schemes 179

6.8 Summary and conclusions 183

6.9 Exercises and projects 184

7 Foundations of the Monte Carlo Method 189

7.1 Introduction and objectives 189

7.2 Basic probability 189

7.3 The Law of Large Numbers 190

7.4 The Central Limit Theorem 191

7.5 Quasi Monte Carlo methods 194

7.6 Summary and conclusions 198

7.7 Exercises and projects 198

PART II DESIGN PATTERNS

8 Architectures and Frameworks for Monte Carlo Methods: Overview 203

8.1 Goals of Part II of this book 203

8.2 Introduction and objectives of this chapter 203

8.3 The advantages of domain architectures 204

8.4 Software Architectures for the Monte Carlo method 207

8.5 Summary and conclusions 212

8.6 Exercises and projects 213

9 System Decomposition and System Patterns 217

9.1 Introduction and objectives 217

9.2 Software development process; a critique 217

9.3 System decomposition, from concept to code 217

9.4 Decomposition techniques, the process 220

9.5 Whole-part 222

9.6 Whole-part decomposition; the process 223

9.7 Presentation-Abstraction Control (PAC) 226

9.8 Building complex objects and configuring applications 229

9.9 Summary and conclusions 239

9.10 Exercises and projects 239

10 Detailed Design using the GOF Patterns 243

10.1 Introduction and objectives 243

10.2 Discovering which patterns to use 244

10.3 An overview of the GOF patterns 255

10.4 The essential structural patterns 257

10.5 The essential creational patterns 266

10.6 The essential behavioural patterns 270

10.7 Summary and conclusions 276

10.8 Exercises and projects 276

11 Combining Object-Oriented and Generic Programming Models 281

11.1 Introduction and objectives 281

11.2 Using templates to implement components: overview 281

11.3 Templates versus inheritance, run-time versus compile-time 283

11.4 Advanced C++ templates 286

11.5 Traits and policy-based design 294

11.6 Creating templated design patterns 306

11.7 A generic Singleton pattern 307

11.8 Generic composite structures 310

11.9 Summary and conclusions 314

11.10 Exercises and projects 314

12 Data Structures and their Application to the Monte Carlo Method 319

12.1 Introduction and objectives 319

12.2 Arrays, vectors and matrices 319

12.3 Compile-time vectors and matrices 324

12.4 Creating adapters for STL containers 331

12.5 Date and time classes 334

12.6 The class string 339

12.7 Modifying strings 343

12.8 A final look at the generic composite 345

12.9 Summary and conclusions 348

12.10 Exercises and projects 348

13 The Boost Library: An Introduction 353

13.1 Introduction and objectives 353

13.2 A taxonomy of C++ pointer types 353

13.3 Modelling homogeneous and heterogeneous data in Boost 361

13.4 Boost signals: notification and data synchronisation 367

13.5 Input and output 368

13.6 Linear algebra and uBLAS 371

13.7 Date and time 372

13.8 Other libraries 372

13.9 Summary and conclusions 374

13.10 Exercises and projects 374

PART III ADVANCED APPLICATIONS

14 Instruments and Payoffs 379

14.1 Introduction and objectives 379

14.2 Creating a C++ instrument hierarchy 379

14.3 Modelling payoffs in C++ 383

14.4 Summary and conclusions 392

14.5 Exercises and projects 393

15 Path-Dependent Options 395

15.1 Introduction and objectives 395

15.2 Monte Carlo – a simple general-purpose version 396

15.3 Asian options 401

15.4 Options on the running Max/Min 411

15.5 Barrier options 412

15.6 Lookback options 418

15.7 Cliquet Options 422

15.8 Summary and conclusions 424

15.9 Exercises and projects 424

16 Affine Stochastic Volatility Models 427

16.1 Introduction and objectives 427

16.2 The volatility skew/smile 427

16.3 The Heston model 429

16.4 The Bates/SVJ model 441

16.5 Implementing the Bates model 443

16.6 Numerical results – European options 444

16.7 Numerical results – skew-dependent options 446

16.8 XLL – using DLL within Microsoft Excel 449

16.9 Analytic solutions for affine stochastic volatility models 455

16.10 Summary and conclusions 457

16.11 Exercises and projects 458

17 Multi-Asset Options 461

17.1 Introduction and objectives 461

17.2 Modelling in multiple dimensions 461

17.3 Implementing payoff classes for multi-asset options 465

17.4 Some multi-asset options 466

17.5 Basket options 469

17.6 Min/Max options 471

17.7 Mountain range options 475

17.8 The Heston model in multiple dimensions 480

17.9 Equity interest rate hybrids 482

17.10 Summary and conclusions 486

17.11 Exercises and projects 486

18 Advanced Monte Carlo I – Computing Greeks 489

18.1 Introduction and objectives 489

18.2 The finite difference method 489

18.3 The pathwise method 492

18.4 The likelihood ratio method 497

18.5 Likelihood ratio for finite differences – proxy simulation 503

18.6 Summary and conclusions 504

18.7 Exercises and projects 506

19 Advanced Monte Carlo II – Early Exercise 511

19.1 Introduction and objectives 511

19.2 Description of the problem 511

19.3 Pricing American options by regression 512

19.4 C++ design 513

19.5 Linear least squares regression 516

19.6 Example – step by step 520

19.7 Analysis of the method and improvements 521

19.8 Upper bounds 525

19.9 Examples 527

19.10 Summary and conclusions 528

19.11 Exercises and projects 528

20 Beyond Brownian Motion 531

20.1 Introduction and objectives 531

20.2 Normal mean variance mixture models 531

20.3 The multi-dimensional case 536

20.4 Summary and conclusions 536

20.5 Exercises and projects 538

PART IV SUPPLEMENTS

21 C++ Application Optimisation and Performance Improvement 543

21.1 Introduction and objectives 543

21.2 Modelling functions in C++: choices and consequences 543

21.3 Performance issues in C++: classifying potential bottlenecks 552

21.4 Temporary objects 560

21.5 Special features in the Boost library 562

21.6 Boost multiarray library 563

21.7 Boost random number library 564

21.8 STL and Boost smart pointers: final remarks 566

21.9 Summary and conclusions 568

21.10 Exercises, projects and guidelines 569

22 Random Number Generation and Distributions 571

22.1 Introduction and objectives 571

22.2 Uniform number generation 571

22.3 The Sobol class 578

22.4 Number generation due to given distributions 580

22.5 Jump processes 588

22.6 The random generator templates 593

22.7 Tests for randomness 596

22.8 Summary and conclusions 596

22.9 Exercises and projects 597

23 Some Mathematical Background 601

23.1 Introduction and objectives 601

23.2 A matrix class 601

23.3 Matrix functions 601

23.4 Functional analysis 608

23.5 Applications to option pricing 610

23.6 Summary and conclusions 614

23.7 Exercises and projects 614

24 An Introduction to Multi-threaded and Parallel Programming 617

24.1 Introduction and objectives 617

24.2 Shared memory models 617

24.3 Sequential, concurrent and parallel programming 101 619

24.4 How fast is fast? Performance analysis of parallel programs 623

24.5 An introduction to processes and threads 625

24.6 What kinds of applications are suitable for multi-threading? 626

24.7 The multi-threaded application lifecycle 627

24.8 Some model architectures 629

24.9 Analysing and designing large software systems: a summary of the steps 633

24.10 Conclusions and summary 634

24.11 Exercises and projects 634

25 An Introduction to OpenMP and its Applications to the Monte Carlo Method 637

25.1 Introduction and objectives 637

25.2 Loop optimisation 637

25.3 An overview of OpenMP 644

25.4 Threads in OpenMP 644

25.5 Loop-level parallelism 646

25.6 Data sharing 646

25.7 Work-sharing and parallel regions 651

25.8 Nested loop optimisation 654

25.9 Scheduling in OpenMP 656

25.10 OpenMP for the Monte Carlo method 657

25.11 Conclusions and summary 661

25.12 Exercises and projects 661

26 A Case Study of Numerical Schemes for the Heston Model 665

26.1 Introduction and objectives 665

26.2 Test scenarios 666

26.3 Numerical approximations for the Heston model 667

26.4 Testing different schemes and scenarios 672

26.5 Results 675

26.6 Lessons learned 678

26.7 Extensions, calibration and more 679

26.8 Other numerical methods for Heston 680

26.9 Summary and conclusions 681

26.10 Exercises and projects 681

27 Excel, C++ and Monte Carlo Integration 685

27.1 Introduction and objectives 685

27.2 Integrating applications and Excel 686

27.3 ATL architecture 686

27.4 Creating my first ATL project: the steps 693

27.5 Creating automation add-ins in Excel 695

27.6 Useful utilities and interoperability projects 696

27.7 Test Case: a COM add-in and complete code 697

27.8 Summary and conclusions 707

27.9 Exercises and projects 707

References 711

Index 719