Geodesic
On the asymptotic normality of the frequencies of~letters in a multicyclic sequence
Prikladnaâ diskretnaâ matematika, no. 2 (2020), pp. 5-15.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper presents a multidimensional central limit theorem for frequencies $\xi_{y,T}$ of letters $y$, $y \in \{0,1,\ldots,N-1\}$, $N\ge 2$, in a multicyclic sequence of length $T$ formed by addition letters from $r$, $r \ge 2 $, independent vectors of coprime lengths $n_1,\ldots, n_r$ consisted of independent random variables distributed uniformly on the set $\{0,1,\ldots,N-1\}$: if the lengths of the registers $n_1,\ldots,n_r \to \infty$, the size of the alphabet $N$ is fixed, and $T\left(\textstyle\sum\limits_{k=1}^r n_k^{-1}\right)^{2(1-1/m)} \to 0$ for some natural number $ m \ge 3$, then the random vector $(T/N)^{-1/2}(\xi_{0,T}-T/N,\ldots,\xi_{N-2,T}-T/N)$ converge in distribution to the $(N-1)$-dimensional normal law with zero mean and non-degenerate covariance matrix. We also obtain an estimate for the rate of convergence in the uniform metric of the one-dimensional distribution function of any of the frequencies $\xi_{y,T}$ to the distribution function of the standard normal law $\Phi$ of the form $$ \left|\mathsf{P}\left\{\xi_{y,T}\frac{T}{N}+\frac{x}{N}\sqrt{T(N-1)}\right\}- \Phi(x)\right|\le C T^{3/4}\left(\textstyle\sum\limits_{k=1}^r {n_k^{-1}}\right) $$ for any $y\in\mathcal{A}_N, x \in \mathbb{R},$ where $C>0$ is known constant.
Keywords: multicyclic sequence, central limit theorem, frequencies of letters, Janson's method. 
@article{PDM_2020_2_a0,
     author = {N. M. Mezhennaya and V. G. Mikhailov},
     title = {On the asymptotic normality of the frequencies of~letters in a multicyclic sequence},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {5--15},
     publisher = {mathdoc},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2020_2_a0/}
}
TY  - JOUR
AU  - N. M. Mezhennaya
AU  - V. G. Mikhailov
TI  - On the asymptotic normality of the frequencies of~letters in a multicyclic sequence
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2020
SP  - 5
EP  - 15
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2020_2_a0/
LA  - ru
ID  - PDM_2020_2_a0
ER  - 
%0 Journal Article
%A N. M. Mezhennaya
%A V. G. Mikhailov
%T On the asymptotic normality of the frequencies of~letters in a multicyclic sequence
%J Prikladnaâ diskretnaâ matematika
%D 2020
%P 5-15
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2020_2_a0/
%G ru
%F PDM_2020_2_a0
N. M. Mezhennaya; V. G. Mikhailov. On the asymptotic normality of the frequencies of~letters in a multicyclic sequence. Prikladnaâ diskretnaâ matematika, no. 2 (2020), pp. 5-15. http://geodesic.mathdoc.fr/item/PDM_2020_2_a0/

[1] Pohl P., “Description of MCV, a pseudo-random number generator”, Scand. Actuar. J., 1 (1976), 1–14 | DOI | MR | Zbl

[2] Pohl P., MCV — a Fast Pseudo-Random Number Generator with Extremely Good Statistical Properties, PhD Dissertation, University of Stockholm, Stockholm, 1975, 34 pp.

[3] Lehmer D. H., “Mathematical methods in large-scale computing units”, Proc. Second Symp. Large-Scale Digital Calculating Machinery, Harvard University Press, Cambridge (Mass.), 1951, 141–146 | MR

[4] Kamlovskii O. V., “Distribution properties of sequences produced by filtering generators”, Prikladnaya Diskretnaya Matematika, 2013, no. 3(21), 11–25 (in Russian)

[5] Bilyak I. B., Kamlovskii O. V., “Frequency characteristics of cycles in output sequences generated by combining generators over the field of two elements”, Prikladnaya Diskretnaya Matematika, 2015, no. 3(29), 17–31 (in Russian)

[6] Kamlovskii O. V., “Occurrence numbers for vectors in cycles of output sequences of binary combining generators”, Problems Inform. Transmission, 53:1 (2017), 84–91 | DOI | MR | Zbl

[7] Agibalov G. P., “Finite automata in cryptography”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2009, no. 2, 43–73 (in Russian)

[8] Dai Z. D., Feng X. N., Liu M. L., Wan Z. X., “Some statistical properties of feedforward sequences (I)”, Science in China (Ser. A), 37:1 (1994), 34–41 | MR | Zbl

[9] Dai Z. D., Feng X. N., Liu M. L., Wan Z. X., “Some statistical properties of feedforward sequences (II)”, Science in China (Ser. A), 37:2 (1994), 129–136 | MR | Zbl

[10] Niederreiter H., “Distribution properties of feedback shift register sequences”, Probl. Control and Inform. Theory, 15:1 (1986), 19–34 | MR | Zbl

[11] Mezhennaya N. M., Mikhailov V. G., “On frequencies of elements in multicyclic random sequence modulo 4”, Discrete Math. Appl., 25:6 (2015), 359–365 | DOI | DOI | MR | Zbl

[12] Mezhennaya N. M., Mikhailov V. G., “On the distribution of the number of ones in the output sequence of the MCV-generator over GF(2)”, Matematicheskie Voprosy Kriptografii, 4:4 (2013), 95–107 (in Russian) | DOI

[13] Tyurin I. S., “An improvement of the residual in the Lyapunov theorem”, Theory Probab. Appl., 56:3 (2011), 693–696 | DOI | MR

[14] Mezhennaya N. M., “On distribution of number of ones in binary multicycle sequence”, Prikladnaya Diskretnaya Matematika, 2015, no. 1(27), 69–77 (in Russian)

[15] Mezhennaya N. M., Mikhailov V. G., “On the asymptotic normality of frequencies of values in the non-equiprobable multi-cyclic random sequence modulo 4”, Matematicheskie Voprosy Kriptografii, 7:4 (2016), 81–94 (in Russian) | DOI | MR

[16] Billingsley P., Convergence of Probability Measures, 2nd ed., Wiley, New-York, 1999, 296 pp. | MR | Zbl

[17] Janson S., “Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs”, Ann. Probab., 16:1 (1988), 305–312 | DOI | MR | Zbl

[18] Fikhtengol'ts G. M., Differential and Integral Calculus Course, v. 1, 8th ed., Fizmatlit Publ., M., 2003, 680 pp. (in Russian)

[19] Baldi P., Rinott Y., “On normal approximations of distributions in terms of dependency graphs”, Ann. Probab., 17:4 (1989), 1646–1650 | DOI | MR | Zbl