On the Littlewood‐Offord problem for arbitrary distributions. Issue 2 (3rd November 2020)

• Record Type: Journal Article
• Authors: Juškevičius, Tomas; Kurauskas, Valentas
• Is Part Of: Random structures & algorithms. Volume 58:Issue 2(2021)
• Page Start: 370
• Page End: 380
• Publication Date: 2020-11-03
• Subjects: concentration function -- Littlewood‐Offord problem -- small ball probability; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20977
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Let X 1, … , X n be independent identically distributed discrete random vectors in R d . We consider upper bounds on sup x P ( a 1 X 1 + … + a n X n = x ) under various restrictions on X i and weights a i . When P ( X i = ± 1 ) = 1 2, this corresponds to the classical Littlewood‐Offord problem. We prove that in general for identically distributed random vectors and even values of n the optimal choice for ( a i ) is a i = 1 for i ≤ n 2 and a i = −1 for i > n 2, regardless of the distribution of X 1 . Applying these results to Bernoulli random variables answers a recent question of Fox et al. Finally, we provide sharp bounds for concentration probabilities of sums of random vectors under the condition sup x P ( X i = x ) ≤ α, where it turns out that the worst case scenario is provided by distributions on an arithmetic progression that are in some sense as close to the uniform distribution as possible. Unlike much of the literature on the subject we use neither methods of harmonic analysis nor those from extremal combinatorics.