RANDOM NUMBER GENERATION AND MONTE CARLO METHODS

By EVELYN TAYLOR

CONTENTS SIMULATING RANDOM NUMBERS FROM A UNIFORM DISTRIBUTION UNIFORM INTEGERS AND AN APPROXIMATE UNIFORM DENSITY SIMPLE LINEAR CONGRUENTIAL GENERATORS STRUCTURE IN THE GENERATED NUMBERS TESTS OF SIMPLE LINEAR CONGRUENTIAL GENERATORS SHU?ING THE OUTPUT STREAM GENERATION OF SUBSTREAMS IN SIMPLE LINEAR CONGRUENTIAL GENERATORS COMPUTER IMPLEMENTATION OF SIMPLE LINEAR CONGRUENTIAL GENERATORS ENSURING EXACT COMPUTATIONS RESTRICTION THAT THE OUTPUT BE IN THE OPEN INTERVAL (0, 1) E?CIENCY CONSIDERATIONS VECTOR PROCESSORS OTHER LINEAR CONGRUENTIAL GENERATORS MULTIPLE RECURSIVE GENERATORS MATRIX CONGRUENTIAL GENERATORS ADD-WITH-CARRY, SUBTRACT-WITH-BORROW, AND MULTIPLY-WITH-CARRY GENERATORS NONLINEAR CONGRUENTIAL GENERATORS INVERSIVE CONGRUENTIAL GENERATORS OTHER NONLINEAR CONGRUENTIAL GENERATORS FEEDBACK SHIFT REGISTER GENERATORS GENERALIZED FEEDBACK SHIFT REGISTERS AND VARIATIONS SKIPPING AHEAD IN GFSR GENERATORS OTHER SOURCES OF UNIFORM RANDOM NUMBERS GENERATORS BASED ON CELLULAR AUTOMATA GENERATORS BASED ON CHAOTIC SYSTEMS OTHER RECURSIVE GENERATORS TABLES OF RANDOM NUMBERS COMBINING GENERATORS PROPERTIES OF COMBINED GENERATORS 1 10 INDEPENDENT STREAMS AND PARALLEL RANDOM NUMBER GENERATION 1 10 1 SKIPPING AHEAD WITH COMBINATION GENERATORS 1 10 2 DI?ERENT GENERATORS FOR DI?ERENT STREAMS 1 10 3 QUALITY OF PARALLEL RANDOM NUMBER STREAMS 1 11 PORTABILITY OF RANDOM NUMBER GENERATORS 1 12 SUMMARY EXERCISES QUALITY OF RANDOM NUMBER GENERATORS PROPERTIES OF RANDOM NUMBERS MEASURES OF LACK OF FIT MEASURES BASED ON THE LATTICE STRUCTURE DI?ERENCES IN FREQUENCIES AND PROBABILITIES INDEPENDENCE EMPIRICAL ASSESSMENTS STATISTICAL GOODNESS-OF-FIT TESTS COMPARISONS OF SIMULATED RESULTS WITH STATISTICAL MODELS IN PHYSICS ANECDOTAL EVIDENCE TESTS OF RANDOM NUMBER GENERATORS USED IN PARALLEL PROGRAMMING ISSUES SUMMARY QUASIRANDOM NUMBERS LOW DISCREPANCY TYPES OF SEQUENCES HALTON SEQUENCES SOBOL’ SEQUENCES COMPARISONS VARIATIONS COMPUTATIONS FURTHER COMMENTS TRANSFORMATIONS OF UNIFORM DEVIATES: GENERAL METHODS INVERSE CDF METHOD DECOMPOSITIONS OF DISTRIBUTIONS TRANSFORMATIONS THAT USE MORE THAN ONE UNIFORM DEVIATE MULTIVARIATE UNIFORM DISTRIBUTIONS WITH NONUNIFORM MARGINALS ACCEPTANCE/REJECTION METHODS MIXTURES AND ACCEPTANCE METHODS RATIO-OF-UNIFORMS METHOD ALIAS METHOD USE OF THE CHARACTERISTIC FUNCTION 4 10 USE OF STATIONARY DISTRIBUTIONS OF MARKOV CHAINS 4 11 USE OF CONDITIONAL DISTRIBUTIONS 4 12 WEIGHTED RESAMPLING 4 13 METHODS FOR DISTRIBUTIONS WITH CERTAIN SPECIAL PROPERTIES 4 14 GENERAL METHODS FOR MULTIVARIATE DISTRIBUTIONS 4 15 GENERATING SAMPLES FROM A GIVEN DISTRIBUTION SIMULATING RANDOM NUMBERS FROM SPECI?C DISTRIBUTIONS MODI?CATIONS OF STANDARD DISTRIBUTIONS SOME SPECI?C UNIVARIATE DISTRIBUTIONS NORMAL DISTRIBUTION EXPONENTIAL, DOUBLE EXPONENTIAL, AND EXPONENTIAL POWER DISTRIBUTIONS GAMMA DISTRIBUTION BETA DISTRIBUTION CHI-SQUARED, STUDENT’S T, AND F DISTRIBUTIONS WEIBULL DISTRIBUTION BINOMIAL DISTRIBUTION POISSON DISTRIBUTION NEGATIVE BINOMIAL AND GEOMETRIC DISTRIBUTIONS 5 2 10 HYPERGEOMETRIC DISTRIBUTION 5 2 11 LOGARITHMIC DISTRIBUTION 5 2 12 OTHER SPECI?C UNIVARIATE DISTRIBUTIONS 5 2 13 GENERAL FAMILIES OF UNIVARIATE DISTRIBUTIONS SOME SPECI?C MULTIVARIATE DISTRIBUTIONS MULTIVARIATE NORMAL DISTRIBUTION MULTINOMIAL DISTRIBUTION CORRELATION MATRICES AND VARIANCE-COVARIANCE MATRICES POINTS ON A SPHERE TWO-WAY TABLES OTHER SPECI?C MULTIVARIATE DISTRIBUTIONS FAMILIES OF MULTIVARIATE DISTRIBUTIONS DATA-BASED RANDOM NUMBER GENERATION GEOMETRIC OBJECTS GENERATION OF RANDOM SAMPLES, PERMUTATIONS, AND STOCHASTIC PROCESSES RANDOM SAMPLES PERMUTATIONS LIMITATIONS OF RANDOM NUMBER GENERATORS GENERATION OF NONINDEPENDENT SAMPLES ORDER STATISTICS CENSORED DATA GENERATION OF NONINDEPENDENT SEQUENCES MARKOV PROCESS NONHOMOGENEOUS POISSON PROCESS OTHER TIME SERIES MODELS MONTE CARLO METHODS EVALUATING AN INTEGRAL SEQUENTIAL MONTE CARLO METHODS EXPERIMENTAL ERROR IN MONTE CARLO METHODS VARIANCE OF MONTE CARLO ESTIMATORS VARIANCE REDUCTION ANALYTIC REDUCTION STRATI?ED SAMPLING AND IMPORTANCE SAMPLING USE OF COVARIATES CONSTRAINED SAMPLING STRATI?CATION IN HIGHER DIMENSIONS: LATIN HYPERCUBE SAMPLING THE DISTRIBUTION OF A SIMULATED STATISTIC COMPUTATIONAL STATISTICS MONTE CARLO METHODS FOR INFERENCE BOOTSTRAP METHODS EVALUATING A POSTERIOR DISTRIBUTION COMPUTER EXPERIMENTS COMPUTATIONAL PHYSICS 7 10 COMPUTATIONAL FINANCE SOFTWARE FOR RANDOM NUMBER GENERATION THE USER INTERFACE FOR RANDOM NUMBER GENERATORS CONTROLLING THE SEEDS IN MONTE CARLO STUDIES RANDOM NUMBER GENERATION IN PROGRAMMING LANGUAGES RANDOM NUMBER GENERATION IN IMSL LIBRARIES RANDOM NUMBER GENERATION IN S-PLUS AND R MONTE CARLO STUDIES IN STATISTICS SIMULATION AS AN EXPERIMENT REPORTING SIMULATION EXPERIMENTS AN EXAMPLE