Bounds on the concentration function in terms of Diophantine approximation

Introduction

The P. Lévy concentration function of a random variable $S$ is defined as

Since the work of Lévy, Littlewood–Offord, Erdős, Esseen, Kolmogorov and others, numerous results in probability theory concern upper bounds on the concentration function of the sum of independent random variables; a particularly powerful approach was introduced in the 1970-s by Halász .

This note was motivated by the recent work of Rudelson and Vershynin . Let $X$ be a random variable; let $X_{1},\cdots,X_{n}$ be independent copies of $X$, and let ${\bf a}=(a_{1},\cdots,a_{n})$ be an $n$-tuple of real numbers.

In the Gaussian case $X\sim N(0,1)$, we have: $\sum_{k=1}^{n}a_{k}X_{k}\sim N(0,|{\bf a}|^{2})$ (where $|\cdot|$ stands for Euclidean norm), and consequently

Rudelson and Vershynin gave a bound in terms of Diophantine approximation of the vector ${\bf a}$. Their approach makes use of a deep measure-theoretic lemma from . Our goal is to show a simpler analytic method that may be of use in such problems. The following theorem is a (slightly improved) version of [4, Theorem 1.3].

Of course, Theorem 1.1 follows formally from Theorem 1.2. For simplicity of exposition we will prove Theorem 1.1 and indicate the adjustments that are necessary for $d>1$.

Proof of Theorem 1.1

Step 1: By Chebyshev’s inequality and the identity

Now we can swap the expectation with the integral and take absolute value:

Step 2 (this step is analogous to [2, §3] and [4, 4.2]): First,

Let $X^{\prime}$ be an independent copy of $X$, ${X}^{\#}=X-X^{\prime}$. Observe that

Replace the conditional expectation with supremum over the possible values $z\geq 2$ of $|{X}^{\#}|$ and recall that

Then the last integral in (8) can be split into

Therefore by (3) either $|\eta^{\prime}-\eta^{\prime\prime}|<1/(2\|a\|_{\infty})$ or $|\eta^{\prime}-\eta^{\prime\prime}|>D$. In other words, $B\subset\bigcup_{j}B_{j}$, where $B_{j}$ are intervals of length $\leq 1/\|a\|_{\infty}$ such that any two points belonging to different $B_{j}$ are at least $D$-apart.

Step 4: For every $j$ there exists $\eta_{j}\in B_{j}$ such that

The length of the interval $a_{k}B_{j}$ is $\leq 1$; hence $m_{k}$ (which is the closest integer to $\eta a_{k}$) can obtain at most 2 values while $\eta\in B_{j}$. Therefore every one of the integrals on the right-hand side of (11) is bounded by

Now, $B_{j}$ (and hence $\eta_{j}$) are $D$-separated; therefore

combining this with (7–10) we deduce (4).

Remarks

The results can be also used to estimate the formally more general form of the Lévy concentration function:

Indeed, $\mathcal{L}(\sum_{k=1}^{n}X_{k}\overrightarrow{a}_{k};\varepsilon)=\mathcal{Q}(\sum_{k=1}^{n}X_{k}\overrightarrow{a}_{k}/\varepsilon)$, so one can just apply the theorems to $\overrightarrow{a}_{k}^{\prime}=\overrightarrow{a}_{k}/\varepsilon$.

By similar reasoning, the assumption $\mathcal{Q}(X)\leq 1-p$ can be replaced with $\mathcal{Q}(KX)\leq 1-p$ (for an arbitrary $K>0$); this will only influence the values of the constants in (4), (6).

The proof of Theorem 1.2 is parallel to that of Theorem 1.1. The main difference appears in Step 4, where instead of Hölder’s inequality one should use the Brascamp–Lieb–Luttinger rearrangement inequality . (Note that a different rearrangement inequality was applied to a similar problem by Howard ).

Acknowledgements

We are grateful to our supervisor Vitali Milman for his support and for encouraging to write this note. We thank Mark Rudelson and Roman Vershynin for stimulating discussions, and in particular for suggesting the current formulation of Theorem 1.2 with improved dependence on the dimension $d$, and for spotting several blunders.

References