Random-number and random-variate generation: automatic random variate generation for simulation input

ABSTRACT

We develop and evaluate algorithms for generating random variates for simulation input. One group called automatic, or black-box algorithms can be used to sample from distributions with known density. They are based on the rejection principle. The hat function is generated automatically in a setup step using the idea of transformed density rejection. There the density is transformed into a concave function and the minimum of several tangents is used to construct the hat function. The resulting algorithms are not too complicated and are quite fast. The principle is also applicable to random vectors. A second group of algorithms is presented that generate random variates directly from a given sample by implicitly estimating the unknown distribution. The best of these algorithms are based on the idea of naive resampling plus added noise. These algorithms can be interpreted as sampling from the kernel density estimates. This method can be also applied to random vectors. There it can be interpreted as a mixture of naive resampling and sampling from the multi-normal distribution that has the same co-variance matrix as the data. The algorithms described in this paper have been implemented in ANSI C in a library called UNURAN which is available via anonymous ftp.

REFERENCES

• 1: Ahrens, J., H. 1995. A one-table method for sampling from continuous and discrete distributions. Computing, 54(2):127-146.
• 2: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 3: Dagpunar, J. 1988. Principles of Random Variate Generation. Oxford, U.K.: Clarendon Oxford Science Publications.
• 4: Derflinger, G. and W. Hörmann. 1998. The optimal selection of hat functions for rejection algorithms. Unpublished manuscript.
• 5: Devroye, L. 1986. Non-Uniform Random Variate Generation. New York: Springer-Verlag.
• 6: Devroye, L. 1997. Universal smoothing factor selection in density estimation, theory and practice. Test, 6:223-320.
• 7: Devroye, L. and L. Györfi. 1985. Nonparametric Density Estimation: The L1View. New-York: John Wiley.
• 8: Evans, M. and T. Swartz. 1998. Random variable generation using concavity properties of transformed densities. Journal of Computational and Graphical Statistics, 7(4):514-528.
• 9: Gentle, J. E. 1998. Random Number Generation and Monte Carlo Methods. Statistics and Computing. New York:Springer.
• 10: Gilks, W. R. and P. Wild. 1992. Adaptive rejection sampling for Gibbs sampling. Applied Statistics, 41:337-348.
• 11: Wolfgang Hörmann, A rejection technique for sampling from T-concave distributions, ACM Transactions on Mathematical Software (TOMS), v.21 n.2, p.182-193, June 1995 [doi>10.1145/203082.203089]
• 12: Hörmann, W. 2000. An automatic generator for bivariate log-concave distributions. ACM Transactions on Modeling and Computer Simulation, (to appear).
• 13: Hörmann, W. and O. Bayar. 2000. Modeling probability distributions from data and its influence on simulation. In Troch I. and Breitenecker F., editors, Proceedings IMACS Symposium on Mathematical Modeling, Argesim Report (15):429 - 435.
• 14: Hörmann, W. and G. Derflinger. 1994. Universal generators for correlation induction. In Compstat, Proceedings in Computational Statistics, ed. R. Dutter and W. Grossmann, 52-57. Physica-Verlag, Heidelberg.
• 15: Mark E Johnson, Multivariate statistical simulation, John Wiley & Sons, Inc., New York, NY, 1987
• 16: Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
• 17: Josef Leydold, A rejection technique for sampling from log-concave multivariate distributions, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.3, p.254-280, July 1998 [doi>10.1145/290274.290287]
• 18: Josef Leydold, Automatic sampling with the ratio-of-uniforms method, ACM Transactions on Mathematical Software (TOMS), v.26 n.1, p.78-98, March 2000 [doi>10.1145/347837.347863]
• 19: Josef Leydold , Wolfgang Hörmann, A sweep-plane algorithm for generating random tuples in simple polytopes, Mathematics of Computation, v.67 n.224, p.1617-1635, Oct. 1998 [doi>10.1090/S0025-5718-98-01004-7]
• 20: Leydold, J. and W. Hörmann. 2000. UNURAN - A library for Universal Non-Uniform Random number generators. Institut für Statistik, WU Wien, A-1090 Wien, Austria. Available on-line via ⟨ftp://statistik.wu-wien.ac.at/src/unuran/⟩.
• 21: Barry L. Nelson , Michael Yamnitsky, Input modeling tools for complex problems, Proceedings of the 30th conference on Winter simulation, p.105-112, December 13-16, 1998, Washington, D.C., United States
• 22: B. Schmeiser , V. Kachitvichyanukul, Noninverse correlation induction: guidelines for algorithm development, Journal of Computational and Applied Mathematics, v.31 n.1, p.173-180, July 1990 [doi>10.1016/0377-0427(90)90348-4]
• 23: Silverman, B. 1986. Density Estimation for Statistics and Data Analysis. London: Chapman and Hall.
• 24: M S Taylor , J R Thompson, A data based algorithm for the generation of random vectors, Computational Statistics & Data Analysis, v.4 n.2, p.93-101, July 1986 [doi>10.1016/0167-9473(86)90013-7]
• 25: Mary Ann Flanigan Wagner , James R. Wilson, Graphical interactive simulation input modeling with bivariate Bézier distributions, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.3, p.163-189, July 1995 [doi>10.1145/217853.217854]
• 26: Wagner, M. A. F. and J. R. Wilson. 1996. Using univariate Bezier distributions to model simulation input processes. IIE Transactions, 28:699-711.
• 27: Wand, M. and M. Jones. 1995. Kernel Smoothing. London: Chapman and Hall.