Page 95 - DCAP601_SIMULATION_AND_MODELING

Unit 6: Discrete System Simulation (III)

A classic example is Rabin’s algorithm for primality testing: for any n which is not prime, a Notes
random x has at least a 75% chance of proving that n is not prime. Hence, if n is not prime, but x
says that it might be, we have observed at most a 1-in-4 event. If 10 different random x say that
“n is probably prime” when it is not, we have observed a one-in-a-million event.
In general a Monte Carlo algorithm of this kind produces one correct answer with a guarantee
n is composite, and x proves it so, but another one without, but with a guarantee of not getting
this answer when it is wrong too often — in this case at most 25% of the time.

Monte Carlo and Random Numbers

Interestingly, Monte Carlo simulation methods do not always require truly random numbers to
be useful — while for some applications, such as primality testing, unpredictability is vital.
Many of the most useful techniques use deterministic, pseudo-random sequences, making it
easy to test and re-run simulations. The only quality usually necessary to make good simulations
is for the pseudo-random sequence to appear “random enough” in a certain sense.
What this means depends on the application, but typically they should pass a series of statistical
tests. Testing that the numbers are uniformly distributed or follow another desired distribution
when a large enough number of elements of the sequence are considered is one of the simplest
and most common ones.

General

Statistics Portal

1. Auxiliary field Monte Carlo
2. Bootstrapping (statistics)
3. Demon algorithm
4. Evolutionary Computation
5. Las Vegas algorithm
6. Markov chain

7. Molecular dynamics
8. Monte Carlo option model
9. Monte Carlo integration
10. Quasi-Monte Carlo method
11. Random number generator
12. Randomness
13. Resampling (statistics)

Application Areas

1. Graphics, particularly for ray tracing; a version of the Metropolis-Hastings algorithm is
also used for ray tracing where it is known as Metropolis light transport
2. light transport in biological tissue
3. Monte Carlo methods in finance

LOVELY PROFESSIONAL UNIVERSITY 89