View source for Random and pseudo-random numbers

<!--
r0772601.png
$#A+1 = 35 n = 0
$#C+1 = 35 : ~/encyclopedia/old_files/data/R077/R.0707260 Random and pseudo\AAhrandom numbers
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

Numbers  $  \xi _ {n} $(
in particular, binary digits  $  \alpha _ {n} $) 
whose sequential appearance satisfies some kind of statistical regularity (see [[Probability theory|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|Uniform distribution]]; [[Normal 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|Games, theory of]]), in [[Mathematical statistics|mathematical statistics]], in Monte-Carlo methods (cf. [[Monte-Carlo method|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 [[#References|[2]]] and P. Martin-Löf [[#References|[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 [[#References|[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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.M. Ermakov,   "Die Monte-Carlo Methode und verwandte Fragen" , Deutsch. Verlag Wissenschaft.  (1975)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.N. Kolmogorov,   "On tables of random numbers"  ''Sankhya Ser. A'' , '''25'''  (1963)  pp. 369–376</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  N.M. Korobov,   "On some questions of uniform distribution"  ''Izv. Akad. Nauk SSSR'' , '''14''' :  3  (1950)  pp. 215–238  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  D. Knuth,   "The art of computer programming" , '''2''' , Addison-Wesley  (1969)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  P. Martin-Löf,   "The definition of random sequences"  ''Inform. and Control'' , '''9'''  (1966)  pp. 602–619</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  N.N. Chentsov,   "Pseudo-random numbers for simulation of Markov chains"  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''7''' :  3  (1967)  pp. 632–643</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  A. Shen',   "Frequency approach to the definition of the notion of random sequence"  ''Semiotika i Informatika'' , '''18'''  (1982)  pp. 14–42  (In Russian)</TD></TR></table>

====Comments====

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Bratley,   B.L. Fox,   L.E. Schrage,   "A guide to simulation" , Springer  (1987)</TD></TR></table>