×

Non-uniform random variate generation. (English) Zbl 0593.65005

New York etc.: Springer-Verlag. XVI, 843 p. DM 164.00 (1986).
This book deals with generation of non-uniform random variates which are needed in several fields of statistics, operations research and computer science. Following Chapter I (26 pages), where an outline of the book and several probability distributions are presented, Chapter II (56 pages) and Chapter III (35 pages) explain the fundamental principles in non- uniform random number generations such as principles of inversion, rejection and composition in all their generality. Less universal methods for random number generation including historically important methods and series methods are presented in Chapter IV (88 pages). These principles are applied to generate random variates with specific univariate distributions in the following chapters. In Chapter VII (72 pages), the fundamental principles are used to develop universal methods called black-box methods which are applicable to generate random variates according to a large family of distributions with a common property, e.g., log-concavity. Chapter IX (106 pages) discusses methods for normal, exponential, gamma, beta, t and other continuous distributions, and Chapter X (69 pages) for geometric, Poisson, binomial, logarithmic series and other discrete distributions. Chapter VIII (21 pages) explains the table methods (strip methods and grid methods), with which random number generation can be sped up. The generation problem for multi-dimensional random variates is discussed in Chapter XI (57 pages). Following several general principles including conditional distribution method, specific subclasses of distributions are dealt with.
The remaining chapters are concerned with some specialized topics. Chapter V (40 pages) emphasizes the usefulness of the idea of order statistics; normal, exponential, beta, gamma and t distributed random variates can be obtained by suitable manipulations of the order statistics or spacing defined by samples of uniform random variates. The problem of computer generation of random variables with a given hazard rate is considered in Chapter VI (40 pages). Following random sampling problem in Chapter XII (31 pages), general strategies for generating random combinatorial objects including random graphs, random trees, random partitions and random permutations are presented in Chapter XIII (32 pages). Chapter XIV (94 pages) explains probabilistic shortcuts in random variate generation for reducing the expected time in simulation, design of efficient methods for large simulation and generation methods of random numbers with incomplete or indirectly specified information of distributions. Finally, the idea of random bit model for generation of discrete variables due to D. E. Knuth and A. C. Yao [Algorithms and Complexity, Proc. Symp., Pittsburgh 1976, 357-428 (1976; Zbl 0395.65004)] is presented in Chapter XV (16 pages). Extensive list of references including approximately 500 references concludes this book.
Each chapter usually begins with the general scope of the chapter followed by theoretical basis of the generators, and ends with the algorithms. Well-organized and clear descriptions and ample exercises may make it easy to understand the idea on which the generation methods are based. To keep everything abstract, as the author stressed, this book does not contain any computer programs and timing comparison of algorithms. So, in practice, users should carefully choose the algorithm suitable for own use. In summary, this book gives a very completely account of the state of art in non-uniform random number generation and will be useful as a text or a reference concerning with non-uniform random number generation, though it is a little theoretical and abstract in character and selection of chapters is essential depending on the needs of the audience.
Reviewer: K.Uosaki

MSC:

65C10 Random number generation in numerical analysis
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
65C99 Probabilistic methods, stochastic differential equations
62H12 Estimation in multivariate analysis
62G05 Nonparametric estimation
68U99 Computing methodologies and applications
91B99 Mathematical economics
90B99 Operations research and management science

Citations:

Zbl 0395.65004