The accompanying table gives data for verifying that ran4 and psdes work correctly on your machine. We do not advise the use of ran4 unless you are able to reproduce the hex values shown. Typically, ran4 is about 4 times slower than ran0 (§), or about 3 times slower than ran1. | Quasi- thatis Sub- Random Sequences 309 CITED REFERENCES AND FURTHER READING Hammersley . and Handscomb . 1964 Monte Carlo Methods London Methuen . Shreider Yu. A. ed. 1966 The Monte Carlo Method Oxford Pergamon . Sobol . 1974 The Monte Carlo Method Chicago University of Chicago Press . Kalos . and Whitlock . 1986 Monte Carlo Methods New York Wiley . Quasi- that is Sub- Random Sequences We have just seen that choosing N points uniformly randomly in an n-dimensional space leads to an error term in Monte Carlo integration that decreases as 1 vN. In essence each new point sampled adds linearly to an accumulated sum that will become the function average and also linearly to an accumulated sum of squares that will become the variance equation . The estimated error comes from the square root of this variance hence the power N1 2. Just because this square root convergence is familiar does not however mean that it is inevitable. A simple counterexample is to choose sample points that lie on a Cartesian grid and to sample each grid point exactly once in whatever order . The Monte Carlo method thus becomes a deterministic quadrature scheme albeit a simple one whose fractional error decreases at least as fast as N-1 even faster if the function goes to zero smoothly at the boundaries of the sampled region or is periodic in the region . The trouble with a grid is that one has to decide in advance how fine it should be. One is then committed to completing all of its sample points. With a grid it is not convenient to sample until some convergence or termination criterion is met. One might ask if there is not some intermediate scheme some way to pick sample points at random yet spread out in some self-avoiding way avoiding the chance clustering that occurs with uniformly random points. A similar question arises for tasks other than Monte Carlo integration. We might want to search an n-dimensional space for a point where some locally computable .
