Abstract
We consider the problem of generating random variates with a monotone nonincreasing density on [0, ∞). No bounds are known that would allow a straightforward application of the rejection method, and the inverse of the distribution function is not explictly known either. We develop the inversion/rejection method, and show how it can be used for all monotone densities, even those with an infinite peak at 0 and unbounded support, provided only that the densityf and the distribution functionF can be computed for eachx. A theoretical analysis of the average time behaviaour of the algorithm is included.
Zusammenfassung
Wir betrachten das Problem der Erzeugung von Zufallsvariablen mit monoton nichtsteigender Dichtefunktion im Intervall [0,∞). Schranken, die eine direkte Anwendung der Zurückweisungsmethode erlauben würden sowie die Umkehrfuntkion der Verteilung sind nicht bekannt. Wir entwicklen die Umkehr/Zurückweisungsmethode und zeigen ihre Anwendbarkeit auf alle monotonen Dichten, sogar auf solche, die eine Polstelle bei 0 besitzen und die einen unbeschränkten Werteberich haben. Vorausgesetzt ist lediglich, daßf undF an jeder Stelle berechenbar sind. Eine theoretische Analyse des mittleren Zeitverhaltens der Algorithmen ist beigefügt.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Ahrens, J. H., Kohrt, K. D.: Computer methods for efficient sampling from largely arbitrary statistical distributions. Computing26, 19–31 (1981).
Barlow, R. E., Marshall, A. W.., Proschan, F.: Properties of probability distribution with monotone hazard rate. Annals of Mathematical Statistics34, 375–389 (1963).
Chen, H. C., Asau, Y.: On generating random variates from an empirical distribution. AIIE Transactions6, 163–166 (1974).
Devroye, L.: Random variate generation for unimodal and monotone densities. Technical Report, School of Computer Science, McGill University, Montreal, Canada H3A 2K6, 1982.
Feller, W.: An Introduction to probability Theory and Its Applications, Vol. 1. New York: J. Wiely 1961.
Feller, W.: An Introduction to Probability Theory and Its Application, vol. 2, 2nd ed. New York: J. Wiley 1971.
Hardy, G. H., Littlewood, J. E., Polya, G.: Inequalities, 2nd ed. London: Cambridge University Press 1952.
Kohrt, K. D.: Efficient sampling from non-uniform statistical distributions. Diploma Thesis, University of Kiel, Federal Republic of Germany, 1980.
Kronmal, R. A., Peterson, A. V.: On the alias methe for generating random variables from a discrete distribution. The American Statistician33, 214–218 (1979a).
Kornmal, R. A., Peterson, A. V.: Programs for generating discrete random integers using Walker's alias method. Manuscript, Department of Biostatistics, University of Washington, Seattle, Washington, 1979b.
Marsaglia, G.: The squeeze method for generating gamma variaties. Computer and Mathematics with Applications3, 321–325 (1977).
Schmeiser, B. W.: Random variage generation: a survey. Proceedings of the 1980 Winter Simulation Conferece, Orlando, Florida, 1980.
Steffensen, J. F.: On certain inequalities between mean values and their application to actuarial problems. Skand. Aktuarittidskrift1, 82–97 1918).
Steffensen, J. F.: On a generalization of certain inequalities of Tchebychef and Jensen. Skand. Aktuarietidskrift8, 137–147 (1925).
Walker, A. J.: An efficient method for generating discrete random variables with general distributions. ACM Transactions on Mathematical Software3, 253–256 (1977).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Devroye, L. Random variate generation for unimodal and monotone densities. Computing 32, 43–68 (1984). https://doi.org/10.1007/BF02243018
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02243018