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

DOI:
https://doi.org/10.1090/mcom/3555

Published electronically:
July 20, 2020

MathSciNet review:
4166462

Full-text PDF

View in AMS MathViewer

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$.

- 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

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

Email:
hezhijian@scut.edu.cn

**Xiaoqun Wang**

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

Email:
wangxiaoqun@mail.tsinghua.edu.cn

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