×

Monte Carlo and quasi-Monte Carlo density estimation via conditioning. (English) Zbl 07552232

Summary: Estimating the unknown density from which a given independent sample originates is more difficult than estimating the mean in the sense that, for the best popular nonparametric density estimators, the mean integrated square error converges more slowly than at the canonical rate of \(\mathcal{O} ( 1 / n )\). When the sample is generated from a simulation model and we have control over how this is done, we can do better. We examine an approach in which conditional Monte Carlo yields, under certain conditions, a random conditional density that is an unbiased estimator of the true density at any point. By averaging independent replications, we obtain a density estimator that converges at a faster rate than the usual ones. Moreover, combining this new type of estimator with randomized quasi-Monte Carlo to generate the samples typically brings a larger improvement on the error and convergence rate than for the usual estimators because the new estimator is smoother as a function of the underlying uniform random numbers.
Summary of contribution: Stochastic simulation is commonly used to estimate the mathematical expectation of some output random variable \(X\) together with a confidence interval for this expectation. But the simulations usually provide information to do much more, such as estimating the entire distribution (or density) of \(X\). Histograms are routinely provided by standard simulation software, but they are very primitive density estimators. Kernel density estimators perform better, but they are trickier to use, have bias, and their mean square error converges more slowly than the canonical rate of \(O(1/n)\) with \(n\) independent samples. In this paper, we explain how to construct unbiased density estimators that converge at the canonical rate and even much faster when combined with randomized quasi-Monte Carlo. The key idea is to use conditional Monte Carlo to hide appropriate information and obtain a computable (random) conditional density, which acts (under certain conditions) as an unbiased density estimator. Moreover, this sample density is typically smoother than the classic density estimators as a function of the underlying uniform random numbers, so it can get along much better with randomized quasi-Monte Carlo methods. This offers an opportunity to further improve the \(O(1/n)\) rate. We observe rates near \(O(1/n^2)\) on some examples, and we give conditions under which this type of rate provably holds. The proposed approach is simple, easy to implement, and extremely effective, so it provides a significant addition to the stochastic simulation toolbox.

MSC:

