Resilience for the Littlewood-Offord Problem

Abstract

Consider the sum $X(\xi )={\sum }_{i=1}^n{a}_i{\xi }_i$, where $a=(a_i{)}_{i=1}^n$ is a sequence of non-zero reals and $\xi =({\xi }_i{)}_{i=1}^n$ is a sequence of i.i.d. Rademacher random variables (that is, $\mathrm{Pr}[{\xi }_i=1]=\mathrm{Pr}[{\xi }_i=-1]=1/2$). The classical Littlewood-Offord problem asks for the best possible upper bound on the concentration probabilities $\mathrm{Pr}[X=x]$. In this paper we study a resilience version of the Littlewood-Offord problem: how many of the ${\xi }_i$ is an adversary typically allowed to change without being able to force concentration on a particular value? We solve this problem asymptotically, and present a few interesting open problems.

This version addresses referee's comments