Measures of pseudorandomness for finite sequences: typical values.

Abstract: Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences <italic>E</italic><italic>N</italic> ∈ {−1, 1}<italic>N</italic> in order to measure their ‘level of randomness’. Those parameters, the <italic>normality measure</italic><italic>N</italic>(<italic>E</italic><italic>N</italic>), the <italic>well‐distribution measure W</italic>(<italic>E</italic><italic>N</italic>), and the <italic>correlation measure</italic><italic>C</italic><italic>k</italic>(<italic>E</italic><italic>N</italic>) of order <italic>k</italic>, focus on different combinatorial aspects of <italic>E</italic><italic>N</italic>. In their work, amongst others, Mauduit and Sárközy (i) investigated the relationship among those parameters and their minimal possible value, (ii) estimated <italic>N</italic>(<italic>E</italic><italic>N</italic>), <italic>W</italic>(<italic>E</italic><italic>N</italic>) and <italic>C</italic><italic>k</italic>(<italic>E</italic><italic>N</italic>) for certain explicitly constructed sequences <italic>E</italic><italic>N</italic> suggested to have a ‘pseudorandom nature’, and (iii) investigated the value of those parameters for genuinely random sequences <italic>E</italic><italic>N</italic>. In this paper, we continue the work in the direction of (iii) above and determine the order of magnitude of <italic>N</italic>(<italic>E</italic><italic>N</italic>), <italic>W</italic>(<italic>E</italic><italic>N</italic>) and <italic>C</italic><italic>k</italic>(<italic>E</italic><italic>N</italic>) for typical <italic>E</italic><italic>N</italic>. We prove that, for most <italic>E</italic><italic>N</italic> ∈ {−1, 1}<italic>N</italic>, both <italic>W</italic>(<italic>E</italic><italic>N</italic>) and <italic>N</italic>(<italic>E</italic><italic>N</italic>) are of order √ <italic>N</italic>, while <italic>C</italic><italic>k</italic>(<italic>E</italic><italic>N</italic>) is of order N log ( N k ) for any given 2 ⩽ <italic>k</italic> ⩽ <italic>N</italic>/4. [ABSTRACT FROM AUTHOR]