Monte Carlo method, random number, and pseudorandom number (Q550594)

The book is devoted to the mathematical foundation of the Monte Carlo method. A detailed explanation of pseudorandom numbers and random numbers is given, showing that a proper mathematical formulation of the Monte Carlo method leads to the development of the most reliable computer-aided sampling methods. In Chapter 1, the fair coin tossing process is introduced as the model process of random numbers and pseudorandom numbers. In Chapter 2, a proper mathematical formulation of the Monte Carlo method as well as rough definitions of random numbers and pseudorandom numbers are introduced. In Chapter 3, a partial recursive function, a fundamental notion in the theory of computation, is first introduced with its basic properties. Then the Kolmogorov complexity is introduced, and the notion of random numbers is defined. In the second half of Chapter 3, Martin-Löf's theorem is proved. This theorem explains the relation between random numbers and statistical tests of randomness. Chapter 4 deals with basic items of the computationally secure pseudorandom generator. A pseudorandom generator discovered by the author is introduced. It approaches the computationally secure pseudorandom generator from probability theory. Full proofs of the related theorems are given. Chapter 5 deals with the random Weyl sampling (RWS), which plays the role of a secure pseudorandom generator in the Monte Carlo integration. A numerical example proves DRWS (dynamical RWS) to be the most reliable sampling method for the Monte Carlo integration. Chapter 6 deals with the implementations of the RWS and DRWS pseudorandom generators by the C language.