Optimal Probability Inequalities for Random Walks related to Problems in Extremal Combinatorics

Let S_n=X_1+…+X_n be a sum of independent symmetric random variables such that |X_{i}|\leq 1. Denote by W_n=\epsilon_{1}+…+\epsilon_{n} a sum of independent random variables such that \prob{\eps_i = \pm 1} = 1/2. We prove that $\mathbb{P}${S_{n} \in A} \leq $\mathbb{P}${cW_k \in A}, where A is either an interval of the form [x, \infty) or just a single point. The inequality is exact and the optimal values of c and k are given explicitly. It improves Kwapie'n’s inequality in the case of the Rademacher series. We also provide a new and very short proof of the Littlewood-Offord problem without using Sperner’s Theorem. Finally, an extension to odd Lipschitz functions is given.