90-XX Operations research, mathematical programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Asmussen S (2018) Conditional Monte Carlo for sums, with applications to insurance and finance. Ann. Actuarial Sci. 12(2):455-478.Crossref, Google Scholar · doi:10.1017/S1748499517000252
[2] Asmussen S, Glynn PW (2007) Stochastic Simulation (Springer-Verlag, New York).Google Scholar · Zbl 1126.65001
[3] Avramidis AN, L’Ecuyer P (2006) Efficient Monte Carlo and quasi-Monte Carlo option pricing under the variance-gamma model. Management Sci. 52(12):1930-1944.Link, Google Scholar · Zbl 1232.91700
[4] Avramidis AN, Wilson JR (1996) Integrated variance reduction strategies for simulation. Oper. Res. 44(2):327-346.Link, Google Scholar · Zbl 0857.65149
[5] Avramidis AN, Wilson JR (1998) Correlation-induction techniques for estimating quantiles in simulation experiments. Oper. Res. 46(4):574-591.Link, Google Scholar · Zbl 1009.62598
[6] Ben Abdellah A, L’Ecuyer P, Owen A, Puchhammer F (2021) Density estimation by randomized quasi-Monte Carlo. SIAM J. Uncertainty Quantification 9(1):280-301.Crossref, Google Scholar · Zbl 1462.62224 · doi:10.1137/19M1259213
[7] Bingham D (2017) Virtual library of simulation experiments. Accessed December 19, 2021, https://www.sfu.ca/ ssurjano/canti.html.Google Scholar
[8] Boyle P, Broadie M, Glasserman P (1997) Monte Carlo methods for security pricing. J. Econom. Dynamic Control 21(8-9):1267-1321.Crossref, Google Scholar · Zbl 0901.90007 · doi:10.1016/S0165-1889(97)00028-6
[9] Bratley P, Fox BL, Schrage LE (1987) A Guide to Simulation, 2nd ed. (Springer-Verlag, New York).Crossref, Google Scholar · doi:10.1007/978-1-4419-8724-2
[10] Caflisch RE, Morokoff W, Owen A (1997) Valuation of mortgage-backed securities using Brownian bridges to reduce effective dimension. J. Comput. Finance 1(1):27-46.Crossref, Google Scholar · doi:10.21314/JCF.1997.005
[11] Choquet D, L’Ecuyer P, Léger C (1999) Bootstrap confidence intervals for ratios of expectations. ACM Trans. Model. Comput. Simulation 9(4):326-348.Crossref, Google Scholar · Zbl 1391.65027 · doi:10.1145/352222.352224
[12] Cui Z, Fu MC, Hu JQ, Liu Y, Peng Y, Zhu L (2020) On the variance of single-run unbiased stochastic derivative estimators. INFORMS J. Comput. 32(2):390-407.Abstract, Google Scholar · Zbl 07290853
[13] Dick J, Pillichshammer F (2010) Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar · Zbl 1282.65012 · doi:10.1017/CBO9780511761188
[14] Dieudonné J (1969) Foundations of Modern Analysis, 2nd ed. (Academic Press, New York).Google Scholar · Zbl 0176.00502
[15] Efron B, Hastie T (2016) Computer Age Statistical Inference (Cambridge University Press, New York).Crossref, Google Scholar · Zbl 1377.62004 · doi:10.1017/CBO9781316576533
[16] Fu MC (2006) Sensitivity analysis in Monte Carlo simulation of stochastic activity networks. Alt FB, Fu MC, Golden BL, eds. Perspectives in Operations Research, Operations Research/Computer Science Interfaces Series (Springer, Boston), 351-366.Crossref, Google Scholar · Zbl 1113.90150 · doi:10.1007/978-0-387-39934-8_20
[17] Fu MC, Hu JQ (1997) Conditional Monte Carlo (Kluwer Academic, Boston).Crossref, Google Scholar · doi:10.1007/978-1-4615-6293-1
[18] Fu MC, Hong LJ, Hu JQ (2009) Conditional Monte Carlo estimation of quantile sensitivities. Management Sci. 55(12):2019-2027.Link, Google Scholar · Zbl 1232.91704
[19] Glasserman P (2004) Monte Carlo Methods in Financial Engineering (Springer-Verlag, New York).Crossref, Google Scholar · Zbl 1038.91045 · doi:10.1007/978-0-387-21617-1
[20] Glynn PW (1987) Likelihood ratio gradient estimation: An overview. Thesen A, Grant H, Kelton WD, eds. Proc. 1987 Winter Simulation Conf. (IEEE Press, Piscataway, NJ), 366-375.Google Scholar
[21] Gong WB, Ho YC (1987) Smoothed (conditional) perturbation analysis of discrete event dynamical systems. IEEE Trans. Automatic Control 32(10):858-866.Crossref, Google Scholar · Zbl 0634.93076 · doi:10.1109/TAC.1987.1104464
[22] Gu C, Qiu C (1993) Smoothing spline density estimation: Theory. Ann. Statist. 21(1):217-234.Crossref, Google Scholar · Zbl 0770.62030 · doi:10.1214/aos/1176349023
[23] He Z, Wang X (2015) On the convergence rate of randomized quasi-Monte Carlo for discontinuous functions. SIAM J. Numerical Anal. 53(5):2488-2503.Crossref, Google Scholar · Zbl 1325.65012 · doi:10.1137/15M1007963
[24] Heidergott B, Leahu H, Volk-Makarewicz WM (2015) A smoothed perturbation analysis of parisian options. IEEE Trans. Automatic Control 60(2):469-474.Crossref, Google Scholar · Zbl 1360.91140 · doi:10.1109/TAC.2014.2326717
[25] Hickernell FJ (2002) Obtaining O(N−2+ϵ) convergence for lattice quadrature rules. Fang KT, Hickernell FJ, Niederreiter H, eds. Monte Carlo and Quasi-Monte Carlo Methods 2000 (Springer-Verlag, Berlin), 274-289.Crossref, Google Scholar · Zbl 1002.65009 · doi:10.1007/978-3-642-56046-0_18
[26] Laub PJ, Salomone R, Botev ZI (2019) Monte Carlo estimation of the density of the sum of dependent random variables. Math. Comput. Simulation 161:23-31.Crossref, Google Scholar · Zbl 07316673 · doi:10.1016/j.matcom.2018.12.001
[27] Law AM (2014) Simulation Modeling and Analysis, 5th ed. (McGraw-Hill, New York).Google Scholar
[28] L’Ecuyer P (1990) A unified view of the IPA, SF, and LR gradient estimation techniques. Management Sci. 36(11):1364-1383.Link, Google Scholar · Zbl 0731.65130
[29] L’Ecuyer P (2009) Quasi-Monte Carlo methods with applications in finance. Finance Stochastics 13(3):307-349.Crossref, Google Scholar · Zbl 1199.65004 · doi:10.1007/s00780-009-0095-y
[30] L’Ecuyer P (2016) SSJ: Stochastic simulation in Java. Accessed August 9, 2021, http://simul.iro.umontreal.ca/ssj/.Google Scholar
[31] L’Ecuyer P (2018) Randomized quasi-Monte Carlo: An introduction for practitioners. Glynn PW, Owen AB, eds. Monte Carlo and Quasi-Monte Carlo Methods: MCQMC 2016 (Springer, Berlin), 29-52.Crossref, Google Scholar · Zbl 1407.65013 · doi:10.1007/978-3-319-91436-7_2
[32] L’Ecuyer P, Buist E (2008) On the interaction between stratification and control variates, with illustrations in a call center simulation. J. Simulation 2(1):29-40.Crossref, Google Scholar · doi:10.1057/palgrave.jos.4250035
[33] L’Ecuyer P, Lemieux C (2000) Variance reduction via lattice rules. Management Sci. 46(9):1214-1235.Link, Google Scholar · Zbl 1232.65008
[34] L’Ecuyer P, Lemieux C (2002) Recent advances in randomized quasi-Monte Carlo methods. Dror M, L’Ecuyer P, Szidarovszky F, eds. Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications (Kluwer Academic, Boston), 419-474.Crossref, Google Scholar · doi:10.1007/0-306-48102-2_20
[35] L’Ecuyer P, Munger D (2012) On figures of merit for randomly-shifted lattice rules. Woźniakowski H, Plaskota L, eds. Monte Carlo and Quasi-Monte Carlo Methods 2010 (Springer-Verlag, Berlin), 133-159.Crossref, Google Scholar · Zbl 1271.65045 · doi:10.1007/978-3-642-27440-4_6
[36] L’Ecuyer P, Munger D (2016) Algorithm 958: Lattice builder: A general software tool for constructing rank-1 lattice rules. ACM Trans. Math. Software 42(2):1-30.Crossref, Google Scholar · doi:10.1145/2754929
[37] L’Ecuyer P, Perron G (1994) On the convergence rates of IPA and FDC derivative estimators. Oper. Res. 42(4):643-656.Link, Google Scholar · Zbl 0863.65096
[38] L’Ecuyer P, Parent-Chartier JS, Dion M (2008) Simulation of a Lévy process by PCA sampling to reduce the effective dimension. Mason SJ, Hill RR, Mönch L, Rose O, Jefferson T, Fowler JW, eds. Proc. 2008 Winter Simulation Conf. (IEEE Press, Piscataway, NJ), 436-443.Google Scholar
[39] L’Ecuyer P, Marion P, Godin M, Fuchhammer F (2022) A tool for custom construction of QMC and RQMC point sets. Keller A, eds. Monte Carlo and Quasi-Monte Carlo Methods: MCQMC 2020 (Springer, Berlin). https://arxiv.org/abs/2012.10263.Google Scholar
[40] Lei L, Peng Y, Fu MC, Hu JQ (2018) Applications of generalized likelihood ratio method to distribution sensitivities and steady-state simulation. Discrete Event Dynamic Systems 28(1):109-125.Crossref, Google Scholar · Zbl 1384.93145 · doi:10.1007/s10626-017-0247-8
[41] Lemieux C (2009) Monte Carlo and Quasi-Monte Carlo Sampling (Springer-Verlag, New York).Google Scholar · Zbl 1269.65001
[42] Nakayama MK (2014a) Confidence intervals for quantiles using sectioning when applying variance-reduction techniques. ACM Trans. Model. Comput. Simulation 24(4).Crossref, Google Scholar · Zbl 1322.68251 · doi:10.1145/2558328
[43] Nakayama MK (2014b) Quantile estimation when applying conditional Monte Carlo. 2014 Internat. Conf. Simulation Model. Methodologies Tech. Appl. (IEEE), 280-285.Google Scholar
[44] Nelson BL (2008) The MORE plot: Displaying measures of risk and error from simulation output. Mason SJ, Hill RR, Mönch L, Rose O, Jefferson T, Fowler JW, eds. Proc. 2008 Winter Simulation Conf. (IEEE Press, Piscataway, NJ), 413-416.Google Scholar
[45] Niederreiter H (1992) Random Number Generation and Quasi-Monte Carlo Methods. SIAM CBMS-NSF Regional Conference Series Applied Mathematics, vol. 63 (SIAM).Google Scholar · Zbl 0761.65002
[46] Owen AB (2003) Variance with alternative scramblings of digital nets. ACM Trans. Model. Comput. Simulation 13(4):363-378.Crossref, Google Scholar · Zbl 1390.65037 · doi:10.1145/945511.945518
[47] Parzen E (1962) On estimation of a probability density function and mode. Ann. Math. Statist. 33(3):1065-1076.Crossref, Google Scholar · Zbl 0116.11302 · doi:10.1214/aoms/1177704472
[48] Peng Y, Fu MC, Heidergott B, Lam H (2020) Maximum likelihood estimation by Monte Carlo simulation: Toward data-driven stochastic modeling. Oper. Res. 68(6):1896-1912.Link, Google Scholar · Zbl 1460.62035
[49] Peng Y, Fu MC, Hu JQ, Heidergott B (2018) A new unbiased stochastic derivative estimator for discontinuous sample performances with structural parameters. Oper. Res. 66(2):487-499.Link, Google Scholar · Zbl 1458.62070
[50] Scott DW (2015) Multivariate Density Estimation, 2nd ed. (Wiley, Hoboken, NJ).Crossref, Google Scholar · Zbl 1311.62004 · doi:10.1002/9781118575574
[51] Serfling RJ (1980) Approximation Theorems for Mathematical Statistics (Wiley, New York).Crossref, Google Scholar · Zbl 0538.62002 · doi:10.1002/9780470316481
[52] Silverman B (1986) Density Estimation for Statistics and Data Analysis (Chapman and Hall, London).Crossref, Google Scholar · Zbl 0617.62042 · doi:10.1007/978-1-4899-3324-9
[53] Smith JS, Nelson BL (2015) Estimating and interpreting the waiting time for customers arriving to non-stationary queueing system. Yilmaz L, Chan WKV, Moon I, Roeder TMK, Macal C, Rossetti MD, eds. Proc. 2015 Winter Simulation Conf. (IEEE Press, Piscataway, NJ), 2610-2621.Google Scholar
[54] Sturrock DT, Pegden CD (2010) Recents innovations in Simio. Johansson B, Jain S, Montoya-Torres J, Hugan J, Yücesan E, eds. Proc. 2010 Winter Simulation Conf. (IEEE Press, Piscataway, NJ), 21-31.Google Scholar
[55] Thiongane M, Chan W, L’Ecuyer P (2021) Learning-based prediction of conditional waiting time distributions in multiskill call centers. Operations Research and Entreprise Systems, Expanded Selected Papers from ICORES 2020 (Springer).Google Scholar
[56] Van der Vaart AW (2000) Asymptotic Statistics (Cambridge University Press, New York).Google Scholar · Zbl 0943.62002
[57] Wand MP, Jones MC (1995) Kernel Smoothing (Chapman and Hall, Boca Raton, FL).Crossref, Google Scholar · Zbl 0854.62043 · doi:10.1007/978-1-4899-4493-1
[58] Yu J, Shi J, Liu A, Wang Y (2020) Smoothing spline semiparametric density models. J. Amer. Statist. Assoc. http://dx.doi.org/10.1080/01621459.2020.1769636.Google Scholar
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.