7
$\begingroup$

Let $\epsilon <1/2$. Let $X$ be a random variable in $\mathbb Z$ such that $\mathbb P (X=x)\le \epsilon $ for any $x\in \mathbb Z$ (you may add any moment or regularity conditions on $X$ if needed). Let $S_n$ be a sum of $n$ independent copies of $X$. Show that for any $x\in \mathbb Z$ $$\mathbb P (S_n=x) \le C\cdot \epsilon \cdot n^{-1/2}$$ for some universal constant $C$.

I'm also looking for high dimensional generalizations of this claim in which the factor $n^{-1/2}$ is replaced with $n^{-d/2}$ where $d$ is the dimension (I'm thinking of $d$ as fixed). Clearly, for such a statement to hold we need an assumption saying that $X$ is "truly $d$ dimensional". I wonder if the following statement is correct:

Let $M$ large and let $X$ be a random variable in $\mathbb Z ^d$ such that $\mathbb P (X=x)\le M^{-d/2}$ for any $x\in \mathbb Z ^d$ and $\mathbb P(X\cdot v=y) \le 1/M$ for any vector $v\in \mathbb R ^d$ and $y>0$. Then, for any $x\in \mathbb Z ^d$ we have $$\mathbb P (S_n=x) \le C_d (Mn)^{-d/2}$$ for some constant $C_d$ depending only on $d$.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Your condition on $\epsilon$ implies that the variance is $\epsilon^2$ or more. The conclusion then is standard - for example from versions of the local CLT (google it to find references, a classical is Petrov's book, but the upper bound requires essentially no conditions). The multi-d case is similar - just condition on the number of steps in each direction. $\endgroup$
    – ofer zeitouni
    Jul 31, 2022 at 13:15
  • $\begingroup$ From the condition it follows that the variance is at least $1/\epsilon ^2$. Note that this bound on the variance alone is not enough to get the bound in the question (because we can take a random variable that is equal $1/\epsilon $ with probability $1/2$ and $-1/\epsilon $ with probability $1/2$. The local bound on the probability in this case will be $Cn^{-1/2}$ and not $C\epsilon n^{-1/2}$.) $\endgroup$
    – Dor
    Jul 31, 2022 at 13:26
  • 2
    $\begingroup$ Indeed, $1/\epsilon^2$ and not $\epsilon^2$, sorry for the typo. Now, with the variable you take, the local CLT gives a bound (for $n$ large enough) which is as you wanted, that is for $n$ large the bound is $C\epsilon/\sqrt{n}$. Did you mean a bound valid for all $n$? In that case, what I wrote is irrelevant, although the uniform upper bound can be fed into the Fourier proof of the LCLT to yield what you wanted. $\endgroup$
    – ofer zeitouni
    Jul 31, 2022 at 13:58
  • 1
    $\begingroup$ Note that in the example that Dor gave in this comment, we have $P(S_n=0)=\Omega(1/\sqrt n)$, regardless on how large the variance of $X$ is. $\endgroup$
    – Ron P
    Jul 31, 2022 at 14:09
  • 1
    $\begingroup$ Yes, I wanted to get the bound $C\epsilon n^{-1/2}$ for all $n$ and $\epsilon $. In my case $\epsilon $ can be small depending on $n$. I will try to do it with Fourier. It looks like one needs to bound the number of places in which the Fourier series is close to $1$ $\endgroup$
    – Dor
    Jul 31, 2022 at 14:35

1 Answer 1

Reset to default
4
$\begingroup$

For the one dimensional case, a quite nice bound is in Theorem 4.2 of [1]. See also [2]. The dependence on $\epsilon$ that you seek was first shown by Kesten[3].

The combinatorial approach was revived in [4]. The sharpest result is quite recent, see [5], which also identifies the worst case. Look there first.

[1] Esseen, Carl-Gustav. "On the concentration function of a sum of independent random variables." Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 9, no. 4 (1968): 290-308. https://link.springer.com/content/pdf/10.1007/BF00531753.pdf

[2] https://link.springer.com/article/10.1023/A:1022654631571

[3] KESTEN, H. (1969). A sharper form of the Doeblin-Lévy-Kolmogorov-Rogozin inequality for concentration functions. Math. Scand. 25 133–144.

[4] LEADER, I. and RADCLIFFE, A. J. (1994). Littlewood-Offord inequalities for random variables. SIAM J. Discrete Math. 7 90–101.

[5] https://arxiv.org/pdf/2201.09861.pdf

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.