   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