Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Convergence analysis of quasi-Monte Carlo sampling for quantile and expected shortfall

Authors: Zhijian He and Xiaoqun Wang
Journal: Math. Comp. 90 (2021), 303-319
MSC (2010): Primary 65D30, 65C05
Published electronically: July 20, 2020
MathSciNet review: 4166462
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: Quantiles and expected shortfalls are usually used to measure risks of stochastic systems, which are often estimated by Monte Carlo methods. This paper focuses on the use of the quasi-Monte Carlo (QMC) method, whose convergence rate is asymptotically better than Monte Carlo in the numerical integration. We first prove the convergence of QMC-based quantile estimates under very mild conditions, and then establish a deterministic error bound of $O(N^{-1/d})$ for the quantile estimates, where $d$ is the dimension of the QMC point sets used in the simulation and $N$ is the sample size. Under certain conditions, we show that the mean squared error (MSE) of the randomized QMC estimate for expected shortfall is $o(N^{-1})$. Moreover, under stronger conditions the MSE can be improved to $O(N^{-1-1/(2d-1)+\epsilon })$ for arbitrarily small $\epsilon >0$.

References [Enhancements On Off] (What's this?)

  • A. N. Avramidis and J. R. Wilson, Correlation-induction techniques for estimating quantiles in simulation experiments, Oper. Res. 46 (1998), no. 4, 574–591.
  • R. R. Bahadur, A note on quantiles in large samples, Ann. Math. Statist. 37 (1966), 577–580. MR 189095, DOI 10.1214/aoms/1177699450
  • S. Chen, J. Dick, and A. B. Owen, Consistency of Markov chain quasi-Monte Carlo on continuous state spaces, Ann. Statist. 39 (2011), no. 2, 673–701. MR 2816335, DOI 10.1214/10-AOS831
  • Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394, DOI 10.1017/CBO9780511761188
  • Josef Dick, Frances Y. Kuo, and Ian H. Sloan, High-dimensional integration: the quasi-Monte Carlo way, Acta Numer. 22 (2013), 133–288. MR 3038697, DOI 10.1017/S0962492913000044
  • Hui Dong and Marvin K. Nakayama, Quantile estimation with Latin hypercube sampling, Oper. Res. 65 (2017), no. 6, 1678–1695. MR 3730800, DOI 10.1287/opre.2017.1637
  • P. Glasserman, P. Heidelberger, and P. Shahabuddin, Variance reduction techniques for estimating value-at-risk, Management Sci. 46 (2000), no. 10, 1349–1364.
  • P. W. Glynn, Importance Sampling for Monte Carlo Estimation of Quantiles, Mathematical Methods in Stochastic Simulation and Experimental Design: Proceedings of the 2nd St. Petersburg Workshop on Simulation, 1996, pp. 180–185.
  • Zhijian He and Art B. Owen, Extensible grids: uniform sampling on a space filling curve, J. R. Stat. Soc. Ser. B. Stat. Methodol. 78 (2016), no. 4, 917–931. MR 3534356, DOI 10.1111/rssb.12132
  • Zhijian He and Xiaoqun Wang, On the convergence rate of randomized quasi–Monte Carlo for discontinuous functions, SIAM J. Numer. Anal. 53 (2015), no. 5, 2488–2503. MR 3504603, DOI 10.1137/15M1007963
  • Zhijian He, Quasi-Monte Carlo for discontinuous integrands with singularities along the boundary of the unit cube, Math. Comp. 87 (2018), no. 314, 2857–2870. MR 3834688, DOI 10.1090/mcom/3324
  • L. Jeff Hong, Zhaolin Hu, and Guangwu Liu, Monte Carlo methods for value-at-risk and conditional value-at-risk: a review, ACM Trans. Model. Comput. Simul. 24 (2014), no. 4, Art. 22, 37. MR 3287091, DOI 10.1145/2661631
  • X. Jin, M. C. Fu, and X. Xiong, Probabilistic error bounds for simulation quantile estimators, Management Sci. 49 (2003), no. 2, 230–246.
  • X. Jin and A. X. Zhang, Reclaiming quasi-Monte Carlo efficiency in portfolio value-at-risk simulation through Fourier transform, Management Sci. 52 (2006), no. 6, 925–938.
  • Pierre L’Ecuyer, Quasi-Monte Carlo methods with applications in finance, Finance Stoch. 13 (2009), no. 3, 307–349. MR 2519835, DOI 10.1007/s00780-009-0095-y
  • Pierre L’Ecuyer and Christiane Lemieux, Recent advances in randomized quasi-Monte Carlo methods, Modeling uncertainty, Internat. Ser. Oper. Res. Management Sci., vol. 46, Kluwer Acad. Publ., Boston, MA, 2002, pp. 419–474. MR 1893290, DOI 10.1007/0-306-48102-2_{2}0
  • J. E. Marsden and M. J. Hoffman, Elementary Classical Analysis, Macmillan, 1993.
  • Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
  • Art B. Owen, Randomly permuted $(t,m,s)$-nets and $(t,s)$-sequences, Monte Carlo and quasi-Monte Carlo methods in scientific computing (Las Vegas, NV, 1994) Lect. Notes Stat., vol. 106, Springer, New York, 1995, pp. 299–317. MR 1445791, DOI 10.1007/978-1-4612-2552-2_{1}9
  • Art B. Owen, Monte Carlo variance of scrambled net quadrature, SIAM J. Numer. Anal. 34 (1997), no. 5, 1884–1910. MR 1472202, DOI 10.1137/S0036142994277468
  • A. B. Owen, Latin supercube sampling for very high-dimensional simulations, ACM Trans. Model. Comput. Simul. 8 (1998), no. 1, 71–102.
  • A. B. Owen, Multidimensional Variation for Quasi-Monte Carlo, International Conference on Statistics in honour of Professor K.-T. Fang’s 65th birthday (J. Fan and G. Li, eds.), 2005.
  • A. Papageorgiou and S. H. Paskov, Deterministic simulation for risk management, J. Portfolio Management 25 (1999), no. 5, 122–127.
  • Georg Ch. Pflug, Some remarks on the value-at-risk and the conditional value-at-risk, Probabilistic constrained optimization, Nonconvex Optim. Appl., vol. 49, Kluwer Acad. Publ., Dordrecht, 2000, pp. 272–281. MR 1819417, DOI 10.1007/978-1-4757-3150-7_{1}5
  • R Tyrrell Rockafellar and Stanislav Uryasev, Conditional value-at-risk for general loss distributions, J. Banking Finance 26 (2002), no. 7, 1443–1471.
  • Murray Rosenblatt, Remarks on a multivariate transformation, Ann. Math. Statistics 23 (1952), 470–472. MR 49525, DOI 10.1214/aoms/1177729394
  • Robert J. Serfling, Approximation theorems of mathematical statistics, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1980. MR 595165, DOI 10.1002/9780470316481
  • Lihua Sun and L. Jeff Hong, Asymptotic representations for importance-sampling estimators of value-at-risk and conditional value-at-risk, Oper. Res. Lett. 38 (2010), no. 4, 246–251. MR 2647231, DOI 10.1016/j.orl.2010.02.007
  • A. A. Trindade, S. Uryasev, A. Shapiro, and G. Zrazhevsky, Financial prediction with constrained tail risk, J. Banking Finance 31 (2007), no. 11, 3524–3538.
  • Houying Zhu and Josef Dick, Discrepancy bounds for deterministic acceptance-rejection samplers, Electron. J. Stat. 8 (2014), no. 1, 678–707. MR 3211028, DOI 10.1214/14-EJS898

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D30, 65C05

Retrieve articles in all journals with MSC (2010): 65D30, 65C05

Additional Information

Zhijian He
Affiliation: School of Mathematics, South China University of Technology, Guangzhou 510641, China
MR Author ID: 1056493

Xiaoqun Wang
Affiliation: Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Keywords: Quasi-Monte Carlo method, quantile, value-at-risk, expected shortfall, conditional value-at-risk
Received by editor(s): May 21, 2019
Received by editor(s) in revised form: January 5, 2020, and April 18, 2020
Published electronically: July 20, 2020
Additional Notes: This work was supported by the National Science Foundation of China (No. 71601189), the Fundamental Research Funds for the Central Universities (No. 2019MS106), the Research Funds of South China University of Technology (No. D6191160), and the National Key R&D Program of China (No. 2016QY02D0301).
Article copyright: © Copyright 2020 American Mathematical Society