Preface

Selected Notation

1 Introduction

1.1 About This Book

1.1.1 Controlling Error

1.1.2 Strategies For Reading This Book

1.1.3 Intended Audience

1.2 Available Software

1.2.1 Unix Machines

1.2.2 IBM Compatible Personal Computers

1.3 What This Book Does Not Contain

1.4 Conventions

References

2 Estimating Volume and Count

2.1 Volume

2.2 Error and Sample Size Considerations

2.3 Confidence Intervals

2.4 Exploiting Regional Bounds

2.4.1 Bounds on Volume

2.4.2 Worst-Case and Best-Case Sample Sizes

2.4.3 Worst-Case Normal Error

2.4.4 Hyperrectangular Bounds

2.4.5 Modifying the Sampling Distribution

2.5 Relative Error

2.5.1 Exponential Sample Size

2.6 Network Reliability

2.7 Multivariable Integration

2.7.1 Quadrature Formulas

2.7.2 Equidistributed Points

2.7.3 Monte Carlo Sampling

2.8 Exploiting Function Bounds

2.9 Exploiting Parameter Bounds

2.10 Restricting the Sampling Region

2.11 Reducing the Sampling Dimension

2.12 Counting Problems

2.13 Sensitivity Analysis

2.13.1 Worst-Case and Best-Case Sample Sizes for Absolute Error

2.13.1.a Worst Case

2.13.1.b Best Case

2.13.2 Example

2.13.3 Worst-Case and Best-Case Sample Sizes for Relative Error

2.13.4 Example

2.14 Simultaneous Confidence Intervals

2.15 Ratio Estimation

2.16 Sequential Estimation

2.16.1 Absolute Error

2.16.2 Relative Error

2.16.3 Mixed Error Criteria

Appendix

Exercises

References

3 Generating Samples

3.1 Independence and Dependence

3.2 Inverse Transform Method

3.2.1 Continuous Distributions

3.2.2 Restricted Sampling

3.2.3 Preserving Monotonicity

3.2.4 Discrete Distributions

3.2.4.1 Accumulated Roundoff Error

3.3 Cutpoint Method

3.3.1 Restricted Sampling

3.3.2 The Case of Large b - a

3.4 Composition Method

3.5 Alias Method

3.5.1 One or Two Uniform Deviates

3.5.2 Setting Up the Tables

3.5.3 Comparing the Cutpoint and Alias

Methods

3.6 Acceptance-Rejection Method

Example 3.1

3.6.1 Squeeze Method

Example 3.2

3.6.2 Avoiding Logarithmic Evaluations

3.6.3 Theory and Practice

3.7 Ratio-of-Uniforms Method

Example 3.3

3.8 Exact-Approximation Method

3.9 Algorithms for Selected Distributions

3.10 Exponential Distribution

3.11 Normal Distribution

3.12 Lognormal Distribution

3.13 Cauchy Distribution

3.14 Gamma Distribution

ALPHA less than equal to 1

ALPHA greater than 1

3.15 Beta Distribution

max(ALPHA,BETA) less than 1

min(ALPHA, BETA) greater than 1

min(ALPHA, BETA) less than 1 and

max(ALPHA, BETA) greater than

3.16 Student's t Distribution

3.17 Snedecor's F Distribution

3.18 Revisiting the Ratio-of-Uniforms

Method

3.19 Poisson Distribution

3.20 Binomial Distribution

3.21 Hypergeometric Distribution

3.22 Geometric Distribution

3.23 Negative Binomial Distribution

3.24 Multivariate Normal Distribution

3.25 Multinomial Distribution

3.26 Order Statistics

3.26.1 Generating the Smallest or

Largest Order Statistics

3.27 Sampling Without Replacement and Permutations

3.27.1 Generating k Out of n with Unequal Weights

3.28 Points in and on a Simplex

3.28.1 Points in XXX(n)(b)\XXX(n)(a) for (b) greater than equal to (a) greater


than

3.28.2 Convex Polytopes

3.29 Points in and on a Hyperellipsoid

3.30 Bernoulli Trials

3.31 Sampling from a Changing Probability Table

3.32 Random Spanning Trees

Exercises

References

4 Increasing Efficiency

4.1 Importance Sampling

4.1.1 Converting Unboundedness to Boundedness

4.1.2 Revisiting the Union Counting Problem

