An adaptive Monte Carlo algorithm for European and American options

Document Type : Research Paper


Insurance Research Center, Saadat Abad, Tehran, Iran.


In this paper, a new adaptive Monte Carlo algorithm is proposed to solve systems of linear algebraic equations (SLAEs). The corresponding properties of the algorithm and its advantages over the conventional and previous adaptive Monte Carlo algorithms are discussed and theoretical results are established to justify the convergence of the algorithm. Furthermore, the algorithm is used to solve the SLAEs obtained from finite difference method for the problem of European and American options pricing. Numerical tests are performed on examples with matrices of different sizes and on SLAEs coming from option pricing problems. Comparisons with standard numerical and stochastic algorithms are also done which demonstrate the computational efficiency of the proposed algorithm. 


  • [1]          V. N. Alexandrov, C. G. Martel, and J. Straßburg, Monte Carlo scalable algorithms for computational finance, Procedia Computer Science, 4 (2011), 1708–1715.
  • [2]          A. R. Bacinello, Regression-based algorithms for life insurance contracts with surrender guarantees, Quantitative Finance, 10(9) (2010), 1077–1090.
  • [3]          D. Bauer, A. Kling, and J. Rub, A universal pricing framework for guaranteed minimum benefits in variable annuities, ASTIN Bulletin, 38 (2008), 621–651.
  • [4]          M. H. Chiang, H. H. Fu, Y. T. Huang, C. L. Lo, and P. T. Shih, Analytical Approximations for American Options: The Binary Power Option Approach, Journal of Financial Studies, 26(3) (2018).
  • [5]          M. Dehghan and M. Hajarian, SSHI methods for solving general linear matrix equations, Engineering Computations, 2012.
  • [6]          I. Dimov, S. Maire, and J. M. Sellier, A new walk on equations Monte Carlo method for solving systems of linear algebraic equations, Appl. Math. Model, 39 (2015), 4494–4510
  • [7]          R. Farnoosh and M. Aalaei, New adaptive Monte Carlo algorithm for parallel solution of large linear systems with applications, Proceedings of the Romanian Academy Series A, 16(1) (2015), 11–19.
  • [8]          R. Farnoosh, M. Aalaei, and M. Ebrahimi, Combined probabilistic algorithm for solving high dimensional problems, Stochastics An International Journal of Probability and Stochastic Processes, 87(1) (2015), 30–47.
  • [9]          W. Hackbusch, Iterative Solution of Large Sparse Systems of Equations, Applied Mathematical Sciences, 95 (2016).
  • [10]        J. Halton, Sequential Monte Carlo, Proceedings of the Cambridge Philosophical Society, 58 (1962), 57–78.
  • [11]        C. H. Han and Y. Lai, A smooth estimator for MC/QMC methods in finance, Mathematics and Computers in simulation, 81(3) (2010), 536–550.
  • [12]        A. Jasra and P. D. Moral, Sequential Monte Carlo methods for option pricing, Stochastic analysis and applications, 29 (2011), 292–316.
  • [13]        F. Kiyoumarsi, European and American put valuation via a high-order semi-discretization scheme, Computational Methods for Differential Equations, 6(1) (2018), 63–79.
  • [14]        Y. Lai, Adaptive Monte Carlo methods for matrix equations with applications, Journal of Computational  and  Applied Mathematics, 231 (2009), 705–714.
  • [15]        R. Y. Rubinstein, Simulation and the Monte Carlo method, Wiley, New York, 1981.
  • [16]        D.Y. Tangman, A. Gopaul, and M. Bhuruth, A fast high-order finite difference algorithm for pricing American options, J. Comput. Appl. Math., 222 (2008), 17–29.
  • [17]        I. Vidid, Numerical methods for option pricing, Master Thesis, Master in Advanced Computing for Science and Engineering, Politecnica University, 2012.