Autocorrelations of random binary sequences

Autocorrelations of random binary sequences Article

Mercer, ID. (2006). Autocorrelations of random binary sequences . Combinatorics Probability and Computing, 15(5), 663-671. 10.1017/S0963548306007589

We define ℬn to be the set of n-tuples of the form (a 0,...,an-1) where aj = ± 1. If A ∈ ℬ n then we call A a binary sequence and define the autocorrelations of A by ck:= Σj=0^n-k-1 ajaj+k for 0 ≤ k ≤ n - 1. The problem of finding binary sequences with autocorrelations 'near zero' has arisen in communications engineering and is also relevant to conjectures of Littlewood and Erdos on 'flat' polynomials with ±1 coefficients. Following Turyn, we define b(n):= min max |Ck|. A∈ℬn1≤k≤n-1 The purpose of this article is to show that, using some known techniques from discrete probability, we can improve upon the best upper bound on b(n) appearing in the previous literature, and we can obtain both asymptotic and exact expressions for the expected value of ck^m if the a j are independent ±1 random variables with mean 0. We also include some brief heuristic remarks in support of the unproved conjecture that b(n) = O(√n). © 2006 Cambridge University Press.