ON THE NUMBER OF 1'S PER CYCLE OF
A BINARY RANDOM MULTICYCLIC SEQUENCE
Natalia M. Mezhennaya1, Vladimir G. Mikhailov2
1 Applied Mathematics Department
Bauman Moscow State Technical University
ul. Baumanskaya 2-ya, 5/1
Moscow - 105005, RUSSIA
2 Discrete Mathematics Department
Steklov Mathematical Institute
of Russian Academy of Sciences
ul. Gubkina, 8
Moscow - 119991, RUSSIA

Abstract

A binary random multicyclic sequence is determined by a Boolean function of $r$ variables and $r$ independent binary random cyclic sequences with period lengths $m_1,\dots, m_r$. We obtain the limit distribution of the number of $1$'s per cycle of a multicyclic sequence in the case when the numbers $m_1,\ldots,m_r \to \infty$ and the number of $1$'s for each sequence has its own limit distribution.

Citation details of the article



Journal: International Journal of Applied Mathematics
Journal ISSN (Print): ISSN 1311-1728
Journal ISSN (Electronic): ISSN 1314-8060
Volume: 32
Issue: 5
Year: 2019

DOI: 10.12732/ijam.v32i5.10

Download Section



Download the full text of article from here.

You will need Adobe Acrobat reader. For more information and free download of the reader, please follow this link.

References

  1. [1] I.B. Bilyak, O.V. Kamlovskii, Frequency characteristics of cycles in output sequences generated by combining generators over the field of two elements, Prikl. Diskr. Mat., 3, No 29 (2015), 17–31 (in Russian).
  2. [2] O.V. Kamlovskii, Occurrence numbers for vectors in cycles of output sequences of binary combining generators, Probl. Inf. Trans., 53, No 1 (2017), 84–91.
  3. [3] V.M. Fomichev, On periods of complicated sequences, Mat. Vopr. Kibern., 13 (2004), 37–40 (in Russian).
  4. [4] P. Pohl, Description of MCV, a pseudo-random number generator, Scand. Actuar. J., 1 (1976), 1–14.
  5. [5] N.M. Mezhennaya, V.G. Mikhailov, On the distribution of the number of ones in the output sequence of the MCV-generator over GF(2), Mat. Vopr. Kriptogr., 4, No 4 (2013), 95–107 (in Russian).
  6. [6] N.M. Mezhennaya, V.G. Mikhailov, On the number of ones in outcome sequence of extended Pohl generator, Discrete Math. Appl., 31, No 1 (2019), 111–124 (in Russian).
  7. [7] N.M. Mezhennaya, V.G. Mikhailov, On the number of ones in the cycle of multicyclic sequence determined by Boolean function, Sib. Electr. Math. Reports, 16 (2019), 229–235.
  8. [8] O.V. Kamlovskii, Distribution properties of sequences produced by filtering generators, Prikl. Diskr. Mat., 3(21) (2013), 11-25 (in Russian).
  9. [9] Z.D. Dai, X.N. Feng, M.L. Liu, Z.X. Wan, Some statistical properties of feedforward sequences (I), Science in China (Ser. A), 37, No 1 (1994), 34–41.
  10. [10] Z.D. Dai, X.N. Feng, M.L. Liu, Z.X. Wan, Some statistical properties of feedforward sequences (II). Science in China (Ser. A), 37, No 2 (1994), 129–136.
  11. [11] H. Niederreiter, Distribution properties of feedback shift register sequences, Probl. Control and Inform. Theory, 15, No 1 (1986), 19–34.
  12. [12] R.A. Rueppel, Analysis and Design of Stream Ciphers. Springer Verlag, Berlin-Heidelberg (1986).
  13. [13] P. Pohl, On binary-exponent alternating sums, BIT Numerical Mathematics, 16, No 3 (1976), 308–312.
  14. [14] N.M. Mezhennaya, On distribution of number of ones in binary multicycle sequence, Prikl. Diskr. Mat., 1(27) (2015), 69–77 (in Russian).
  15. [15] J.C. Fu, W.Y.W. Lou, Z.-D. Bai, G. Li, The exact and limiting distributions for the number of successes in success runs within a sequence of Markov-dependent two-state trials, Ann. Inst. Statist. Math., 54, No 4 (2002), 719–730.
  16. [16] K. Inoue, S. Aki, Joint distributions of numbers of runs of specified length in a sequence of Markov dependent multistate trials, Ann. Inst. Statist. Math., 59, No 3 (2007), 577–595.
  17. [17] N.M. Mezhennaya, On the number of event appearances in a Markov chain, Int. J. Appl. Math., 32, No 3 (2019), 537–547; DOI: 10.12732/ijam.v32i3.13.
  18. [18] V.G. Mikhailov, Estimates of accuracy of the Poisson approximation for the distribution of number of runs of long string repetitions in a Markov chain, Discrete Math. Appl., 26, No 2 (2016), 105–113.
  19. [19] V.G. Mikhailov, A.M. Shoitov, On repetitions of long tuples in a Markov chain, Discrete Math. Appl., 25, No 5 (2015), 295–303.
  20. [20] T. Ritter, Ritter’s Crypto Glossary and Dictionary of Technical Cryptography, 2007; Available at: http://ciphersbyritter.com/GLOSSARY.HTM.
  21. [21] B. Preneel, O.A. Logachev, Boolean Functions in Cryptology and Information Security, IOS Press, Amsterdam (2008).

846