2001-02.wh-der
#
Fast Generation of Order Statistics

### Abstract

Generating a single order statistic without generating the full sample
can be an important task for simulations. If the density and the CDF
of the distribution are given it is no problem to compute the density
of the order statistic. In the main theorem it is shown that
the concavity properties of that density
depend directly on the distribution itself. Especially for log-concave
distributions all order statistics have log-concave
distributions themselves. So recently
suggested automatic transformed density rejection algorithms can be used
to generate single order statistics. This idea leads to
very fast generators. For example for the normal
and gamma distribution the suggested new algorithms are between 10
and 60 times faster than the algorithms suggested in the literature.

**Mathematics Subject Classification:**
65C10 (Random Number Generation)

**CR Categories and Subject Descriptors:**
G.3 [Probability and Statistics]: Random number generation

**General Terms:**
Algorithms

**Key Words:**
random variate generation, rejection method, transformed density rejection,
order statistics,
universal generator, T-concave

Download Preprint

© ACM, (2002). This is the author's version of the work.
It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in
Trans. Model. Comput. Simul. 12(2), 83-93
http://doi.acm.org/10.1145/566392.566393

Paper

Wolfgang.Hoermann@statistik.wu-wien.ac.at