# Lower bound for concentration probability of Rademacher sum

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.

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

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.