Monte Carlo: Concepts, Algorithms, and Applications

Contents

1. Introduction

  • About This Book
  • Available Software
  • What This Book Does Not Contain
  • Conventions

2. Estimating Volume and Count

  • Volume
  • Error and Sample Size Considerations
  • Confidence Intervals
  • Exploiting Regional Bounds
  • Relative Error
  • Network Reliability
  • Multivariable Integration
  • Exploiting Function Bounds
  • Exploiting ParameterBounds
  • Restricting the Sampling Region
  • Reducing the Sampling Dimension
  • Counting Problems
  • Sensitivity Analysis
  • Simultaneous Confidence Intervals
  • Ratio Estimation
  • Sequential Estimation

3. Generating Samples

  • Independence and Dependence
  • Inverse Transform Method
  • Cutpoint Method
  • Composition Method
  • Alias Method
  • Acceptance-Rejection Method
  • Ratio-of-Uniforms Method
  • Exact-Approximation Method
  • Algorithms for Selected Distributions
  • Exponential Distribution
  • Normal Distribution
  • Lognormal Distribution
  • Cauchy Distribution
  • Gamma Distribution
  • Beta Distribution
  • Student’s t Distribution
  • Snedecor’s F Distribution
  • Revisiting the Ratio-of-Uniforms Method
  • Poisson Distribution
  • Binomial Distribution
  • Hypergeometric Distribution
  • Geometric Distribution
  • Negative Binomial Distribution
  • Multivariate Normal Distribution
  • Multinomial Distribution
  • Order Statistics
  • Sampling Without Replacement and Permutations
  • Points in and on a Simplex
  • Points in and on a Hyperellipsoid
  • Bernoulli Trials
  • Sampling from a Changing Probability Table
  • Random Spanning Trees

4. Increasing Efficiency

  • Importance Sampling
  • Control Variates
  • Stratified Sampling
  • Inducing Correlation
  • Conditonal Monte Carlo

5. Random Tours

  • Markov Processes
  • Random Walk
  • Markov Time
  • Score Processes
  • Neutron Transport
  • Buffer Exceedance on a Production Line
  • Fredholm Equations of the Second Kind
  • Catastrophic Failure
  • First Passage Time
  • Random StoppingTime
  • Generating Random Points from a Target Distribution
  • Generating a Uniformly Distributed Point on a Finite Set
  • Generating All Coordinates in a Bounded Region on Each Step
  • Metropolis Method
  • Sampling Coordinates One at a Time
  • Markov Random Fields
  • Gibbs Sampling
  • Simulated Annealing
  • Bayesian Posterior Distributions
  • Edge Effects
  • Time to Stationarity
  • Spectral Structure
  • Bounds on Error
  • Varying Initial Conditions
  • Random Walk on a Hypercube
  • Conductance
  • More About a Random Walk on a Hypercube
  • An Alternative Error Bound for Stationarity
  • Sampling from a Hyperrectangular Grid
  • Sampling from a Hyperrectangle
  • Product Estimator
  • Estimating the Volume of a Convex Body
  • Estimating the Permanent
  • Coupling
  • Strong Markov Time
  • Strong Stationary Dual Process
  • Thresholds

6. Designing and Analyzing Sample Paths

  • Problem Context
  • A First Approach to Computing Confidence Intervals
  • Warm-Up Analysis
  • Choosing a “Good” Initial State or a “Good” Initial Distribution
  • Strictly Stationary Stochastic Processes
  • Optimal Choice of Sample Path Length t and Number of Replications n
  • Estimating Required Sample Path Length
  • Characterizing Convergence
  • An Alternative View of the Variance of the Sample Mean
  • Batch Means Method
  • Batch Means Analysis Programs
  • Regenerative Processes
  • Selecting an Optimal Acceptance Scheme for Metropolis Sampling

7. Generating Pseudorandom Numbers

  • Linear Recurrence Generators
  • Prime Modulus Generators
  • Power-of-Two Modulus Generators
  • Mixed Congruential Generators
  • Implementation and Portability
  • Apparent Randomness
  • Spectral Test
  • Minimal Number of Parallel Hyperplanes
  • Distance Between Points
  • Discrepancy
  • Beyer Quotient
  • Empirical Assessments
  • Combining Linear Congruential Generators
  • j-Step Linear Recurrence
  • Feedback Shift Register Generators
  • Generalized Feedback Shift Register Generators
  • Nonlinear Generators