HomeIssuesOn the asymptotic normality of the frequencies of letters in a multicyclic sequence

On the asymptotic normality of the frequencies of letters in a multicyclic sequence | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 48. DOI: 10.17223/20710410/48/1

A multidimensional central limit theorem is proved for sign frequencies in a multicyclic sequence formed by adding characters from r ≥ 2 independent vectors of coprime lengths ni, ..., nr of independent random variables distributed uniformly on some finite alphabet when the register lengths are n1, ..., nr ⟶ ∞, and the size of the alphabet is fixed. An estimate is obtained of the rate of convergence in the uniform metric of the one-dimensional distribution law of any of the sign frequencies (with a suitable normalization) to the standard normal law.
Download file
Counter downloads: 119
  • Title On the asymptotic normality of the frequencies of letters in a multicyclic sequence
  • Headline On the asymptotic normality of the frequencies of letters in a multicyclic sequence
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 48
  • Date:
  • DOI 10.17223/20710410/48/1
Keywords
multicyclic sequence, central limit theorem, frequencies of letters, Janson’s method, мультициклическая последовательность, центральная предельная теорема, частоты знаков, метод Янсона
Authors
References
Pohl P. Description of MCV, a pseudo-random number generator // Scand. Actuar. J. 1976. V. 1. P. 1-14.
Pohl P. MCV - a Fast Pseudo-Random Number Generator with Extremely Good Statistical Properties. PhD Dissertation. University of Stockholm, Stockholm, 1975. 34 p.
Lehmer D. H. Mathematical methods in large-scale computing units // Proc. Second Symp. Large-Scale Digital Calculating Machinery, Cambridge (Mass.). Harvard University Press, 1951. P. 141-146.
Камловский О. В. Количество появлений элементов в выходных последовательностях фильтрующих генераторов // Прикладная дискретная математика. 2013. №3(21). С.11-25.
Биляк И. Б., Камловский О. В. Частотные характеристики циклов выходных последовательностей комбинирующих генераторов над полем из двух элементов // Прикладная дискретная математика. 2015. №3(29). С. 17-31.
Камловский О. В. Количество появлений векторов на циклах выходных последовательностей двоичных комбинирующих генераторов // Проблемы передачи информации. 2017. Т. 53. №1. С. 92-100.
Агибалов Г.П. Конечные автоматы в криптографии // Прикладная дискретная математика. Приложение. 2009. №2. С. 43-73.
Dai Z.D., Feng X.N., Liu M.L., and Wan Z.X. Some statistical properties of feedforward sequences (I) // Science in China (Ser. A). 1994. V.37. No. 1. P.34-41.
Dai Z.D., Feng X.N., Liu M.L., and Wan Z.X. Some statistical properties of feedforward sequences (II) // Science in China (Ser. A). 1994. V. 37. No. 2. P.129-136.
Niederreiter H. Distribution properties of feedback shift register sequences // Probl. Control and Inform. Theory. 1986. V. 15. No. 1. P. 19-34.
Меженная Н. М., Михайлов В. Г. О числе появлений знаков в мультициклической случайной последовательности по модулю 4 // Дискретная математика. 2014. Т. 26. №4. С. 51-58.
Меженная Н. М., Михайлов В. Г. О распределении числа единиц в выходной последовательности генератора Пола над полем GF(2) // Математические вопросы криптографии. 2013. Т. 4. №4. С. 95-107.
Тюрин И. С. Уточнения остаточного члена в теореме Ляпунова // Теория вероятностей и ее применения. 2011. Т. 56. №3. С. 808-811.
Меженная Н. М. О распределении числа единиц в двоичной мультициклической последовательности // Прикладная дискретная математика. 2015. №1(27). С. 69-77.
Меженная Н. М., Михайлов В. Г. Об асимптотической нормальности чисел появлений знаков в неравновероятной мультициклической случайной последовательности по модулю 4 // Математические вопросы криптографии. 2016. Т. 7. №4. С. 81-94.
Биллингсли П. Сходимость вероятностных мер. М.: Наука, 1977. 352 с.
Janson S. Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs // Ann. Probab. 1988. V. 16. No. 1. P. 305-312.
Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. 8-е изд. М.: Физматлит, 2003. Т. 1. 680c.
Baldi P. and Rinott Y. On normal approximations of distributions in terms of dependency graphs // Ann. Probab. 1989. V. 17. No. 4. P. 1646-1650.
On the asymptotic normality of the frequencies of letters in a multicyclic sequence | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 48. DOI: 10.17223/20710410/48/1
On the asymptotic normality of the frequencies of letters in a multicyclic sequence | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 48. DOI: 10.17223/20710410/48/1