Two variants of Lempel – Ziv test for binary sequences

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.