4.1.3 Exponential Change of Measure

4.1.4 Random Summations with Random Stopping Times

4.1.5 M/M/1 Exceedance Probability

4.1.6 Sequential Probability Ratio Test

4.2 Control Variates

4.2.1 Normal Control Variates

4.2.2 Binary Control Variates and Stochastic Ordering

4.2.3 Estimating the Distribution of

Maximal Flow

4.3 Stratified Sampling

4.3.1 Sample Size Considerations

4.3.2 Estimating a Distributional

Constant

4.3.3 Confidence Intervals

4.3.4 Poststratified Sampling

5.36.1 Random Walk on the Integers

5.36.2 Another Walk on a Hypercube

5.37 Thresholds

Exercises

References

6 Designing and Analyzing Sample Paths

6.1 Problem Context

6.1.1 Single Replication

6.1.2 Multiple Replications

6.2 A First Approach to Computing

Confidence Intervals

6.3 Warm-Up Analysis

6.3.1 Starting Each Replication in the Same State

6.3.2 Estimating Path Length

6.3.3 Choosing n(0) and t(0)

6.3.4 Stratifying the Assignments of

Initial States

6.3.5 Randomly Assigning Initial States

6.4 Choosing a "Good" Initial State or a "Good" &(0)

6.5 Strictly Stationary Stochastic Processes

6.6 Optimal Choice of Sample Path Length t and Number of Replications n

6.6.1 More General Correlation Structures

6.6.2 Negative ALPHA

6.7 Estimating Required Sample Path Length

6.8 Characterizing Convergence

6.8.1 I.I.D. Sequences

6.8.2 XXX-Mixing Sequences

6.8.3 Strongly Mixing Sequences

6.9 An Alternative View of var X(t)

6.10 Batch Means Method

6.10.1 Constant Number of Batches

6.10.2 Increasing Number of Batches

6.10.3 FNB and SQRT Rules

6.10.3.1 Interim Review

6.10.4 Comparing the FNB and SQRT Rules

6.10.5 LBATCH and ABATCH Rules

6.10.5.1 LBATCH Rule

6.10.5.2 ABATCH Rule

6.10.6 Test for Correlation

6.10.7 Comparing the FNB, SQRT, LBATCH, and ABATCH Rules

6.11 Batch Means Analysis Programs

6.11.1 p-Value

6.11.2 Prebatching

6.11.3 A Comparison with the Multiple Replication Approach

6.12 Regenerative Processes

6.12.1 Chain Splitting

6.13 Selecting an Optimal Acceptance

Scheme for Metropolis Sampling

Exercises

References

7 Generating Pseudorandom Numbers

7.1 Linear Recurrence Generators

7.2 Prime Modulus Generators

7.2.1 Choosing a Prime Modulus

7.2.2 Finding Primitive Roots

7.2.3 Sparseness and Nonuniformity

7.2.4 Computational Efficiency

7.3 Generators with M = 2^/(/ greater than

equal to 3)

7.3.1 Two's Complement

7.3.2 Dangerous Multipliers

7.4 Mixed Congruential Generators

7.5 Implementation and Portability

7.6 Apparent Randomness

7.6.1 Theory and Practice

7.7 Spectral Test

7.8 Minimal Number of Parallel Hyperplanes

7.9 Distance Between Points

7.10 Discrepancy

7.11 Beyer Quotient

7.12 Empirical Assessments

7.12.1 Testing Hypothesis j

7.12.2 Testing for Independence: H(0)

7.12.3 Testing for One-dimensional Uniformity: H(1)

7.12.4 Testing for Bivariate Uniformity: H(2)

7.12.5 Testing for Trivariate Uniformity: H(3)

7.12.6 An Omnibus Test: H(4)

7.13 Combining Linear Congruential Generators

7.13.1 Majorization

7.13.2 Shuffling

7.13.3 Summing Pseudorandom Numbers

7.14 j-Step Linear Recurrence

7.15 Feedback Shift Register Generators

7.15.1 Distributional Properties

7.16 Generalized Feedback Shift Register Generators

7.16.1 Initializing a GFSR Sequence

7.16.2 Distributional Properties

7.17 Nonlinear Generators

7.17.1 Quadratic Generators

7.17.2 Inversive Generators

Appendix

Exercises

References

Author Index

Subject Index