Fast Generation of Deviates for Order Statistics by an Exact Method

Document Type : Research Paper


1 Sharif University of Technology, Iran

2 The University of Toronto, Ontario, Canada

3 University of Washington, Seatle, WA, USA


We propose an exact method for generating random deviates from continuous order statistics. This versatile method that generates Beta deviates as a middle step can be applied to any density function without resorting to numerical inversion. We also conduct an exhaustive investigation to document the merits of our method in generating deviates from any Beta distribution.


Main Subjects

[1] Ahrens J.H., Dieter U. (1974), Computer methods for sampling from gamma, beta, Poisson and
binomial distributions; Computing 12; 233-246.
[2] Ahrens J.H., Dieter U. (1974), Acceptance-rejection techniques for sampling from the gamma and beta
distributions; Technical Report 83; Stanford, California, Stanford University.
[3] Atkinson A.C., Whittaker J. (1976), A switching algorithm for the generation of beta random variables
with at Least One Parameter less than 1; Journal of The Royal Statistical Society 139; 431-467.
[4] Atkinson A.C. (1979), A family of switching algorithms for computer generation of beta random
variables; Biometrika 66; 141-145.
[5] Cheng R.C.H. (1978), Generating beta variates with nonintegral shape parameters; Comm. ACM 21;
[6] Devroye L. (1980), Generating the maximum of independent identically distributed random variables;
Comput. Math. Appl. 6; 305-315.
[7] Devroye L. (1986), Non-uniform random variate generation; Springer-Verlag.
[8] Hörmann W., Derflinger G. (2002), Fast generation of order statistics; ACM Transactions on Modeling
and Computer Simulation 12(2); 83-93.
[9] Hörmann W., Leydold J., Derflinger G. (2004), Automatic nonuniform random variate generation;
[10] Hörmann W., Leydold J. (2003), Continuous random variate generation by fast numerical inversion;
ACM Trans. Model. Comput. Simul. 13(4); 347-362.
[11] Johnk M.D. (1964), Erzeugung von betaverteilten und gammaverteilten zufallszahlen; Metrika 8; 5-15.
[12] Mahlooji H., Jahromi A. E., Mehrizi H. A., Izady N. (2008), Uniform fractional part: A simple fast
method for generating continuous random variates; Scientia Iranica 15(5); 613-622.
[13] Mahlooji H., Mehrizi H.A., Farzan A. (2005), A fast method for generating continuous order statistics
based on uniform fractional parts; 35th International Conference on Computers and Industrial
Engineering Turkey(Istanbul); 1355-1360.
[14] Sakasegawa H. (1983), Stratified rejection and squeeze method for generating beta random numbers;
Ann. Inst. Statist. Math. 35; 291-302.
[15] Schmeiser B.W., Babu A.J.G. (1980), Beta variate generation via exponential majorizing functions;
Oper. Research 28; 917-926.
[16] Zechner H., Stadlober E. (1992), Generating beta variates via patchwork rejection; Technical report;
Institute for Statistik, Techn. University Graz.