×

Primal-dual quasi-Monte Carlo simulation with dimension reduction for pricing American options. (English) Zbl 1454.91362

Summary: The pricing of American options is one of the most challenging problems in financial engineering due to the involved optimal stopping time problem, which can be solved by using dynamic programming (DP). But applying DP is not always practical, especially when the state space is high dimensional. However, the curse of dimensionality can be overcome by Monte Carlo (MC) simulation. We can get lower and upper bounds by MC to ensure that the true price falls into a valid confidence interval. During the recent decades, progress has been made in using MC simulation to obtain both the lower bound by least-squares Monte Carlo method (LSM) and the upper bound by duality approach. However, there are few works on pricing American options using quasi-Monte Carlo (QMC) methods, especially to compute the upper bound. For comparing the sample variances and standard errors in the numerical experiments, randomized QMC (RQMC) methods are usually used. In this paper, we propose to use RQMC to replace MC simulation to compute both the lower bound (by the LSM) and the upper bound (by the duality approach). Moreover, we propose to use dimension reduction techniques, such as the Brownian bridge, principal component analysis, linear transformation and the gradients based principle component analysis. We perform numerical experiments on American-Asian options and American max-call options under the Black-Scholes model and the variance gamma model, in which the options have the path-dependent feature or are written on multiple underlying assets. We find that RQMC in combination with dimension reduction techniques can significantly increase the efficiency in computing both the lower and upper bounds, resulting in better estimates and tighter confidence intervals of the true price than pure MC simulation.

MSC:

91G60 Numerical methods (including Monte Carlo methods)
65C05 Monte Carlo methods
91G20 Derivative securities (option pricing, hedging, etc.)
60G40 Stopping times; optimal stopping problems; gambling theory

Software:

