Random Number Generation and Monte Carlo Methods

by Gentle, James E.

• ISBN13: 9780387001784
• ISBN10: 0387001786
• Edition: 2nd
• Format: Hardcover
• Copyright: 2003-07-01
• Publisher: Springer Nature

Summary

Monte Carlo simulation has become one of the most important tools in all fields of science. Simulation methodology relies on a good source of numbers that appear to be random. These "pseudorandom" numbers must pass statistical tests just as random samples would. Methods for producing pseudorandom numbers and transforming those numbers to simulate samples from various distributions are among the most important topics in statistical computing.This book surveys techniques of random number generation and the use of random numbers in Monte Carlo simulation. The book covers basic principles, as well as newer methods such as parallel random number generation, nonlinear congruential generators, quasi Monte Carlo methods, and Markov chain Monte Carlo. The best methods for generating random variates from the standard distributions are presented, but also general techniques useful in more complicated models and in novel settings are described. The emphasis throughout the book is on practical methods that work well in current computing environments.The book includes exercises and can be used as a test or supplementary text for various courses in modern statistics. It could serve as the primary test for a specialized course in statistical computing, or as a supplementary text for a course in computational statistics and other areas of modern statistics that rely on simulation. The book, which covers recent developments in the field, could also serve as a useful reference for practitioners.Although some familiarity with probability and statistics is assumed, the book is accessible to a broad audience. The second edition is approximately 50% longer than the first edition. It includes advances in methods for parallel random number generation, universal methods for generation of nonuniform variates, perfect sampling, and software for random number generation. The material on testing of random number generators has been expanded to include a discussion of newer software for testing, as well as more discussion about the tests themselves. The second edition has more discussion of applications of Monte Carlo methods in various fields, including physics and computational finance.James Gentle is University Professor of Computational Statistics at George Mason University. During a thirteen-year hiatus from academic work before joining George Mason, he was director of research and design at the world's largest independent producer of Fortran and C general-purpose scientific software libraries. These libraries implement several random number generators, and are widely used in Monte Carlo studies.He is a Fellow of the American Statistical Association and a member of the International Statistical Institute. He has held several national offices in the American Statistical Association and has served as an associate editor for journals of the ASA as well as for other journals in statistics and computing. Recent activities include serving as program director of statistics at the National Science Foundation and as research fellow at the Bureau of Labor Statistics.

Author Biography

James E. Gentle is University Professor of Computational Statistics at George Mason University.

Table of Contents

