Small ball probability and Inverse Littlewood-Offord theorems

Tháng Một 2, 2013

Happy New Year everybody !!

Hoi Nguyen and I just finished a survey on the above topic (to appear in the Erdos centennial proceeding). I try to give a brief overview here. Small probability (or anti-concentration) is a classical topic in probability which has currently been revived thanks to applications for various fields of mathematics. For the whole paper, which can be read without too much knowledge in probability, follow this link or this link.

Let $\xi$ be a real random variable with mean zero and variance one
and $A=\{a_1,\dots,a_n\}$ be a multi-set in $R$ (here $n \rightarrow \infty$ ). The random sum $S_A := a_1 \xi_1 + \dots + a_n \xi_n$ where $\xi_i$ are iid copies of $\xi$ plays an essential role in probability. The Central Limit Theorem, arguably the most important theorem in the field, asserts that if the $a_i$ ‘s are the same, then the distribution of $S_A/\sqrt { \sum_{i=1}^n |a_i| ^2 }$ tends to the normal distribution $N(0,1) .$

Furthermore, Berry-Esseen theorem shows that if $\xi$ has bounded third moment, then the rate of convergence is $O(n^{-1/2} )$ .
This, in particular, implies that for any small open interval I, the probability $Pr ( S_A \in I )$ is of order $O(|I| / n^{1/2} ).$

The assumption that the coefficients are the same is, of course, not essential. Typically, it suffices to assume that none of the $a_i$ are dominating.

The probability $Pr ( S_A \in I)$ (and its high dimensional generalization) will be referred to as small ball probability. In 1943, Littlewood and Offord, in connection with their studies of random polynomials, raised the problem of estimating the small probability for arbitrary coefficients $a_i$ . This is called the Littlewood-Offord problem. Notice that when we do not assume anything about the coefficients, even the Central Limit Theorem may fail, so Berry-Esseen type bounds no longer apply.

Quite remarkably, Littlewood and Offord managed to show

Theorem 1. If $\xi$ is Bernoulli (taking values $\pm 1$ with probability $1/2$ ) and $a_i$ have absolute value at least 1, then for any open interval $I$ of length 2, $P (S_A \in I) = O( \frac{\log n}{n^{1/2}} ).$

Shortly after, Erdos gave an improvement, improving the right hand side to (exactly) $B_n/2^n$ , where $B_n$ is the largest binomial coefficient. As far as the order of magnitude is concerned, this (via Sterling formula) imporved Littlewood-Offord bound by the log factor.

Erdos’proof made an ingenious use of Sperner’s lemma, which asserts that if F is an anti-chain on a set of $n$ elements, then it has at most $B_n$ elements (an anti-chain is a family of subsets none of which contains the other; it is clear that the collection of subsets of the same size form an anti-chain; thus, Sperner’s bound is sharp). Let $x$ be a fixed number. By reversing the sign of $a_i$ if necessary, one can assume that $a_i\ge 1$ for all i. Now let F be the collection of all subsets X of the index set $\{1,2 \dots, n\}$ such that

$\sum_{i\in X} a_i - \sum_{j \in \bar{X}}a_j \in (x-1,x+1).$

One can easily verify that F is an anti-chain. Hence, by Sperner’s lemma,

$|F| \le \frac{B_n}{2^n},$ completing the proof.

To see that the bound is sharp, consider $n$ even, then $Pr (S=0) = \frac{\binom{n}{n/2}}{2^n}$ . The problem was also studied in probability by Kolmogorov, Rogozin, Esseen, Kesten, and many others. In particular, one can define the concentration function $f(t):= \sup_{I, |I|= t} Pr (S_A \in I)$ and study the behavior of this function.

Erdos’ result is popular in the combinatorics community and has became the starting point for a whole theory. For instance, there are extensions/refinements in several directions. For instance, one can

(1) Consider high dimensional settings.

(2) Consider the original (or the high dimensional) problem with additional assumption on the set $A$ (for instance, what happens if the elements of $A$ are well separated).

(3) Replace the linear function $\sum_i a_i \xi_i$ by a higher degree polynomial.

There has been lots of studies in these directions in the last 40 years or so, including deep and beautiful results of Kleitman, Halasz, Stanley, Sarkozy-Szemeredi, Frankl-Furedi, and many others, using very different methods. We discussed these results in the paper, along with few applications, and refer to them as forward theorems. These form the first part of the survey.

The second (middle part) focuses on the inverse phenomenon, which Terry Tao and I proposed about 6 years ago. We tried to find the underlying reason as to why the small ball probability is large (say, polynomial in $n$ ).

It is easier and more natural to work with the discrete version. Let $A$ be a multi-set of integers and $\xi$ be the Bernoulli random variable.

Question.
Let $n \rightarrow \infty$ . Assume that for some constant $C$ , $\rho_A = \sup_x Pr (S_A =x ) \ge n^{-C}.$ What can we say about the elements $a_1,\dots,a_n$ of $A$ ?

Denote by $M$ the sum of all elements of $A$ and rewrite $\sum_{i} a_i \xi_i$ as $M -2 \sum_{i; \xi_i =-1} a_i$ . As $A$ has $2^n$ subsets, the bound $\rho_A \ge n^{-C}$ implies that at least $2^n /n^C$ among the subset sums are exactly $(M-x)/2$ . This overwhelming collision suggests that A must have some strong additive structure. One can easily see, for instance, that an arithmetic progression satisfies this property.

Tao and I proposed

Inverse Principle. A set with large small ball probability must have strong additive structure.

As a matter of fact, we managed to show that most elements of $A$ belong to the Minkowsky sum of few arithmetic progressions (such a sum is refer to as a generalized arithmetic progression in the literature; see this paper and this link for more details). This result was strongly motivated by the famous Freiman Inverse theorem in Additive Combinatorics.

Since then, many more inverse theorems concerning small ball probability have been found, thanks to works of Rudelson-Vershynin, Friedland -Sodin, and Hoi and myself. We discussed these results in details, along with some proofs. (In one of the latest proofs, we managed to use Freiman theorem directly as a lemma, so the connection seems even stronger).

The third part of the survey contains an array of applications:

(1) Applying Inverse theorems to prove Forward theorems. (Several forward theorems followed easily from the inverse ones; some old conjecture, such as one by Frank and Furedi can also be proved using the Inverse approach.)

(2) Strong bounds on the singularity probability of random Bernoulli matrices by Tao et. al. (unsymmetric case) and Hoi Nguyen and Vershyin (symmetric case).

(3) Tail distribution of the least singular value of random matrix (by Rudelson, Tao et.al. Rudelson-Vershynin, Hoi Nguyen). Partial solution to a conjecture of Spielman and Teng. We do not discuss the connection to the proof of the Circular Law conjecture, but interested reader can check this link or this link or this link for more information.

(4) Random polynomials (by Kozma-Zeitnouni).

(5) Applications in the theory of Boolean circuits (Razborov-Viola).

About these ads

From → Khoa hoc