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
    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

    Identifiers