Next: Linear Congruential Generators
Random Walks, Markov Chains and the Monte Carlo Method
Dr. Everett F. Carter Jr.
Taygeta Scientific Inc.
A look at some of the practical considerations when making calculations
based upon Monte Carlo type
methods.
- The kind of Monte Carlo calculation we will consider.
- Random number generation
- Pseudo-random numbers
- Quasi-random numbers
- Nonuniform distributions
- Monte Carlo integration with quasi-random numbers
- Solution to large linear algebra problems using Markov chains
- Generalization to solution of integral equations
- solving Fredholm integral equations of the second kind
The only good Monte Carlo is a dead Monte Carlo
Trotter & Tukey, 1954
The class of algorithms that solve problems probabilistically
are known by the (purposely) colorful name of Monte Carlo methods.
There are two types of Monte Carlo methods:
- Simple Monte Carlo -- The direct modeling of a random process.
(e.g. queueing problems).
- Sophisticated Monte Carlo methods recast deterministic problems
in probabilistic terms.
Anyone who considers arithmetical methods of
producing random digits is, of course,
in a state of sin.
John Von Neumann (1951)
There are many subtle problems that can occur and various
compromises have to be made in order to even pretend to generate random
numbers with a computer.
- A good random number generator must reasonably represent a known
probability distribution function (usually uniform over some finite domain).
- We do not want any built in trends, biases, or periodicities.
- We usually
do not the value generated at a given time to be correlated in any way
with previous values.
Use a trustworthy, long period random number generator.
The generator built in to your compiler is not trustworthy.
Skip Carter
Tue Jan 9 12:38:54 PST 1996