Random and pseudo-random numbers

Numbers $ \xi _ {n} $( in particular, binary digits $ \alpha _ {n} $) whose sequential appearance satisfies some kind of statistical regularity (see Probability theory). One distinguishes random numbers, being generated by a stochastic apparatus, and pseudo-random numbers, being constructed using arithmetical algorithms. It is usually assumed (for better or worse reason) that the sequence obtained (or constructed) has frequency properties that are "typical" for a sequence of independent realizations of some random variable $ \xi $ with distribution function $ F ( z) $; then one speaks of (independent) random numbers distributed according to the law $ F ( z) $. The most commonly used examples are as follows: random numbers $ \xi _ {n} $ uniformly distributed on the interval $ [ 0 , 1 ] $, $ {\mathsf P} ( \xi _ {n} < x ) = x $, equi-probable random binary digits $ \alpha _ {n} $, $ {\mathsf P} \{ \alpha _ {n} = 0 \} = {\mathsf P} \{ \alpha _ {n} = 1 \} = 1/2 $, and random normal numbers $ \eta _ {n} $ distributed according to the normal law with mean $ 0 $ and variance 1 (cf. Uniform distribution; Normal distribution). Random numbers $ \zeta _ {n} $ with an arbitrary distribution function $ F ( z) $ can be constructed from a sequence of uniformly-distributed random numbers $ \xi _ {n} $ by putting $ \xi _ {n} = F ^ { - 1 } ( \zeta _ {n} ) $, that is, they can be found from the equation $ \zeta _ {n} = F ( \xi _ {n} ) $, $ n = 1 , 2 ,\dots $. There are also other methods of construction: for example, it is analytically simpler to obtain normally-distributed random numbers from uniformly-distributed random numbers by using the pairs

$$ \zeta _ {2 n - 1 } = \ \sqrt {- 2 \mathop{\rm ln} \xi _ {2n} } \cos 2 \pi \xi _ {2 n - 1 } , $$

$$ \zeta _ {2n} = \sqrt {- 2 \mathop{\rm ln} \xi _ {2n} } \sin 2 \pi \xi _ {2 n - 1 } . $$

The digits of uniformly-distributed random numbers in binary notation are equi-probable random binary digits; conversely, by grouping equi-probable random binary digits into infinite sequences one obtains uniformly-distributed random numbers.

Random and pseudo-random numbers are used in practice in the theory of games (cf. Games, theory of), in mathematical statistics, in Monte-Carlo methods (cf. Monte-Carlo method), and in cryptography, for the concrete realization of non-determined algorithms and behaviour predicted only "on the average" . For example, if the next $ \alpha _ {n} = 0 $, then a player chooses the first strategy, but if $ \alpha _ {n} = 1 $, then he/she takes the second.

It is only possible to attach a strict mathematical sense to the concept of random numbers in the framework of the algorithmic probability theory of A.N. Kolmogorov [2] and P. Martin-Löf [5]. Let $ H = \times _ {n=} 1 ^ \infty \{ {x _ {n} } : {0 \leq x _ {n} \leq 1 } \} $ be the countably-dimensional unit hypercube, let $ \lambda $ be the Lebesgue measure on $ H $ and let $ G \subset H $ be a largest constructively-described measurable set of measure zero (it exists). Then any sequence $ \{ x _ {n} \} \notin G $ can be regarded as typical, and so taken as a sequence of uniformly-distributed random numbers. Similarly one can introduce the concept of constructive $ ( \epsilon , l ) $- typicality of an $ N $- sequence of binary symbols $ a _ {j} $, $ j = 1 \dots N $, with respect to the system of all events $ B \subset \{ 0 ; 1 \} ^ {N} $: to be of measure not more than $ \epsilon $ and of length of description not more than $ l $. It is evident from the definition that a typical sequence of uniformly-distributed random numbers cannot itself be constructive, and even the construction of an $ ( \epsilon , l ) $- typical sequence of random symbols requires an extraordinary large search. Therefore, in practice one uses simpler algorithms, allowing checking of their statistical "quality" with a few tests. Thus, in constructing uniformly-distributed random numbers one must necessarily test the uniform distribution of the sequence (see [3]). In simple problems, the fulfillment of certain tests can actually guarantee the usefulness of a sequence. It is sometimes more effective to use correlated random numbers, constructed from a sequence of uniformly-distributed random numbers.

Tables of random numbers and random digits have been published. However, it appears to be impossible to guarantee that they satisfy all reasonable statistical tests for non-correlation.

References

[1]	S.M. Ermakov, "Die Monte-Carlo Methode und verwandte Fragen" , Deutsch. Verlag Wissenschaft. (1975) (Translated from Russian)
[2]	A.N. Kolmogorov, "On tables of random numbers" Sankhya Ser. A , 25 (1963) pp. 369–376
[3]	N.M. Korobov, "On some questions of uniform distribution" Izv. Akad. Nauk SSSR , 14 : 3 (1950) pp. 215–238 (In Russian)
[4]	D. Knuth, "The art of computer programming" , 2 , Addison-Wesley (1969)
[5]	P. Martin-Löf, "The definition of random sequences" Inform. and Control , 9 (1966) pp. 602–619
[6]	N.N. Chentsov, "Pseudo-random numbers for simulation of Markov chains" Zh. Vychisl. Mat. i Mat. Fiz. , 7 : 3 (1967) pp. 632–643
[7]	A. Shen', "Frequency approach to the definition of the notion of random sequence" Semiotika i Informatika , 18 (1982) pp. 14–42 (In Russian)

References

[a1]	P. Bratley, B.L. Fox, L.E. Schrage, "A guide to simulation" , Springer (1987)