On Littlewood-Offord theory for arbitrary distributions

2019/12/18 by Tomas Juškevičius, Juškevičius, Tomas, Valentas Kurauskas +1
Mathematics · #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.1912.08770

openalex publication_date 2019/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let X₁,…,X_n be independent identically distributed random vectors in ℝ^d. We consider upper bounds on max_x ℙ(a₁X₁+⋯+a_nX_n=x) under various restrictions on X_i and the weights a_i. When ℙ(X_i=± 1) = \frac 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 > \frac n 2, regardless of the distribution of X₁. Applying these results for Bernoulli random variables answers a recent question of Fox, Kwan and Sauermann. Finally, we provide sharp bounds for concentration probabilities of sums of random vectors under the condition sup_xℙ(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. An important feature of this work is that unlike much of the literature on the subject we use neither methods of harmonic analysis nor those from extremal combinatorics.

Related

• A non-uniform Littlewood-Offord inequality
• Erdos-Littlewood-Offord problem with arbitrary probabilities
• A nonuniform Littlewood-Offord inequality for all norms
• A sharp inverse Littlewood-Offord theorem
• Improved applications of Arak's inequalities to the Littlewood-Offord problem