No RNG Is IdealFinite precision arithmetic finite number of states cycles
Period = length of cycle
If period > number of values needed, effectively acyclic
Reproducible correlations
Often speed versus quality trade-offs
Parallel Programming in C with MPI and OpenMP Michael J. Quinn
Chapter 10 Monte Carlo Methods
Chapter Objectives
Introduce Monte Carlo methods
Introduce techniques for parallel random number generation
Outline
Monte Carlo method
Sequential random number generators
Parallel random number generators
Generating non-uniform random numbers
Monte Carlo case studies
Monte Carlo Method
Solve a problem using statistical sampling
Name comes from Monaco’s gambling resort city
First important use in development of atomic bomb during World War II
Applications of Monte Carlo Method
Evaluating integrals of arbitrary functions of 6+ dimensions
Predicting future values of stocks
Solving partial differential equations
Sharpening satellite images
Modeling cell populations
Finding approximate solutions to NP-hard problems
Example of Monte Carlo Method
Area = D2 Area = D2/4 D D
Example of Monte Carlo Method
Area = D2
Absolute Error
Absolute error is a way to measure the quality of an estimate
The smaller the error, the better the estimate
a: actual value
e: estimated value
Absolute error = |e-a|/a
The expected value of (1/n)(f(x0) + … + f(xn-1)) is f
Why Monte Carlo Works
Why Monte Carlo is Effective
Error in Monte Carlo estimate decreases by the factor 1/n1/2
Rate of convergence independent of integrand’s dimension
Deterministic numerical integration methods do not share this property
Hence Monte Carlo superior when integrand has 6 or more dimensions
Parallelism in Monte Carlo Methods
Monte Carlo methods often amenable to parallelism
Find an estimate about p times faster
OR
Reduce error of estimate by p1/2
Random versus Pseudo-random
Virtually all computers have “random number” generators
Their operation is deterministic
Sequences are predictable
More accurately called “pseudo-random number” generators
In this chapter “random” is shorthand for “pseudo-random”
“RNG” means “random number generator”
Properties of an Ideal RNG
Uniformly distributed
Uncorrelated
Never cycles
Satisfies any statistical test for randomness
Reproducible
Machine-independent
Changing “seed” value changes sequence
Easily split into independent subsequences
Fast
Limited memory requirements
No RNG Is Ideal
Finite precision arithmetic finite number of states cycles
Period = length of cycle
If period > number of values needed, effectively acyclic
Reproducible correlations
Often speed versus quality trade-offs
Linear Congruential RNGs
Multiplier Additive constant Modulus Sequence depends on choice of seed, X0
Period of Linear Congruential RNG
Maximum period is M
For 32-bit integers maximum period is 232, or about 4 billion
This is too small for modern computers
Use a generator with at least 48 bits of precision
Comments