On the typical values of the cross-correlation measure (Q284078)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the typical values of the cross-correlation measure |
scientific article |
Statements
On the typical values of the cross-correlation measure (English)
0 references
17 May 2016
0 references
\textit{K Gyarmati}, \textit{C. Mauduit} and \textit{A. Sárközy} [``The cross-correlation measure for families of binary sequences''. In: Applied Algebra and Number Theory, pp. 126--143. Cambridge: Cambridge Univ. Press (2014)] introduced the \(k\)-th order the cross-correlation measure \(\Phi_{k}\) for measuring randomness of binary sequences. In the present article it is shown that for given \(\varepsilon>0\) ``random'' families \(\mathcal{F}\) of ``small'' size \(|\mathcal{F}|\), with probability \(1-\varepsilon\) satisfy \[ \Phi_{k}(\mathcal{F})\asymp\sqrt{N\log{N\choose k}+k|\mathcal{F}|}. \] The typical value of \(\Phi_{k}(\mathcal{F})\) strongly depends on the size of the family \(\mathcal{F}\). The given bound holds provided that \(\mid\mathcal{F}\mid< 2 ^{N/12}\), where \(N\) is the length of the sequence.
0 references
pseudorandom sequence
0 references
binary sequence
0 references
correlation measure
0 references
cross-correlation measure
0 references
0 references