Lattice Builder
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Acworth, P. , Broadie, M. and Glasserman, P. , A comparison of some Monte Carlo and quasi-Monte Carlo techniques for option pricing. Monte Carlo and Quasi-Monte Carlo Methods 1996, pp. 1-18, 1998 (Springer: New York). · Zbl 0888.90010
[2] Andersen, L. and Broadie, M. , A primal-dual simulation algorithm for pricing multidimensional American options. Manage. Sci. , 2004, 50 , 1222-1234. doi: 10.1287/mnsc.1040.0258 · doi:10.1287/mnsc.1040.0258
[3] Avramidis, A.N. and L’Ecuyer, P. , Efficient Monte Carlo and quasi-Monte Carlo option pricing under the variance gamma model. Manage. Sci. , 2006, 52 , 1930-1944. doi: 10.1287/mnsc.1060.0575 · Zbl 1232.91700 · doi:10.1287/mnsc.1060.0575
[4] Barraquand, J. and Martineau, D. , Numerical valuation of high dimensional multivariate American securities. J. Finance Quant. Anal. , 1995, 30 , 383-405. doi: 10.2307/2331347 · doi:10.2307/2331347
[5] Belomestny, D. and Milstein, G. , Monte Carlo evaluation of American options using consumption processes. Int. J. Theor. Appl. Finance , 2006, 9 , 455-481. doi: 10.1142/S0219024906003652 · Zbl 1184.91209 · doi:10.1142/S0219024906003652
[6] Belomestny, D. , Milstein, G. and Spokoiny, V. , Regression methods in pricing American and Bermudan options using consumption processes. Quant. Finance , 2009a, 9 , 315-327. doi: 10.1080/14697680802165736 · Zbl 1169.91338
[7] Belomestny, D. , Bender, C. and Schoenmakers, J. , True upper bounds for Bermudan products via non-nested Monte Carlo. Math. Finance , 2009b, 19 , 53-71. doi: 10.1111/j.1467-9965.2008.00357.x · Zbl 1155.91376 · doi:10.1111/j.1467-9965.2008.00357.x
[8] Belomestny, D. , Schoenmakers, J. , Spokoiny, V. and Zharkynbay, B. , Optimal stopping via reinforced regression. Preprint, 2018. arXiv:1808.02341. · Zbl 1440.60032
[9] Ben Ameur, H. , Breton, M. and L’Ecuyer, P. , A dynamic programming procedure for pricing American-style Asian options. Manage. Sci. , 2002, 48 , 625-643. doi: 10.1287/mnsc.48.5.625.7803 · Zbl 1232.91645 · doi:10.1287/mnsc.48.5.625.7803
[10] Ben-Ameur, H. , Breton, M. , Karoui, L. and L’Ecuyer, P. , A dynamic programming approach for pricing options embedded in bonds. J. Econ. Dyn. Control , 2007, 31 , 2212-2233. doi: 10.1016/j.jedc.2006.06.007 · Zbl 1163.91380 · doi:10.1016/j.jedc.2006.06.007
[11] Boyle, P.P. , Options: A Monte Carlo approach. J. Finance Econ. , 1977, 4 , 323-338. doi: 10.1016/0304-405X(77)90005-8 · doi:10.1016/0304-405X(77)90005-8
[12] Boyle, P.P. , Kolkiewicz, A. and Tan, K.S. , Pricing Bermudan style options using low discrepancy mesh methods. Quant. Finance , 2013, 13 , 841-860. doi: 10.1080/14697688.2013.776699 · Zbl 1281.91181
[13] Brennan, M.J. and Schwartz, E.S. , The valuation of American put option. J. Finance , 1977, 32 , 449-462. doi: 10.2307/2326779 · doi:10.2307/2326779
[14] Broadie, M. and Glasserman, P. , Pricing American-style securities using simulation. J. Econ. Dyn. Control , 1997, 21 , 1323-1352. doi: 10.1016/S0165-1889(97)00029-8 · Zbl 0901.90009 · doi:10.1016/S0165-1889(97)00029-8
[15] Broadie, M. and Glasserman, P. , A stochastic mesh method for pricing high-dimensional American options. J. Comput. Finance , 2004, 7 , 35-72. doi: 10.21314/JCF.2004.117 · doi:10.21314/JCF.2004.117
[16] Caflisch, R.E. , Morokoff, W.J. and Owen, A.B. , Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension. J. Comput. Finance , 1997, 1 , 27-46. doi: 10.21314/JCF.1997.005 · doi:10.21314/JCF.1997.005
[17] Carrière, J.F. , Valuation of the early-exercise price for options using simulations and nonparametric regression. Insur. Math. Econ. , 1996, 19 , 19-30. doi: 10.1016/S0167-6687(96)00004-2 · Zbl 0894.62109 · doi:10.1016/S0167-6687(96)00004-2
[18] Chaudhary, S.K. , American options and the LSM algorithm: Quasi-random sequences and Brownian bridges. J. Comput. Finance , 2005, 8 , 101-115. doi: 10.21314/JCF.2005.132 · doi:10.21314/JCF.2005.132
[19] Clément, E. , Lamberton, D. and Protter, P. , An analysis of a least squares regression method for American option pricing. Finance Stoch. , 2002, 6 , 449-471. doi: 10.1007/s007800200071 · Zbl 1039.91020 · doi:10.1007/s007800200071
[20] Couffignals, E. , Quasi-Monte Carlo simulations for Longstaff Schwartz pricing of American options. Master Thesis, University of Oxford, 2010.
[21] Cox, J. , Ross, S. and Rubinstein, M. , Option pricing: A simplified approach. J. Finance Econ. , 1979, 7 , 229-263. doi: 10.1016/0304-405X(79)90015-1 · Zbl 1131.91333 · doi:10.1016/0304-405X(79)90015-1
[22] Dick, J. and Pillichshammer, F. , Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration , 2010 (Cambridge University Press: Cambridge). · Zbl 1282.65012 · doi:10.1017/CBO9780511761188
[23] Dion, M. and L’Ecuyer, P. , American option pricing with randomized quasi-Monte Carlo simulations. WSC10: Winter Simulation Conference, Baltimore, MD, December 2010, pp. 2705-2720, 2011.
[24] Glasserman, P. , Monte Carlo Methods in Financial Engineering , 2003 (Springer-Verlag: New York). · doi:10.1007/978-0-387-21617-1
[25] Haugh, M.B. and Kogan, L. , Pricing American options: A duality approach. Oper. Res. , 2004, 52 , 258-270. doi: 10.1287/opre.1030.0070 · Zbl 1165.91401 · doi:10.1287/opre.1030.0070
[26] Imai, J. and Tan, K.S. , A general dimension reduction technique for derivative pricing. J. Comput. Finance , 2006, 10 , 129-155. doi: 10.21314/JCF.2006.143 · doi:10.21314/JCF.2006.143
[27] Joy, C. , Boyle, P.P. and Tan, K.S. , Quasi-Monte Carlo methods in numerical finance. Manage. Sci. , 1996, 42 , 926-938. doi: 10.1287/mnsc.42.6.926 · Zbl 0880.90006 · doi:10.1287/mnsc.42.6.926
[28] Kohler, M. , A review on regression-based Monte Carlo methods for pricing American options. Recent Developments in Applied Probability and Statistics, pp. 37-58, 2010 (Springer-Verlag: Berlin). · Zbl 1203.91295 · doi:10.1007/978-3-7908-2598-5_2
[29] L’Ecuyer, P. , Quasi-Monte Carlo methods with applications in finance. Finance Stoch. , 2009, 13 , 307-349. doi: 10.1007/s00780-009-0095-y · Zbl 1199.65004 · doi:10.1007/s00780-009-0095-y
[30] L’Ecuyer, P. and Munger, D. , On figures of merit for randomly-shifted lattice rules. Proceedings of the Monte Carlo and Quasi-Monte Carlo Methods 2010, edited by L. Plaskota and H. Woźniakowski, pp. 133-159, 2012 (Springer: Berlin Heidelberg). · Zbl 1271.65045
[31] L’Ecuyer, P. and Munger, D. , Algorithm 958: LatticeBuilder: A general software tool for constructing rank-1 lattice rules. ACM Trans. Math. Softw. , 2016, 42 , 1-30. doi: 10.1145/2754929 · doi:10.1145/2754929
[32] L’Ecuyer, P. and Simard, R.J. , Inverting the symmetrical beta distribution. ACM Trans. Math. Softw. , 2006, 32 , 509-520. doi: 10.1145/1186785.1186786 · Zbl 1230.65014 · doi:10.1145/1186785.1186786
[33] L’Ecuyer, P. , Parent-Chartier, J.S. and Dion, M. , Simulation of a Lévy process by PCA sampling to reduce the effective dimension. Proceedings of the 40th Conference on Winter Simulation, pp. 436-443, 2008.
[34] Lemieux, C. , Monte Carlo and Quasi-Monte Carlo Sampling , 2009 (Springer: New York). · Zbl 1269.65001
[35] Lemieux, C. and La, J. , A study of variance reduction techniques for American option pricing. Proceedings of the 37th Winter Simulation Conference, Orlando, FL, 4-7 December, pp. 1884-1891, 2005.
[36] Longstaff, F.A. and Schwartz, E.S. , Valuing American options by simulation: A simple least-squares approach. Rev. Finance Stud. , 2001, 14 , 113-147. doi: 10.1093/rfs/14.1.113 · Zbl 1386.91144 · doi:10.1093/rfs/14.1.113
[37] Madan, D.B. and Seneta, E. , The variance gamma (V.G.) model for share market returns. J. Bus. , 1990, 63 , 511-524. doi: 10.1086/296519 · doi:10.1086/296519
[38] Madan, D.B. , Carr, P.P. and Chang, E.C. , The variance gamma process and option pricing. Rev. Finance , 1998, 2 , 79-105. doi: 10.1023/A:1009703431535 · Zbl 0937.91052 · doi:10.1023/A:1009703431535
[39] Moreno, M. and Navas, J.F. , On the robustness of least-squares Monte Carlo (LSM) for pricing American derivatives. Rev. Deriv. Res. , 2003, 6 , 107-128. doi: 10.1023/A:1027340210935 · Zbl 1059.91047 · doi:10.1023/A:1027340210935
[40] Morokoff, W.J. and Caflisch, R.E. , Quasi-random sequences and their discrepancies. SIAM J. Sci. Comput. , 1994, 15 , 1251-1279. doi: 10.1137/0915077 · Zbl 0815.65002 · doi:10.1137/0915077
[41] Moskowitz, B. and Caflisch, R.E. , Smoothness and dimension reduction in quasi-Monte Carlo methods. Math. Comput. Model. , 1996, 23 , 37-54. doi: 10.1016/0895-7177(96)00038-6 · Zbl 0858.65023 · doi:10.1016/0895-7177(96)00038-6
[42] Niederreiter, H. , Random Number Generation and Quasi-Monte Carlo Methods , 1992 (SIAM: Philadelphia). · Zbl 0761.65002 · doi:10.1137/1.9781611970081
[43] Paskov, S.H. and Traub, J.F. , Faster valuation of financial derivatives. J. Portfolio Manage. , 1995, 22 , 113-123. doi: 10.3905/jpm.1995.409541 · doi:10.3905/jpm.1995.409541
[44] Rogers, L. , Monte Carlo valuation of American options. Math. Finance , 2002, 12 , 271-286. doi: 10.1111/1467-9965.02010 · Zbl 1029.91036 · doi:10.1111/1467-9965.02010
[45] Sobol’, I. , Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates. Math. Comput. Simul. , 2001, 55 , 271-280. doi: 10.1016/S0378-4754(00)00270-6 · Zbl 1005.65004 · doi:10.1016/S0378-4754(00)00270-6
[46] Stentoft, L. , Convergence of the least squares Monte Carlo approach to American option valuation. Manage. Sci. , 2004, 50 , 1193-1203. doi: 10.1287/mnsc.1030.0155 · Zbl 1080.91041 · doi:10.1287/mnsc.1030.0155
[47] Tilley, J.A. , Valuing American options in a path simulation model. Trans. Soc. Act. , 1993, 45 , 499-550.
[48] Tsitsiklis, J.N. and Van Roy, B. , Regression methods for pricing complex American-style options. IEEE Trans. Neural Netw. , 2001, 12 , 694-703. doi: 10.1109/72.935083 · doi:10.1109/72.935083
[49] Wang, X. , On the effects of dimension reduction techniques on some high-dimensional problems in finance. Oper. Res. , 2006, 54 , 1063-1078. doi: 10.1287/opre.1060.0334 · Zbl 1167.91376 · doi:10.1287/opre.1060.0334
[50] Wang, X. , Constructing robust good lattice rules for computational finance. SIAM J. Sci. Comput. , 2007, 29 , 598-621. doi: 10.1137/060650714 · Zbl 1132.91481 · doi:10.1137/060650714
[51] Wang, X. , Dimension reduction techniques in quasi-Monte Carlo methods for option pricing. Informs J. Comput. , 2009, 21 , 488-504. doi: 10.1287/ijoc.1080.0304 · Zbl 1243.91105 · doi:10.1287/ijoc.1080.0304
[52] Wang, X. and Fang, K.T. , The effective dimension and quasi-Monte Carlo integration. J. Complexity , 2003, 19 , 101-124. doi: 10.1016/S0885-064X(03)00003-7 · Zbl 1021.65002 · doi:10.1016/S0885-064X(03)00003-7
[53] Wang, X. and Sloan, I.H. , Low discrepancy sequences in high dimensions: How well are their projections distributed? J. Comput. Appl. Math. , 2008, 213 , 366-386. doi: 10.1016/j.cam.2007.01.005 · Zbl 1144.65003 · doi:10.1016/j.cam.2007.01.005
[54] Xiao, Y. and Wang, X. , Enhancing quasi-Monte Carlo simulation by minimizing effective dimension for derivative pricing. Comput. Econ. , 2017, 1 , 343-366.
[55] Zanger, D. , Convergence of a least-squares Monte Carlo algorithm for bounded approximating sets. Appl. Math. Finance , 2009, 16 , 123-150. doi: 10.1080/13504860802516881 · Zbl 1169.91346
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.