The classical Hoeffding's inequality bounds the tail probability $\Pr[ \sum a_i x_i > t]$, where $\{x_i\}$ are mean-zero random variables with $|x_i| \leq 1$, and $\{a_i\}$ are coefficients with $\sum a_i^2 = 1$. In the well-studied case where $\{x_i\}$ assume only the values $\{-1,1\}$, sharper bounds can be obtained, which show that the rate of decay of $\Pr[\sum a_i x_i > t]$ is very close to that of a Gaussian. We focus on `local' bounds of this type, which assert that the `relative' decay of such variables is also similar to that of a Gaussian. One example is the following inequality proved by Devroye and Lugosi (2008): Let $\{a_i\}, \{x_i\}$ be as above. If for some $t > 0$, we have $\Pr[\sum a_i x_i > t] = b$, then $\Pr[\sum a_i x_i > t + \delta] < b/2$ holds for $\delta < c/ \sqrt{\log(1/b)}$, where $c$ is a universal constant. Such inequalities seem to be little-known and probably can be useful in various contexts.
In this talk we develop new inequalities of this type. Then we use them to study analytic properties of linear threshold functions (LTFs) -- Boolean functions $f:\{-1,1\}^n \rightarrow \{0,1\}$ of the form $f(x) = 1 \{ \sum a_i x_i > t\}$, for some fixed coefficients $\{a_i\}$ and some threshold $t$, that play an important role in computer science and other fields. We determine the exact asymptotic order of the total influence and of the degree-1 Fourier weight of any biased LTF, in terms of its maximal (normalized) coefficient and its expectation. This provides a sharp generalization of theorems proved by Matulef, O'Donnell, Rubinfeld, and Servedio, and settles a conjecture posed by Kalai et al. As a corollary, we present a new large family of tightness examples for a well-known correlation inequality of Talagrand.
Joint work with Ohad Klein.