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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .