Alon, N.; Kohayakawa, Y.; Mauduit, C.; Moreira, C. G.; Rödl, V. Measures of pseudorandomness for finite sequences: typical values. (English) Zbl 1124.68084 Proc. Lond. Math. Soc. (3) 95, No. 3, 778-812 (2007). Summary: C. Mauduit and A. Sárközy [Acta Arith. 82, No. 4, 365–377 (1997; Zbl 0886.11048)] introduced and studied certain numerical parameters associated to finite binary sequences \(E_N \in \{-1, 1\}^N\) in order to measure their ‘level of randomness’. Those parameters, the normality measure \(\mathcal N(E_N)\), the well-distribution measure \(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) investigated the relationship among those parameters and their minimal possible value, (ii) estimated \(\mathcal N(E_N)\), \(W(E_N)\) and \(C_k(E_N)\) for certain explicitly constructed sequences \(E_N\) suggested to have a ‘pseudorandom nature’, and (iii) investigated the value of those parameters for 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 \(\mathcal N(E_N)\), \(W(E_N)\) and \(C_k(E_N)\) for typical \(E_N\). We prove that, for most \(E_N \in \{-1, 1\}^N\), both \(W(E_N)\) and \(\mathcal N(E_N)\) are of order \(\sqrt N\), while \(C_k(E_N)\) is of order \(\sqrt{N\log \binom{N}{k}}\) for any given \(2 \leq k \leq N/4\). Cited in 1 ReviewCited in 34 Documents MSC: 11K45 Pseudo-random numbers; Monte Carlo methods 11K38 Irregularities of distribution, discrepancy 68R15 Combinatorics on words 68R05 Combinatorics in computer science Keywords:normality measure; well-distribution measure; correlation measure Citations:Zbl 0886.11048 PDFBibTeX XMLCite \textit{N. Alon} et al., Proc. Lond. Math. Soc. (3) 95, No. 3, 778--812 (2007; Zbl 1124.68084) Full Text: DOI