On the Littlewood‐Offord problem for arbitrary distributions

DOI10.1002/RSA.20977zbMATH Open1523.60027arXiv1912.08770OpenAlexW3095255213MaRDI QIDQ6073633FDOQ6073633

Authors: T. Juşkeviçius, Valentas Kurauskas 

Publication date: 11 October 2023

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: Let $X_1,ldots,X_n$ be independent identically distributed random vectors in $mathbb{R}^d$. We consider upper bounds on $ma{x}_{x}mathbbP(a_1{X}_1+cdots+a_n{X}_n=x)$ under various restrictions on $X_i$ and the weights $a_i$. When $mathbbP(X_i=pm1)=frac12$, 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 $ileqfracn2$ and $a_i=-1$ for $i>fracn2$, regardless of the distribution of $X_1$. 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 $su{p}_{x}mathbbP(X_i=x)leqalpha$, 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.

Full work available at URL: https://arxiv.org/abs/1912.08770

Recommendations

• Littlewood-Offord Inequalities for Random Variables
• Estimates for the concentration functions in the Littlewood-Offord problem
• A bound for the maximal probability in the Littlewood-Offord problem
• Arak's inequalities for concentration functions and the Littlewood-Offord problem
• Arak inequalities for concentration functions and the Littlewood-Offord problem
• On an extremal problem for probability distributions
• Erdős-Littlewood-Offord problem with arbitrary probabilities
• On Littlewood's estimate for the binomial distribution
• On the Littlewood-Offord problem

zbMATH Keywords

small ball probabilityLittlewood-Offord problemconcentration function

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
• Estimates for the concentration function of combinatorial number theory and probability
• An elementary proof of the local central limit theorem
• On Random Variables with Comparable Peakedness
• On extreme points of regular convex sets
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• On the Kolmogorov-Rogozin inequality for the concentration function
• On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
• Non-abelian Littlewood-Offord inequalities
• On a lemma of Littlewood and Offord
• Lower bounds for tails of sums of independent symmetric random variables
• Inequalities for Concentration Functions of Convolutions of Arithmetic Distributions and Distributions with Bounded Densities
• Estimation of the Maximum Probability for Sums of Lattice Random Variables
• Littlewood-Offord Inequalities for Random Variables
• Combinatorial anti-concentration inequalities, with applications
• Erdős-Littlewood-Offord problem with arbitrary probabilities
• Upper Estimates of Maximum Probability for Sums of Independent Random Vectors
• Optimal Littlewood-Offord inequalities in groups

Cited In (20)

• A sharp inverse Littlewood-Offord theorem
• Geometric and o-minimal Littlewood-Offord problems
• Resilience for the Littlewood-Offord problem
• Optimal inverse Littlewood-Offord theorems
• A new approach to an old problem of Erdős and Moser
• Erdős-Littlewood-Offord problem with arbitrary probabilities
• Bilinear and quadratic variants on the Littlewood-Offord problem
• Resilience for the Littlewood-Offord problem
• Solution of the Littlewood-Offord problem in high dimensions
• Bernoulli sums and Rényi entropy inequalities
• The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi
• Arak's inequalities for concentration functions and the Littlewood-Offord problem
• The Littlewood-Offord problem for Markov chains
• A bound for the maximal probability in the Littlewood-Offord problem
• A nonuniform Littlewood-Offord inequality for all norms
• Optimal Littlewood-Offord inequalities in groups
• A non-uniform Littlewood-Offord inequality
• Inverse Littlewood-Offord problems for quasi-norms
• On Littlewood's estimate for the binomial distribution
• Optimal probability inequalities for random walks related to problems in extremal combinatorics

This page was built for publication: On the Littlewood‐Offord problem for arbitrary distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6073633)