The peak sidelobe level of random binary sequences

LetA n = ( a 0 , a 1 , … , a n − 1 )be drawn uniformly at random from{ − 1 , + 1 } nand defineM ( A n ) = max 0 < u < n∑ j = 0 n − u − 1a j a j + uforn > 1.It is proved that M ( A n ) / n log nconverges in probability to 2 . This settles a problem first studied by Moon and Moser in the 1960s and proves in the affirmative a recent conjecture due to Alon, Litsyn, and Shpunt. It is also shown that the expectation of M ( A n ) / n log ntends to 2 .