Erdos-Littlewood-Offord problem with arbitrary probabilities

Abstract

The classical Erdős-Littlewood-Offord problem concerns the random variable $X=a_1{\xi }_1+\cdots +a_n{\xi }_n$, where $a_i\in \mathbb{R}\setminus \{0\}$ are fixed and ${\xi }_i\sim \text{Ber}(1/2)$ are independent. The Erdős-Littlewood-Offord theorem states that the maximum possible concentration probability ${\max }_{x\in \mathbb{R}}\mathrm{Pr}(X=x)$ is $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)/2^n$, achieved when the $a_i$ are all $1$. As proposed by Fox, Kwan, and Sauermann, we investigate the general case where ${\xi }_i\sim \text{Ber}(p)$ instead. Using purely combinatorial techniques, we show that the exact maximum concentration probability is achieved when $a_i\in \{-1,1\}$ for each $i$. Then, using Fourier-analytic techniques, we investigate the optimal ratio of $1$s to $-1$s. Surprisingly, we find that in some cases, the numbers of $1$s and $-1$s can be far from equal.