A Sharp Inverse Littlewood-Offord Theorem
Let eta(i), i = 1 ,..., n be iid Bernoulli random variables. Given a multiset v of n numbers v(1) ,..., v(n), the concentration probability P(1)(v) of v is defined as P(1)(v) := sup(x) P(v(1)eta(1)+ ... v(n)eta(n) = x). A classical result of Littlewood-Offord and Erdos from the 1940s asserts that if the v(i) are nonzero, then this probability is at most O(n(-1/2)). Since then, many researchers obtained better bounds by assuming various restrictions on v. In this article, we give an asymptotically optimal characterization for all multisets v having large concentration probability. This allow us to strengthen or recover several previous results in a straightforward manner. (C) 2010 Wiley Periodicals, Inc. Random Struct. Alg., 37, 525-539, 2010
concentration probability littlewood-offord problem inverse theorems random walks additive combinatorics