I am searching for a Chernoff-like bound that controls the probability of small intervals in the tail distribution. More specifically, let $X_1, \ldots, X_n$ be independent random variables with values in $[0,1]$. Let $X := \sum X_i$ and $\mu := \mathbb E[X]$. My conjecture is that, for $\lambda \in [0,\sqrt{\mu}]$, an inequality like the following holds: $$\mathbb P[ \mu + \lambda \sqrt{\mu} \leq X \leq \mu + \lambda\sqrt{\mu} + 1] \leq \frac{e^{-\lambda^2/3}}{\sqrt{\pi \mu}}.$$ (I'll be happy if you need to include diverse absolute constants in the right hand side, even in the exponential... Also, note that I've chosen the width of the interval to be large enough to avoid discretization issues.)

Here's why I think this inequality holds. First, it can be proved that $Var X \leq \mu$, with equality in the extreme case where $X$ is a Poisson distribution (and thus, intuitively, a sum of infinitely many independent random variables). When $X$ is a Poisson distribution, the inequality does hold. Moreover, by analogy with the normal distribution, my intuition is that, when $\lambda \geq 1$, because the Poisson distribution maximizes the variance, it also maximizes the left-hand side above (up to discretization artefacts). Indeed, the probability density function $f_\sigma(x)$ of $\mathcal N(0,\sigma^2)$ for $\sigma \in [0,1]$ and restricted to $x \geq 1$ is increasing in $\sigma$.

Any help is welcome. Thank you!

EDIT: It seems that, using a non-uniform Berry-Esseen bound, one can get a bound of $O \left( \frac{1}{\lambda^3 \sqrt{\mu}} \right)$. This does not seem tight to me though.


For n large enough, you could use the local limit theorem, see section 3.5 in Durrett's book: https://www.math.duke.edu/~rtd/PTE/PTE4_1.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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