N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira and V. Rödl

Mauduit and Sárközy 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{N \choose k}}$ for any given $2 \leq k \leq N/4$.

2000 Mathematics Subject Classification: 68R15.

E-mail:
noga@math.tau.ac.il
yoshi@ime.usp.br
mauduit@iml.univ-mrs.fr
gugu@impa.br
rodl@mathcs.emory.edu