Preface	vii
Simulating Random Numbers from a Uniform Distribution	1	(60)
Uniform Integers and an Approximate Uniform Density	5	(6)
Simple Linear Congruential Generators	11	(16)
Structure in the Generated Numbers	14	(6)
Tests of Simple Linear Congruential Generators	20	(1)
Shuffling the Output Stream	21	(2)
Generation of Substreams in Simple Linear Congruential Generators	23	(4)
Computer Implementation of Simple Linear Congruential Generators	27	(4)
Ensuring Exact Computations	28	(1)
Restriction that the Output Be in the Open Interval (0,1)	29	(1)
Efficiency Considerations	30	(1)
Vector Processors	30	(1)
Other Linear Congruential Generators	31	(5)
Multiple Recursive Generators	32	(2)
Matrix Congruential Generators	34	(1)
Add-with-Carry, Subtract-with-Borrow, and Multiply-with-Carry Generators	35	(1)
Nonlinear Congruential Generators	36	(2)
Inversive Congruential Generators	36	(1)
Other Nonlinear Congruential Generators	37	(1)
Feedback Shift Register Generators	38	(5)
Generalized Feedback Shift Registers and Variations	40	(3)
Skipping Ahead in GFSR Generators	43	(1)
Other Sources of Uniform Random Numbers	43	(3)
Generators Based on Cellular Automata	44	(1)
Generators Based on Chaotic Systems	45	(1)
Other Recursive Generators	45	(1)
Tables of Random Numbers	46	(1)
Combining Generators	46	(2)
Properties of Combined Generators	48	(3)
Independent Streams and Parallel Random Number Generation	51	(3)
Skipping Ahead with Combination Generators	52	(1)
Different Generators for Different Streams	52	(1)
Quality of Parallel Random Number Streams	53	(1)
Portability of Random Number Generators	54	(1)
Summary	55	(6)
Exercises	56	(5)
Quality of Random Number Generators	61	(32)
Properties of Random Numbers	62	(2)
Measures of Lack of Fit	64	(7)
Measures Based on the Lattice Structure	64	(3)
Differences in Frequencies and Probabilities	67	(3)
Independence	70	(1)
Empirical Assessments	71	(16)
Statistical Goodness-of-Fit Tests	71	(15)
Comparisons of Simulated Results with Statistical Models in Physics	86	(1)
Anecdotal Evidence	86	(1)
Tests of Random Number Generators Used in Parallel	87	(1)
Programming Issues	87	(1)
Summary	87	(6)
Exercises	88	(5)
Quasirandom Numbers	93	(8)
Low Discrepancy	93	(1)
Types of Sequences	94	(4)
Halton Sequences	94	(2)
Sobol' Sequences	96	(1)
Comparisons	97	(1)
Variations	97	(1)
Computations	98	(1)
Further Comments	98	(3)
Exercises	100	(1)
Transformations of Uniform Deviates: General Methods	101	(64)
Inverse CDF Method	102	(7)
Decompositions of Distributions	109	(2)
Transformations that Use More than One Uniform Deviate	111	(1)
Multivariate Uniform Distributions with Nonuniform Marginals	112	(1)
Acceptance/Rejection Methods	113	(12)
Mixtures and Acceptance Methods	125	(4)
Ratio-of-Uniforms Method	129	(4)
Alias Method	133	(3)
Use of the Characteristic Function	136	(1)
Use of Stationary Distributions of Markov Chains	137	(12)
Use of Conditional Distributions	149	(1)
Weighted Resampling	149	(1)
Methods for Distributions with Certain Special Properties	150	(5)
General Methods for Multivariate Distributions	155	(4)
Generating Samples from a Given Distribution	159	(6)
Exercises	159	(6)
Simulating Random Numbers from Specific Distributions	165	(52)
Modifications of Standard Distributions	167	(3)
Some Specific Univariate Distributions	170	(27)
Normal Distribution	171	(5)
Exponential, Double Exponential, and Exponential Power Distributions	176	(2)
Gamma Distribution	178	(5)
Beta Distribution	183	(1)
Chi-Squared, Student's t, and F Distributions	184	(2)
Weibull Distribution	186	(1)
Binomial Distribution	187	(1)
Poisson Distribution	188	(1)
Negative Binomial and Geometric Distributions	188	(1)
Hypergeometric Distribution	189	(1)
Logarithmic Distribution	190	(1)
Other Specific Univariate Distributions	191	(2)
General Families of Univariate Distributions	193	(4)
Some Specific Multivariate Distributions	197	(13)
Multivariate Normal Distribution	197	(1)
Multinomial Distribution	198	(1)
Correlation Matrices and Variance-Covariance Matrices	198	(3)
Points on a Sphere	201	(1)
Two-Way Tables	202	(1)
Other Specific Multivariate Distributions	203	(5)
Families of Multivariate Distributions	208	(2)
Data-Based Random Number Generation	210	(2)
Geometric Objects	212	(5)
Exercises	213	(4)
Generation of Random Samples, Permutations, and Stochastic Processes	217	(12)
Random Samples	217	(3)
Permutations	220	(1)
Limitations of Random Number Generators	220	(1)
Generation of Nonindependent Samples	221	(3)
Order Statistics	221	(2)
Censored Data	223	(1)
Generation of Nonindependent Sequences	224	(5)
Markov Process	224	(1)
Nonhomogeneous Poisson Process	225	(1)
Other Time Series Models	226	(1)
Exercises	227	(2)
Monte Carlo Methods	229	(54)
Evaluating an Integral	230	(3)
Sequential Monte Carlo Methods	233	(2)
Experimental Error in Monte Carlo Methods	235	(1)
Variance of Monte Carlo Estimators	236	(3)
Variance Reduction	239	(10)
Analytic Reduction	240	(1)
Stratified Sampling and Importance Sampling	241	(4)
Use of Covariates	245	(3)
Constrained Sampling	248	(1)
Stratification in Higher Dimensions: Latin Hypercube Sampling	248	(1)
The Distribution of a Simulated Statistic	249	(1)
Computational Statistics	250	(6)
Monte Carlo Methods for Inference	251	(1)
Bootstrap Methods	252	(3)
Evaluating a Posterior Distribution	255	(1)
Computer Experiments	256	(1)
Computational Physics	257	(4)
Computational Finance	261	(22)
Exercises	271	(12)
Software for Random Number Generation	283	(14)
The User Interface for Random Number Generators	285	(1)
Controlling the Seeds in Monte Carlo Studies	286	(1)
Random Number Generation in Programming Languages	286	(2)
Random Number Generation in IMSL Libraries	288	(3)
Random Number Generation in S-Plus and R	291	(6)
Exercises	295	(2)
Monte Carlo Studies in Statistics	297	(16)
Simulation as an Experiment	298	(2)
Reporting Simulation Experiments	300	(1)
An Example	301	(12)
Exercises	310	(3)
A Notation and Definitions	313	(10)
B Solutions and Hints for Selected Exercises	323	(8)
Bibliography	331	(40)
Literature in Computational Statistics	332	(2)
World Wide Web, News Groups, List Servers, and Bulletin Boards	334	(2)
References for Software Packages	336	(1)
References to the Literature	336	(35)
Author Index	371	(6)
Subject Index	377