Individually random sequence and random number generators

A. V. Khovanskiy

Matematičeskoe modelirovanie, Tome 21 (2009) no. 7, pp. 93-105

Résumé

The constructive axiomatic approach to investigate individual properties of randomness differing from mass properties studied in classical probability theory based on measure theory is presented. Particularly the axiomatic definition of individually random sequence is given. The model (constructive element) of given axioms is Mobius sequence (without zero elements). The checking on performance of axioms in finite limits is based on “logarithmic postulate” that generalizes the idea of finite random sequence definition by Kolmogoroff ($Q1$). Complexity of axioms checking is $O(N^{1+\varepsilon}$) ($N$ – length of implementation). The proposed theory is developing of G. Polya idea which is noticed an interesting connection between analytical number theory (Riemann conjecture) and statistics and probability theory (random behavior of sequence constructed by Liouville or Mobius function values). On the base of the theory proposed two random generators are constructed. They can be applied in the practice of random processes arithmetical modeling. The Mobius random generator gives the potentially infinite sequence of a-random numbers uniformly distributed on the interval $[0,1)$ with guaranteed large usual and spectral fluctuations. The Legendre random generator though pseudorandom (finite length due to periodicity) has guaranteed small correlations (of the second order) and large spectral fluctuations. As the instruments of investigation the well-known results of analytical number theory are used (Dirichlet series, $\zeta$-function and so on) so as circulant properties that illustrate the deep connections between algebra, analysis and number theory. Particularly on the base of these circulant properties the individual analogue of Chebishev inequality is obtained so as elementary proof of $\Omega$-theorem for Mertens function and weak analogue of Polya recurrence law. Also some advancement in proof of Riemann conjecture is obtained.