×

Measures of pseudorandomness for finite sequences: typical values. (English) Zbl 1124.68084

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\).

MSC:

11K45 Pseudo-random numbers; Monte Carlo methods
11K38 Irregularities of distribution, discrepancy
68R15 Combinatorics on words
68R05 Combinatorics in computer science

Citations:

Zbl 0886.11048
PDFBibTeX XMLCite
Full Text: DOI