BSU bulletin
Mathematics, Informatics

BSU bulletin. Mathematics, Informatics

Bibliographic description:
Mezhennaya N. M.
ON THE NUMBER OF ONES IN A MULTI-CYCLIC SEQUENCE WITH DEPENDENT SIGNS // BSU bulletin. Mathematics, Informatics. - 2018. №2. . - С. 3-12.
DOI: 10.18101/2304-5728-2018-2-3-12UDK: 519.214
The article considers one extension of a classical multi-cyclic generator with r reg- isters, which output sequence consists of elements formed by the products of binits in the registers under their cyclic shift relative to each other. The signs that fill each register are cyclically m-dependent, and the registers are independent of each other. We have found the mathematical expectation and variance for a random variable equal to the number of ones in the presented multi-cyclic sequence using the for- mula connecting its value with the number of ones for each registers. The central limit theorem for the number of ones is proved under the conditions when the lengths of registers tend to infinity, and the parameters of signs distributions filling the registers and the number of registers are fixed. We consider several particular cases of the limit theorem application to the sequences of random variables of a special type filling the registers. The numerical values of the convergence rate to the limiting distribution in the uniform metric for the case of independent and non- uniform fillings of registers are given.
multi-cyclic sequence; Pohl generator; number of ones; central limit theorem; m-dependent random variables.
List of references:
Pohl P. Description of MCV, a Pseudo-Random Number Generator. Scand. Ac- tuar. J. 1976. V. 1. Pp. 1–14. DOI: 10.1080/03461238.1976.10405931.

Mezhennaya N. M., Mikhailov V. G. O raspredelenii chisla edinits v vykhodnoi posledovatel'nosti generatora Pola nad polem GF (2) [On the Distribution of the Num- ber of Ones in the Output Sequence of MCV-Generator over GF(2)]. Matematicheskie voprosy kriptografii — Mathematical Aspects of Cryptography. 2013. V. 4. No. 4. Pp. 95–107. DOI: 10.4213/mvk101.

Bilyak I. B., Kamlovskii O. V. Chastotnye kharakteristiki tsiklov vykhodnykh posledovatel'nostei kombiniruyushchikh generatorov nad polem iz dvukh elementov [Frequency Characteristics of Cycles in Output Sequences Generated by Combining Generators over a Field of Two Elements]. Prikladnaya diskretnaya matematika — Applied Discrete Mathematics. 2015. V. 3, No. 29 (3). Pp. 17–31. DOI: 10.17223/20710410/29/2.

Kamlovskii O. V. Kamlovskii O. V. Kolichestvo poyavlenii vektorov na tsik- lakh vykhodnykh posledovatel'nostei dvoichnykh kombiniruyushchikh generatorov [Occurrence Numbers for Vectors in Cycles of Output Sequences of Binary Combin- ing Generators]. Problemy peredachi informatsii — Problems of Information Trans- mission. 2017. V. 53, No. 1. Pp. 84–91. DOI: 10.1134/S0032946017010070.

Kamlovskii O. V. Kolichestvo poyavlenii elementov v vyhodnyh posle- dovatel'nostyah fil'truyuschih generatorov [Distribution Properties of Sequences Pro- duced by Filtering Generators]. Prikladnaya diskretnaya matematika — Applied Dis- crete Mathematics. 2013. V. 3, No. 21. Pp. 11–25.

Agibalov G. P. Konechnye avtomaty v kriptografii [Finite Automata in Cryp- tography]. Prikladnaya diskretnaya matematika. Prilozhenie — Applied Discrete Mathematics. Supplement. 2009. V. 2. Pp. 43–73.

Mezhennaya N. M. Convergence Rate Estimators for the Number of Ones in Outcome Sequence of MCV-generator with m-dependent Registers Items. Sib. Elec- tron. Math. Reports. 2014. V. 11. Pp. 18–25.

Ibragimov I. A., Linnik Yu. V. Nezavisimye i statsionarno svyazannye velichiny

[Independent and Stationary Related Variables]. Moscow: Nauka Publ., 1965, 524 p.

Shiryaev A. N. Veroyatnost'-1 [Probability-1]. 4th ed. Moscow: MTsNMO, 2011. 552 p.

Mezhennaya N. M. O raspredelenii chisla edinits v dvoichnoi mul'titsik- licheskoi posledovatel'nosti [On Distribution of Number of Ones in Binary Multicycle Sequence]. Prikladnaya diskretnaya matematika — Applied Discrete Mathematics. 2015. V. 1(27). Pp. 69–77.

Mezhennaya N. M., Mikhailov V. G. Limit Theorem for Number of Ones in the Extended Pohl Generator Outcome Sequence. OP&PM Surveys on Applied and Indus- trial Mathematics. 2018. V. 25. No. 1. Pp. 48–50.