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.

Bibliographie

[1] Khalmosh P., Teoriya mery, IL, M., 1953

[2] Sobol I. M., Chislennye metody Monte-Karlo, Nauka, M., 1973 | MR

[3] Dyuge D., Teoreticheskaya i prikladnaya statistika, Nauka, M., 1972

[4] Kramer G., Matematicheskie metody statistiki, Mir, M., 1976 | MR

[5] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, T. 1, 2, Mir, M., 1964 | Zbl

[6] Shiryaev A. N., Veroyatnost, Nauka, M., 1980 | MR | Zbl

[7] Knut D., Iskusstvo programmirovaniya dlya EVM, T. 2, Mir, M., 1977 | Zbl

[8] fon Mizes R., Veroyatnost i statistika, M.–L., 1930

[9] Shnorr K. P., “Edinyi podkhod k opredeleniyu sluchainykh posledovatelnostei”, BKS. Slozhnost vychislenii i algoritmov, Mir, M., 1974, 370–387 | MR

[10] Kolmogorov A. N., Osnovnye ponyatiya teorii veroyatnostei, ONTI, M.–L., 1936

[11] Lamperti Dzh., Veroyatnost, Nauka, M., 1973 | Zbl

[12] Ebbinkhauz G.-D., Yakobs K., Man F.-K., Mashina Tyuringa i rekursivnye funktsii, Mir, M., 1972 | MR

[13] Khovanskii A. V., Resheto Eratosfena za O(N) deistvii, preprint, 5042/16, IAE, M., 1990, 8 pp.

[14] Bukhshtab A. A., Teoriya chisel, Prosveschenie, M., 1966 | Zbl

[15] Uspenskii V. A., Chetyre algoritmicheskikh litsa sluchainosti, MTsNMO, M., 2006

[16] Poia D., Matematika i pravdopodobnye rassuzhdeniya, Nauka, M., 1975 | MR

[17] Titchmarsh E. K., Teoriya $\zeta$-funktsii, IL, M., 1953

[18] Postnikov A. G., Vvedenie v analiticheskuyu teoriyu chisel, Nauka, M., 1971 | MR | Zbl

[19] Gelfond A. O., Linnik Yu. V., Elementarnye metody v teorii chisel, FML, M., 1962

[20] Devenport G., Multiplikativnaya teoriya chisel, Nauka, M., 1971 | MR

[21] Odlyzko A. M., Riele H. J., “Disproof of the Mertens conjecture”, J. reine angew. Math., 357 (1985), 138–160 | MR | Zbl

[22] Kats M., Statisticheskaya nezavisimost v teorii veroyatnostei, analize i teorii chisel, IL, M., 1963

[23] Khovanskii A. V., “Analog neravenstva Chebysheva i individualnye svoistva sluchainosti”, Matematicheskaya konferentsiya FIAE, tezisy dokladov, M., 1990, 37–38

[24] Khovanskii A. V., Skopintsev D. A., K voprosu opredeleniya sluchainoi posledovatelnosti i postroeniya datchikov sluchainykh chisel, ravnomerno raspredelënnykh na [0,1), preprint IAE, 5181/16, TsNIIatominform, M., 1990, 15 pp.

[25] Billingslei P., Ergodicheskaya teoriya i informatsiya, Mir, M., 1969 | MR

[26] Borevich Z. I., Shafarevich I. R., Teoriya chisel, Nauka, M., 1985 | MR | Zbl

[27] E. Bekkenbakh (Red.), Prikladnaya kombinatornaya matematika, Mir, M., 1968

[28] Khovanskii A. V., O nesuschestvovanii adamarovykh tsirkulyantov pri $N>4$, preprint 4530/16, IAE, M., 1987, 9 pp.

[29] Khovanskii A. V., O nekotorykh svoistvakh tsirkulyantov i vozmozhnosti ikh primeneniya v transmissionnoi kompyuternoi tomografii, preprint 0032-A, TsNIIatominform, TRINITI, M., 1997, 13 pp. | MR

[30] Khovanskii A. V., “Metody postroeniya pochti adamarovykh tsirkulyantov i vozmozhnosti ikh prilozheniya”, Matematicheskoe modelirovanie, 8:1 (1996), 69–76 | MR | Zbl

[31] Chebotarëv N. G., Vvedenie v teoriyu algebr, OGIZ, Gostekhizdat, M.–L., 1943

[32] Voevodin V. V., Tyrtyshnikov E. E., Vychislitelnye protsessy s tëplitsevymi matritsami, Nauka, M., 1987 | MR | Zbl

[33] Kolmogorov A. N., Fomin S. V., Elementy teorii funktsii i funktsionalnogo analiza, Nauka, M., 1972

[34] Gantmakher F. R., Teoriya matrits, Nauka, M., 1967 | MR

[35] Bendat Dzh., Pirsol A., Izmerenie i analiz sluchainykh protsessov, Mir, M., 1984

[36] Khovanskii A. V., Dëmkin A. M., “Metody blochno-tsiklicheskogo obrascheniya v kompyuternoi tomografii”, Matematicheskoe Modelirovanie, 13:1 (2001), 51–64 | MR

[37] Bakhman F., Shmidt E., $N$-ugolniki, Mir, M., 1973

[38] Voevodin V. V., Kuznetsov Yu. A., Matritsy i vychisleniya, Nauka, M., 1984 | MR | Zbl

[39] Glassman J. A., “A generalization of the fast Fourier transform”, IEEE, Trans. Comp., C-19 (1970), 105–116 | DOI | MR | Zbl

[40] Breisuell R., Preobrazovanie Khartli, Mir, M., 1990 | MR

[41] Diamond G., “Elementarnye metody v izuchenii raspredeleniya prostykh chisel”, UMN, 45:2(272) (1990), 79–114 | MR | Zbl

[42] Gauss K. F., Trudy po teorii chisel, Izd-vo AN SSSR, M., 1959 | MR