Skip to content

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

2 phản hồi
  1. Ôi thật kỳ diệu, tất cả như nằm trong 1 bản nhạc tuyệt vời

  2. vote. It’s good. Thanks .

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Theo dõi

Get every new post delivered to your Inbox.

Join 245 other followers

%d bloggers like this: