The correlation measures of finite sequences: limiting distributions and\n minimum values

2014/04/01 by Kai‐Uwe Schmidt, Schmidt, Kai-Uwe
Computer Science · #Coding theory and cryptography

paper · pdf · doi:10.48550/arxiv.1404.0172

Abstract

Three measures of pseudorandomness of finite binary sequences were introduced\nby Mauduit and S 'ark "ozy in 1997 and have been studied extensively since\nthen: the normality measure, the well-distribution measure, and the correlation\nmeasure of order r. Our main result is that the correlation measure of order r\nfor random binary sequences converges strongly, and so has a limiting\ndistribution. This solves a problem due to Alon, Kohayakawa, Mauduit, Moreira,\nand R "odl. We also show that the best known lower bounds for the minimum\nvalues of the correlation measures are simple consequences of a celebrated\nresult due to Welch, concerning the maximum nontrivial scalar products over a\nset of vectors.\n

Related

• The cross-correlation measure of families of finite binary sequences:\n limiting distributions and minimal values
• On Finite Pseudorandom Binary Sequences: Functions from a Hardy field
• Correlation, Linear Complexity, Maximum order Complexity on Families of binary Sequences
• On the pseudorandomness of Parry--Bertrand automatic sequences
• Maximum-order Complexity and Correlation Measures