1
$\begingroup$

Suppose that $\epsilon_1, \dots, \epsilon_n$ are $n$, iid Rademacher random variables (equally likely to be $+1, -1$).

I would like to know what the tightest result is for the following concentration probability (for $\alpha > 0$)

$$ p_n(\alpha) := \mathbf{P}\left\{\left|\sum_{i=1}^n \epsilon_i \right| \leq \alpha \sqrt{n}\right\}. $$

One method I know of is via application of Hoeffding-type results, which yield something like

$$\mathbf{P}\left\{\left|\sum_{i=1}^n \epsilon_i \right| \leq \alpha \sqrt{n}\right\} = 1 - \mathbf{P}\left\{\left|\sum_{i=1}^n \epsilon_i \right| > \alpha \sqrt{n}\right\} \geq 1 - 2e^{-\alpha^2/2}. $$

The issue with this result is that if $\alpha < \sqrt{2 \ln 2}$, then this result is completely uninformative (it would be better to bound from below by 0).

Thus, I would like to know if there are better quantitative results (mostly for lower bounds on $p_n(\alpha)$) available for $\alpha$ quite small (say less than $1/2$) but still bounded away from $0$. I'm mostly interested in asymptotics, so we may assume $n$ is as large as we like.

$\endgroup$
  • $\begingroup$ Yes, those are called "anti-concentration results" or "small ball probability" results. $\endgroup$ – Ankitp Jun 20 at 3:36
1
$\begingroup$

A partial answer, which relies on the Central limit theorem goes like this. Since $\epsilon_1, \epsilon_2, \dots$ is an iid sequence of random variables with variance 1 and mean zero, the central limit theorem implies that $n^{-1/2} \sum_{k \leq n} \epsilon_k$ tends in distribution to a $N(0, 1)$ random variable. Hence, $$ \lim_n \mathbf{P}\left\{\left|\sum_{i=1}^n \epsilon_i\right| \leq \alpha \sqrt{n} \right\} = \mathbf{P}\left\{N(0,1) \leq \alpha \right\} = 1 - \mathbf{P}\{N(0,1) > \alpha\} \geq 1 - \frac{1}{\alpha} \frac{1}{\sqrt{2\pi}} e^{-\alpha^2/2}. $$ So at least asymptotically we can improve constants a bit.

$\endgroup$

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.