TY - JOUR

T1 - Measures of pseudorandomness for finite sequences

T2 - Typical values

AU - Alon, N.

AU - Kohayakawa, Y.

AU - Mauduit, C.

AU - Moreira, C. G.

AU - Rödl, V.

N1 - Funding Information:
Part of this work was done at IMPA, whose hospitality the authors gratefully acknowledge. This research was partially supported by IM-AGIMB/IMPA. The first author was partially supported by the Israel Science Foundation, by a USA–Israeli BSF grant, by NSF grant CCR-0324906, by the James Wolfensohn fund and by the State of New Jersey. The second author was partially supported by FAPESP and CNPq through a Temático– ProNEx project (Proc. FAPESP 2003/09925–5) and by CNPq (Proc. 306334/2004–6 and 479882/2004–5). The third author was partially supported by the Brazil/France Agreement in Mathematics (Proc. CNPq 60-0014/01-5 and 69-0140/03-7). The fourth author was partially supported by MCT/CNPq through a ProNEx project (Proc. CNPq 662416/1996–1) and by CNPq (Proc. 300647/95–6). The fifth author was partially supported by NSF Grant DMS 0300529. The authors gratefully acknowledge the support of a CNPq/NSF cooperative grant (910064/99–7, 0072064).

PY - 2007/11

Y1 - 2007/11

N2 - Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences EN ∈ [-1, 1]N in order to measure their 'level of randomness'. Those parameters, the normality measure (EN), the well-distribution measure W(EN), and the correlation measure Ck(EN) of order k, focus on different combinatorial aspects of EN. In their work, amongst others, Mauduit and Sárközy (i) investigated the relationship among those parameters and their minimal possible value, (ii) estimated (EN), W(EN) and Ck(EN) for certain explicitly constructed sequences EN suggested to have a 'pseudorandom nature', and (iii) investigated the value of those parameters for genuinely random sequences en.In this paper, we continue the work in the direction of (iii) above and determine the order of magnitude of (E N), W(EN) and Ck(EN) for typical EN. We prove that, for most EN ∈ [-1, 1]N, both W(EN) and (EN) are of order √ N, while C k(EN) is of order Nlog(Nk) for any givEN 2 ≤ k ≤ N/4.

AB - Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences EN ∈ [-1, 1]N in order to measure their 'level of randomness'. Those parameters, the normality measure (EN), the well-distribution measure W(EN), and the correlation measure Ck(EN) of order k, focus on different combinatorial aspects of EN. In their work, amongst others, Mauduit and Sárközy (i) investigated the relationship among those parameters and their minimal possible value, (ii) estimated (EN), W(EN) and Ck(EN) for certain explicitly constructed sequences EN suggested to have a 'pseudorandom nature', and (iii) investigated the value of those parameters for genuinely random sequences en.In this paper, we continue the work in the direction of (iii) above and determine the order of magnitude of (E N), W(EN) and Ck(EN) for typical EN. We prove that, for most EN ∈ [-1, 1]N, both W(EN) and (EN) are of order √ N, while C k(EN) is of order Nlog(Nk) for any givEN 2 ≤ k ≤ N/4.

UR - http://www.scopus.com/inward/record.url?scp=39749200182&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=39749200182&partnerID=8YFLogxK

U2 - 10.1112/plms/pdm027

DO - 10.1112/plms/pdm027

M3 - Article

AN - SCOPUS:39749200182

VL - 95

SP - 778

EP - 812

JO - Proceedings of the London Mathematical Society

JF - Proceedings of the London Mathematical Society

SN - 0024-6115

IS - 3

ER -