Geodesic
Two Lempel – Ziv goodness-of-fit tests for nonequiprobable random binary sequences
Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 97-110 
V. I. Kruglov. Two Lempel – Ziv goodness-of-fit tests for nonequiprobable random binary sequences. Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 97-110. http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a5/
@article{MVK_2023_14_2_a5,
     author = {V. I. Kruglov},
     title = {Two {Lempel} {\textendash} {Ziv} goodness-of-fit tests for nonequiprobable random binary sequences},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {97--110},
     year = {2023},
     volume = {14},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a5/}
}
TY  - JOUR
AU  - V. I. Kruglov
TI  - Two Lempel – Ziv goodness-of-fit tests for nonequiprobable random binary sequences
JO  - Matematičeskie voprosy kriptografii
PY  - 2023
SP  - 97
EP  - 110
VL  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a5/
LA  - en
ID  - MVK_2023_14_2_a5
ER  - 
%0 Journal Article
%A V. I. Kruglov
%T Two Lempel – Ziv goodness-of-fit tests for nonequiprobable random binary sequences
%J Matematičeskie voprosy kriptografii
%D 2023
%P 97-110
%V 14
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a5/
%G en
%F MVK_2023_14_2_a5

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

Let the hypothesis $H_p$ mean that elements of the sequence $X_1,\ldots,X_n$ are independent and identically distributed: $\mathbf{P}\{X_i=1\}=p$, $\mathbf{P}\{X_i=0\}=1-p$, where $p\in(0,1)$. Earlier two goodness-of-fit tests for the hypothesis $H_{0.5}$ were proposed based on the possibility of exact computation of Lempel – Ziv statistics distributions. In this paper these tests are generalized for any $p\in(0,1)$. For each test a sequence of length $n=mrT$ is divided into blocks of length $T$, for these blocks Lempel – Ziv statistics $W_1(T),\ldots, W_{mr}(T)$ are computed. The first test for $r=2$ is based on the statistic $\tilde W(2mT)=(W_1+\ldots+W_m)-(W_{m+1}+\ldots+W_{2m})$, its distribution is symmetric about zero. The statistic of the second test is $\tilde \chi^2(mrT)=\max_{1\le k\le m} \chi_{(k)}^2(T)$, where $\chi_{(1)}^2(T),\ldots,\chi_{(m)}^2(T)$ are values of chi-square statistics computed for $(W_{1,1}(T),\ldots, W_{1,r}(T)),\ldots,(W_{m,1}(T), W_{m,2}(T), \ldots, W_{m,r}(T))$ correspondingly. For statistics of both tests limit distributions are found, for the statistic of the first test the rate of convergence to the limit normal distribution is given.

[1] Rukhin A. et al., A statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST Special Publication 800-22, 2000 | MR

[2] Rukhin A. et al., A statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST Special Publication 800-22, 2010

[3] Doganaksoy A., Gologlu F., “On Lempel – Ziv complexity of sequences”, SETA 2006, Lect. Notes Comput. Sci., 4086, 2006, 180–189 | DOI | MR | Zbl

[4] Mikhailov V.G., Kruglov V.I., “Two variants of Lempel – Ziv test for binary sequences”, Matematicheskie voprosy kriptografii, 13:3 (2022), 93–106 | DOI | MR | Zbl

[5] Mihailov V.G., “Formulae to calculate distributions of Lempel – Ziv statistic and relative statistics”, Obozrenie prikladnoi i promyshlennoi matematiki, 14:3 (2007), 461–473 (In Russian)

[6] Theory Probab. Appl., 56:4 (2011), 693–696 | DOI | DOI | MR

[7] Ivchenko G.I., Medvedev Y.I., Mathematical Statistics, High School, M., 1984 (In Russian) | MR