Measures of pseudorandomness for finite sequences: typical values

Mauduit and Sárközy introduced and studied certainnumerical parameters associated to finite binary sequences E_N {–1, 1}^N in order to measure their ‘level of randomness’.Those parameters, the normality measure (E_N), the well-distributionmeasure W(E_N), and the correlation measure C_k(E_N) of order k,focus on different combinatorial aspects of E_N. In their work,amongst others, Mauduit and Sárközy (i) investigatedthe relationship among those parameters and their minimal possiblevalue, (ii) estimated (E_N), W(E_N) and C_k(E_N) for certain explicitlyconstructed sequences E_N suggested to have a ‘pseudorandomnature’, and (iii) investigated the value of those parametersfor genuinely random sequences E_N. In this paper, we continue the work in the direction of (iii)above and determine the order of magnitude of (E_N), W(E_N) andC_k(E_N) for typical E_N. We prove that, for most E_N {–1,1}^N, both W(E_N) and (E_N) are of order N, while C_k(E_N) is oforder for any given 2 k N/4.