COMPUTING METHODS

By U. BEENY

CONTENTS INTRODUCTION THE MONTE CARLO METHOD: A BRIEF HISTORY THE NEED FOR MONTE CARLO NUMERICAL INTEGRATION IMPORTANCE SAMPLING QUASI-MONTE CARLO INVERSE MONTE CARLO RANDOM NUMBER GENERATION RANDOM, PSEUDO-RANDOM, QUASI-RANDOM PSEUDO-RANDOM NUMBER GENERATORS NONLINEAR RECURSIONS CHAOTIC PSEUDO-RANDOM NUMBER GENERATORS THE MIDDLE-SQUARE GENERATOR LINEAR CONGRUENTIAL GENERATORS RANDOM SAMPLING METHODS DIRECT METHODS ACCEPT/REJECT METHODS MARKOV CHAIN MONTE CARLO (MCMC) HYBRID TECHNIQUES GOAL AND ORGANIZATION OF THIS BOOK MOTIVATION AND GOALS ORGANIZATION OF THE BOOK REFERENCES NOTATION VECTORS, POINTS, AND INTERVALS RANDOM VARIABLES, DISTRIBUTIONS, AND DENSITIES SETS TRANSFORMATIONS OF RANDOM VARIABLES ONE-TO-ONE TRANSFORMATIONS MANY-TO-ONE TRANSFORMATIONS DECONVOLUTION METHOD DISCRETE MIXTURES CONTINUOUS MIXTURES: MARGINALIZATION ORDER STATISTICS UNIVERSAL DIRECT METHODS INVERSION METHOD VERTICAL DENSITY REPRESENTATION (VDR) THE FUNDAMENTAL THEOREM OF SIMULATION INVERSE-OF-DENSITY METHOD TAILORED TECHNIQUES RECURSIVE METHODS CONVEX DENSITIES EXAMPLES MULTIPLICATION OF INDEPENDENT UNIFORM RANDOM VARIATES SUM OF INDEPENDENT UNIFORM RANDOM VARIATES POLYNOMIAL DENSITIES WITH NON-NEGATIVE COEF?CIENTS POLYNOMIAL DENSITIES WITH ONE OR MORE NEGATIVE CONSTANTS SUMMARY ACCEPT–REJECT METHODS REJECTION SAMPLING ACCEPTANCE RATE DISTRIBUTION OF THE REJECTED SAMPLES DISTRIBUTION OF THE ACCEPTED AND REJECTED SAMPLES WITH GENERIC L > 0 DIFFERENT APPLICATION SCENARIOS BUTCHER’S VERSION OF THE REJECTION SAMPLER VADUVA’S MODI?CATION OF THE BUTCHER’S METHOD LUX’S EXTENSION COMPUTATIONAL COST FURTHER CONSIDERATIONS ABOUT THE ACCEPTANCE RATE SQUEEZING SIBUYA’S MODI?ED REJECTION METHOD BAND REJECTION METHOD PRELIMINARIES GENERALIZED BAND REJECTION ALGORITHM PAYNE-DAGPUNAR’S BAND REJECTION ACCEPTANCE-COMPLEMENT METHOD RS WITH STEPWISE PROPOSALS STRIP METHODS INVERSION-REJECTION METHOD TRANSFORMED REJECTION METHOD TRANSFORMED REJECTION AND IOD METHOD RS FOR GENERATING ORDER STATISTICS MIXTURES WITH NEGATIVE COEF?CIENTS PDFS EXPRESSED AS SEQUENCES OF FUNCTIONS MONTE CARLO ESTIMATION VIA RS RECYCLING REJECTED SAMPLES RS WITH A GENERIC CONSTANT L > 0 ADAPTIVE REJECTION SAMPLING METHODS GENERIC STRUCTURE OF AN ADAPTIVE REJECTION SAMPLER PROPOSAL DENSITIES GENERIC ADAPTIVE ALGORITHM CONSTRUCTIONS OF THE PROPOSAL DENSITIES STANDARD ADAPTIVE REJECTION SAMPLING DERIVATIVE-FREE CONSTRUCTIONS FOR LOG-CONCAVE PDFS CONCAVE-CONVEX ARS TRANSFORMED DENSITY REJECTION EXTENSIONS OF TDR GENERALIZED ADAPTIVE REJECTION SAMPLING PERFORMANCE AND COMPUTATIONAL COST OF THE ARS SCHEMES PROBABILITY OF ADDING A NEW SUPPORT POINT VARIANTS OF THE ADAPTIVE STRUCTURE IN THE ARS SCHEME DETERMINISTIC TEST FOR ADDING NEW SUPPORT POINTS AN ADAPTIVE REJECTION SAMPLER WITH FIXED NUMBER OF SUPPORT POINTS COMBINING ARS AND MCMC ADAPTIVE REJECTION METROPOLIS SAMPLING A PROCEDURE TO BUILD PROPOSAL PDFS FOR THE ARMS ALGORITHM RATIO OF UNIFORMS A REMARK ON INVERSE DENSITIES STANDARD RATIO OF UNIFORMS METHOD SOME BASIC CONSIDERATIONS ENVELOPE POLYGONS AND ADAPTIVE ROU GENERALIZED RATIO OF UNIFORMS METHOD PROPERTIES OF GENERALIZED ROU SAMPLERS BOUNDARY OF AG HOW TO GUARANTEE THAT AG IS BOUNDED POWER FUNCTIONS CONNECTIONS BETWEEN GROU AND OTHER CLASSICAL TECHNIQUES EXTENDED INVERSE-OF-DENSITY METHOD GROU SAMPLING AND THE TRANSFORMED REJECTION METHOD ROLE OF THE CONSTANT CA HOW DOES GROU WORK FOR GENERIC PDFS? IOD FOR ARBITRARY PDFS GROU FOR PDFS WITH A SINGLE MODE AT X D 0 GROU FOR PDFS WITH A SINGLE MODE AT X ¤ 0 GROU FOR ARBITRARY PDFS RECTANGULAR REGION AG YET ANOTHER CONNECTION BETWEEN IOD AND GROU RELAXING ASSUMPTIONS: GROU WITH DECREASING G U/ GENERAL EXPRESSION OF A R V TRANSFORMATION ANOTHER VIEW OF GROU INDEPENDENT SAMPLING FOR MULTIVARIATE DENSITIES GENERIC PROCEDURES CHAIN RULE DECOMPOSITION DEPENDENCE GENERATION ROU FOR MULTIVARIATE DENSITIES ELLIPTICALLY CONTOURED DISTRIBUTIONS POLAR METHODS VERTICAL DENSITY REPRESENTATION UNIFORM DISTRIBUTIONS IN DIMENSION N POINTS UNIFORMLY DISTRIBUTED IN A SIMPLEX SAMPLING UNIFORMLY WITHIN A HYPERSPHERE POINTS UNIFORMLY DISTRIBUTED WITHIN A HYPERELLIPSOID TRANSFORMATIONS OF A RANDOM VARIABLE MANY-TO-FEW TRANSFORMATIONS (M > N) FEW-TO-MANY TRANSFORMATIONS: SINGULAR DISTRIBUTIONS (M < N) SAMPLING A UNIFORM DISTRIBUTION ON A DIFFERENTIABLE MANIFOLD SAMPLING TECHNIQUES FOR SPECI?C DISTRIBUTIONS MULTIVARIATE GAUSSIAN DISTRIBUTION MULTIVARIATE STUDENT’S T-DISTRIBUTION WISHART DISTRIBUTION INVERSE WISHART DISTRIBUTION MULTIVARIATE GAMMA SAMPLES DIRICHLET DISTRIBUTION COOK-JOHNSON’S FAMILY SOME RELEVANT BIVARIATE DISTRIBUTIONS GENERATION OF STOCHASTIC PROCESSES MARKOV JUMP PROCESSES GAUSSIAN PROCESSES WIENER PROCESSES BROWNIAN MOTION POISSON PROCESSES DIRICHLET PROCESSES: “RICH GET RICHER” ASYMPTOTICALLY INDEPENDENT SAMPLERS METROPOLIS-HASTINGS (MH) METHODS THE ALGORITHM INVARIANT DISTRIBUTION OF THE MH ALGORITHM ACCEPTANCE RATE IN MH-TYPE METHODS INDEPENDENT GENERALIZED MH METHODS WITH MULTIPLE CANDIDATES INDEPENDENT MULTIPLE TRY METROPOLIS ALGORITHMS ENSEMBLE MCMC METHOD INDEPENDENT DOUBLY ADAPTIVE REJECTION METROPOLIS SAMPLING ADAPTIVE REJECTION SAMPLING (ARS) STRUCTURAL LIMITATIONS OF ARMS IA2RMS ALGORITHM CONVERGENCE OF THE CHAIN AND COMPUTATIONAL COST EXAMPLES OF PROPOSAL CONSTRUCTIONS FOR IA2RMS SUMMARY AND OUTLOOK CHAPTER THE MONTE CARLO METHOD: A BRIEF HISTORY SEVERAL TECHNIQUES TO PERFORM RANDOM EXPERIMENTS HAVE BEEN USED SINCE, AT LEAST, THE BEGINNING OF THE NINETEENTH CENTURY FOR EXAMPLE, GEORGES-LOUIS LECLERC (COMTE DE BUFFON) FORMULATED (AND SOLVED) IN 1777 WHAT HAS COME TO BE KNOWN AS BUFFON’S NEEDLE PROBLEM, THE EARLIEST PROBLEM IN GEOMETRIC PROBABILITY [73] HE FOUND 1THIS SENTENCE SIMPLY MEANS THAT THERE ARE NO TRUE RANDOM “NUMBERS,” JUST MEANS TO PRODUCE THEM, AND THAT “A STRICT ARITHMETIC PROCEDURE IS NOT SUCH A METHOD” [34]