Arithmetic random number generator

Arithmetic random number generators are random number generators for generating random numbers that are based on arithmetic . They are based on Weyl's theorem , use

${\displaystyle u_{i}=iy_{0}-\lfloor iy_{0}\rfloor =iy_{0}{\bmod {1}}}$

as a generator, where the definitions in Weyl's Theorem apply, i.e. in particular an irrational number . Here stands for the modulo operation. denotes the largest integer that is less than or equal to . ${\displaystyle y_{0}\in {]0,1[}}$ ${\displaystyle \mathrm {mod} }$ ${\displaystyle \lfloor a\rfloor }$ ${\displaystyle a}$

Arithmetic random number generators are used in practice instead of physical random number generators . Since no irrational numbers can be represented on pocket calculators or computers , one often limits oneself to recursive arithmetic random number generators .

Recursive arithmetic random number generators

These are random number generators that are based on arithmetic random number generators , but with which one is satisfied with certain rational numbers as random numbers , since irrational numbers from which arithmetic random number generators are based cannot be displayed on computers. So they are pseudo random number generators .

To initialize the generator, start values called seeds are used. You can e.g. B. fixed if the generated number sequence should be repeatable, or you initialize it in a random way. The computer clock is often used as a data source for this, so the current time determines the initial values ​​of the . ${\displaystyle y_{0},y_{1},...,y_{k-1}}$ ${\displaystyle y_{n}}$

An arithmetic function

${\displaystyle f:\left\{0,...,m-1\right\}^{k}\rightarrow \left\{0,...,m-1\right\}}$

now successively generates the values

${\displaystyle y_{n}:=f(y_{n-k},y_{n-k+1},...,y_{n-1})}$, where . ${\displaystyle n\geq k}$

The random numbers in the interval are then e.g. B .: ${\displaystyle [0;1[}$

${\displaystyle u_{i}:={\frac {y_{i}}{m}}}$.

For the random numbers, you are satisfied with values ​​from the set , where is a sufficiently large natural number . ${\displaystyle \left\{0,{\frac {1}{m}},{\frac {2}{m}},...,{\frac {m-1}{m}}\right\}}$ ${\displaystyle m}$

Probably the most important recursive arithmetic random number generators are congruence generators .

advantages

With a suitable function   , random numbers can be generated quickly . These are completely reproducible when specifying the seed. ${\displaystyle f}$

disadvantage

The consequence is deterministic . No real random numbers are generated, only pseudo- random numbers . So it is a pseudo random number generator . The determinacy also means that there is no independence and equal distribution of the sequence. In particular, a loop will be created at some point. So there is with all . The smallest is called the period . ${\displaystyle (y_{n})_{n\geq 0}}$ ${\displaystyle n_{0},p\in \mathbb {N} }$ ${\displaystyle y_{n+p}=y_{n}}$ ${\displaystyle n\geq n_{0}}$ ${\displaystyle p}$

Whether these disadvantages play a role depends on the application: For example, it is not a disadvantage for simulations that the generated numbers are predictable as long as the period length is sufficiently large. On the contrary: the reproducibility of the numbers makes analysis and troubleshooting easier.

literature

• J. Baumeister: Numerical Methods in Financial Mathematics. (postscript) Chapter 3, Random Numbers and Their Generation. Goethe University, Frankfurt am Main, 2009, accessed April 22, 2019 .