|
Short universal generators via generalized ratio-of-uniforms method
Author(s):
Josef
Leydold.
Journal:
Math. Comp.
72
(2003),
1453-1471.
MSC (2000):
Primary 65C10;
Secondary 65U05
Posted:
March 26, 2003
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
We use inequalities to design short universal algorithms that can be used to generate random variates from large classes of univariate continuous or discrete distributions (including all log-concave distributions). The expected time is uniformly bounded over all these distributions for a particular generator. The algorithms can be implemented in a few lines of high level language code.
References:
-
- 1.
- Ahrens, J. H. (1993).
Sampling from general distributions by suboptimal division of domains.
Grazer Math. Berichte 319, 20 pp. - 2.
- Ahrens, J. H. (1995).
A one-table method for sampling from continuous and discrete distributions.
Computing 54(2), 127-146. MR 96a:65011 - 3.
- Derflinger, G. (2000).
private communication. - 4.
- Derflinger, G., W. Hörmann, and J. Leydold (2002).
Universal methods of nonuniform random variate generation.
in preparation. - 5.
- Devroye, L. (1984a).
On the use of probability inequalities in random variate generation.
J. Stat. Comput. Simulation 20, 91-100. MR 87g:65009 - 6.
- Devroye, L. (1984b).
A simple algorithm for generating random variates with a log-concave density.
Computing 33(3-4), 247-257. MR 86d:65019 - 7.
- Devroye, L. (1986).
NonUniform Random Variate Generation.
New-York: Springer-Verlag. MR 87i:65012 - 8.
- Devroye, L. (1987).
A simple generator for discrete log-concave distributions.
Computing 39, 87-91. MR 89f:65007 - 9.
- Dieter, U. (1989).
Mathematical aspects of various methods for sampling from classical distributions.
In E. A. Mc Nair, K. J. Musselman, and P. Heidelberger (Eds.), Proc. 1989 Winter Simulation Conf., pp. 477-483. - 10.
- 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. - 11.
- Gilks, W. R. and P. Wild (1992).
Adaptive rejection sampling for Gibbs sampling.
Applied Statistics 41(2), 337-348. - 12.
- Gradshteyn, I. S. and I. M. Ryzhnik (1994).
Table of Integrals, Series, and Products (5th ed.).
Academic Press. MR 94g:00008 - 13.
- Hörmann, W. (1995).
A rejection technique for sampling from T-concave distributions.
ACM Trans. Math. Software 21(2), 182-193. MR 96b:65018 - 14.
- Hörmann, W. and G. Derflinger (1996).
Rejection-inversion to generate variates from monotone discrete distributions.
ACM TOMACS 6(3), 169-184. - 15.
- Hörmann, W. and G. Derflinger (1997).
An automatic generator for a large class of unimodal discrete distributions.
In A. R. Kaylan and A. Lehmann (Eds.), ESM 97, pp. 139-144. - 16.
- Kinderman, A. J. and F. J. Monahan (1977).
Computer generation of random variables using the ratio of uniform deviates.
ACM Trans. Math. Software 3(3), 257-260. - 17.
- Leydold, J. (2000a).
Automatic sampling with the ratio-of-uniforms method.
ACM Trans. Math. Software 26(1), 78-98. - 18.
- Leydold, J. (2000b).
A note on transformed density rejection.
Computing 65(2), 187-192. MR 2002e:65016 - 19.
- Leydold, J. (2001).
A simple universal generator for continuous and discrete univariate T-concave distributions.
ACM Trans. Math. Software 27(1), 66-82. - 20.
- Stadlober, E. (1989).
Sampling from Poisson, binomial and hypergeometric distributions: Ratio of uniforms as a simple and fast alternative.
Number 303 in Bericht der Mathematisch-Statistischen Sektion in der Forschungsgesellschaft Joanneum-Graz. MR 91b:65008 - 21.
- Wakefield, J. C., A. E. Gelfand, and A. F. M. Smith (1991).
Efficient generation of random variates via the ratio-of-uniforms method.
Statist. Comput. 1(2), 129-133.
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(2000):
65C10,
65U05
Retrieve articles in all Journals with MSC
(2000):
65C10,
65U05
Additional Information:
Josef
Leydold
Affiliation:
University of Economics and Business Administration, Department for Applied Statistics and Data Processing, Augasse 2-6, A-1090 Vienna, Austria
Email:
Josef.Leydold@statistik.wu-wien.ac.at
DOI:
10.1090/S0025-5718-03-01511-4
PII:
S 0025-5718(03)01511-4
Keywords:
Nonuniform random variates,
universal method,
ratio-of-uniforms method,
transformed density rejection,
discrete distributions,
continuous distributions,
log-concave distributions,
$T$-concave distributions
Received by editor(s):
August 8, 2000
Posted:
March 26, 2003
Additional Notes:
This work was supported by the Austrian Science Foundation (FWF), project no. P12805-MAT
Copyright of article:
Copyright
2003,
American Mathematical Society
|
Comments: webmaster@ams.org