Namespaces
Variants
Actions

Difference between revisions of "Random and pseudo-random numbers"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
Numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r0772601.png" /> (in particular, binary digits <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r0772602.png" />) 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r0772603.png" /> with distribution function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r0772604.png" />; then one speaks of (independent) random numbers distributed according to the law <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r0772605.png" />. The most commonly used examples are as follows: random numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r0772606.png" /> uniformly distributed on the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r0772607.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r0772608.png" />, equi-probable random binary digits <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r0772609.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726010.png" />, and random normal numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726011.png" /> distributed according to the normal law with mean <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726012.png" /> and variance 1 (cf. [[Uniform distribution|Uniform distribution]]; [[Normal distribution|Normal distribution]]). Random numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726013.png" /> with an arbitrary distribution function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726014.png" /> can be constructed from a sequence of uniformly-distributed random numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726015.png" /> by putting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726016.png" />, that is, they can be found from the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726018.png" />. 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
+
<!--
 +
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.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726019.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726020.png" /></td> </tr></table>
+
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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726021.png" />, then a player chooses the first strategy, but if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726022.png" />, then he/she takes the second.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726023.png" /> be the countably-dimensional unit hypercube, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726024.png" /> be the Lebesgue measure on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726025.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726026.png" /> be a largest constructively-described measurable set of measure zero (it exists). Then any sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726027.png" /> can be regarded as typical, and so taken as a sequence of uniformly-distributed random numbers. Similarly one can introduce the concept of constructive <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726029.png" />-typicality of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726030.png" />-sequence of binary symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726032.png" />, with respect to the system of all events <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726033.png" />: to be of measure not more than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726034.png" /> and of length of description not more than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726035.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077260/r07726036.png" />-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.
+
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.
 
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.
Line 15: Line 67:
 
====References====
 
====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>
 
<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====
 
====Comments====
 
  
 
====References====
 
====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>
 
<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>

Latest revision as of 08:09, 6 June 2020


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)

Comments

References

[a1] P. Bratley, B.L. Fox, L.E. Schrage, "A guide to simulation" , Springer (1987)
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