Geodesic
Two variants of Lempel – Ziv test for binary sequences
Matematičeskie voprosy kriptografii, Tome 13 (2022) no. 3, pp. 93-106 
V. G. Mikhailov; V. I. Kruglov. Two variants of Lempel – Ziv test for binary sequences. Matematičeskie voprosy kriptografii, Tome 13 (2022) no. 3, pp. 93-106. http://geodesic.mathdoc.fr/item/MVK_2022_13_3_a5/
@article{MVK_2022_13_3_a5,
     author = {V. G. Mikhailov and V. I. Kruglov},
     title = {Two variants of {Lempel} {\textendash} {Ziv} test for binary sequences},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {93--106},
     year = {2022},
     volume = {13},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2022_13_3_a5/}
}
TY  - JOUR
AU  - V. G. Mikhailov
AU  - V. I. Kruglov
TI  - Two variants of Lempel – Ziv test for binary sequences
JO  - Matematičeskie voprosy kriptografii
PY  - 2022
SP  - 93
EP  - 106
VL  - 13
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MVK_2022_13_3_a5/
LA  - en
ID  - MVK_2022_13_3_a5
ER  - 
%0 Journal Article
%A V. G. Mikhailov
%A V. I. Kruglov
%T Two variants of Lempel – Ziv test for binary sequences
%J Matematičeskie voprosy kriptografii
%D 2022
%P 93-106
%V 13
%N 3
%U http://geodesic.mathdoc.fr/item/MVK_2022_13_3_a5/
%G en
%F MVK_2022_13_3_a5

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

Let according to hypothesis $H_0$ the elements of sequence $X_1,\ldots,X_n$ are independent random variables and have equiprobable distribution on the set $\{0,1\}$. We propose two goodness-of-fit tests for the hypothesis $H_0$ based on the Lempel – Ziv statistic $W(T)$ computed for blocks of length $T$. For the first test a sequence of length $n=2mT$ is divided into $2m$ blocks of length $T$, for these blocks values $W_1(T),\ldots, W_{2m}(T)$ of Lempel – Ziv statistic are computed. The first test is based on the statistic $\tilde W(2mT)=\sum_{k=1}^m W_k(T)-\sum_{k=m+1}^{2m}W_k(T)$, its distribution under $H_0$ is symmetric about zero. For the second test a sequence of length $n=mrT$ is divided into $mr$ blocks of length $T$. For these blocks values $W_{i,j}(T)$ ($i=\in\{1,\ldots,m\}, j\in\{1,\ldots,r\}$) of Lempel – Ziv statistic are computed. The second test is based on the value $\tilde \chi^2(mrT)=\max_{1\le k\le m} \chi_k^2(rT)$, where $\chi_k^2(rT)$ is a chi-square statistic corresponding to $W_{k,1}(T),\ldots, W_{k,r}(T).$ For both tests we find limit distributions of statistics, and for the first test we also give an estimate of the rate of convergence to the limit normal distribution. Formulas for the computation of distribution of $W(T)$ are described.

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

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

[3] Blum L., Blum M., Shub M., “A simple unpredictable pseudo-random number generator”, SIAM J. Computing, 15:2 (1986), 364–383 | DOI | MR

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

[5] Tyurin I.S., “An improvement of the residual in the Lyapunov theorem”, Teor. Veroyatn. Primen., 56:4 (2011), 808–811 | DOI | MR

[6] Ivchenko G.I., Medvedev Y.I., Mathematical Statistics, Vysshaya Shkola, M., 1984 (In Russian) | MR

[7] Knuth D.E., Iskusstvo programmirovaniya, v. 3, Sortirovka i poisk, Vtoroe izdanie, Izd. dom “Williams”, M.–St.Petersburg–Kiev, 2000, 828 pp. (In Russian) | MR

[8] Mikhailov V.G., “Formulae to calculate distributions of Lempel – Ziv statistic and related statistics”, Obozr. prikl. i promyshl. matem., 14:3 (2007), 461–473