# Random and pseudo-random numbers

Jump to: navigation, search

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  and P. Martin-Löf . 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 ). 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.

How to Cite This Entry:
Random and pseudo-random numbers. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Random_and_pseudo-random_numbers&oldid=48421
This article was adapted from an original article by N.N. Chentsov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article