The correlation measures of finite sequences: limiting distributions and minimum values (Q2826765)

The binary sequences are important objects which have many applications in different branches of science. The well-distribution measure, the normality measure and the \(r\)-th order correlation measure are quantitative characteristics for their pseudorandomness. Finite binary sequences for which these measures are small are considered to posses a high ``level of randomness''. Theses measures are studied in the presented paper. The main result here is that the correlation measure of order \(r\) for random binary sequences converges strongly and has a limiting distribution. Also, it is shown that the best known lower bound for the minimum values of the correlation measure are a simple consequence of a result due to \textit{L. R. Welch} [``Lower bounds on the maximum cross correlation of signals'', IEEE Trans. Inf. Theory IT-20, No. 3, 397--399 (1974)]. concerning the maximum nontrivial scalar product over a set of vectors.NEWLINENEWLINEIn the introduction of the paper, the concepts of three measures for the pseudorandomness for finite binary sequences, namely the well-distribution measure \(W(A_n),\) the normality measure \({\mathcal N}(A_n)\) and the \(r\)-th order correlation measure \(C_r(A_n)\) are presented. The problem for the existence of the limiting distributions \(\displaystyle \left\{ {W(A_n) \over \sqrt{n}}\right\}_{n \geq 1},\) \(\displaystyle \left\{ {{\mathcal N}(A_n)\over \sqrt{n}}\right\}_{n \geq 1}\) and \(\displaystyle \left\{ {C_r(A_n) \over \sqrt{n \log {n \choose r}}}\right\}_{n \geq 1}\) is formulated. Theorem 1.1 is the main result. Here, \((a_1, a_2, \ldots)\) is an arbitrary sequence of elements \(-1\) or 1, for each positive integer \(n\) \(A_n = ((a_1, a_2, \ldots, a_n)\) and \(r \geq 2\) is a fixed integer. The statement is that \(\displaystyle {C_r(A_n) \over \sqrt{n \log {n \choose r}}} \to 1\) almost surely as \(n \to \infty\).NEWLINENEWLINEIn Theorem 1.2, \(A_n\) is a drawn uniformly at random from \(\{-1, 1\}^n\) and \(\varepsilon > 0\). The statement is that as \(n \to \infty\) \(Pr[ C_r(A_n) \leq (1 + \varepsilon) \sqrt{2 n \log {n \choose r}}] \to 1,\) for all \(r\) satisfying \(2 \leq r \leq n.\) In view of Theorem 1.1, the bound in Theorem 1.2 is essentially best possible. Also, Theorem 1.2 gives the currently strongest existence result.NEWLINENEWLINEIn Theorem 1.3, it is proved that there exists a sequence of real number \(c_k,\) \(\displaystyle c_k > {1 \over 9}\) for each \(k \geq 3\) and \(\displaystyle c_k \to {1 \over \sqrt{6 e}}\) as \(k \to \infty,\) such that for all positive integers \(s\) and \(n\) with \(\displaystyle s \leq {n \over 3}\) the inequality \( \max\left\{ C_2(A_n), C_4(A_n), \ldots, C_{2s}(A_n)\right\} > c_n\sqrt{s n} \) holds for all \(A_n \in \{-1, 1\}^n.\)NEWLINENEWLINEIn Section 2, Theorem 1.2 is proved. In Section 3, several preliminary lemmas are presented. They are used to prove Theorem 1.1. This is made in Section 4. In Section 5 Theorem 1.3 is proved.