Stochastic Simulation

CHAPTER 7

Uses of Simulation

In a sense this whole book is about uses of simulation. What concerns us here are some of the less obvious uses of simulation, which fall into two broad categories. The first category is within statistics, to perform statistical inference. Obvious uses of simulation in statistics are those of randomization such as randomizing experiments and randomized tests. More innovative uses are Monte-Carlo tests, the bootstrap, and Monte-Carlo confidence intervals. Often when a distribution is unknown, for example that of a test statistic, it is tempting to replace it by a distribution estimated from a simulated sample. Undoubtedly this has been done for many years in an ad hoc way. Increased computer power has made it possible on a large scale, and more formal methods such as the bootstrap and Monte-Carlo tests have been developed. These are the subject of Section 7.1.

Stochastic algorithms have recently proved successful in both cryptography and optimization. Although there is a certain appeal about an algorithm that will always succeed, in practice we may be able to afford to solve a much larger problem with a probabilistic algorithm that has only a high probability of success. Consider, as an example, the problem of finding whether a large integer is prime or the product of a small number of large primes. (Small prime factors can be found by conventional means.) There are stochastic algorithms that will report correctly if the number is prime, and find a ...