# Concentration inequalities for very rare events on a multiplicative scale

Let $$E_1, \dots, E_N$$ be independent events, each of probability $$p$$, where $$p$$ is very close to $$0$$. Let $$A_N = \frac{1}{N} ( 1_{E_1} + \dots + 1_{E_N} )$$ be the proportion of the events $$E_i$$ that occur. We expect $$A_N$$ to be tightly concentrated around its mean $$p$$.

Suppose we want to estimate something like $$\mathbb{P}(A_N > p^{1/2})$$. On the one hand, the multiplicative difference $$p^{1/2}/p$$ is huge, but on the other hand the additive difference $$p^{1/2} - p$$ is very small. All the standard concentration inequalities (Azuma-Hoeffding, Chernov, etc.) give an upper bound for the above probability in terms of the additive difference, which gives only a very slow exponential decay rate as $$N \to \infty$$ for the above probability if $$p$$ is very small.

My question is: which phenomenon is closer to the truth? Should the event $$\{A_N > p^{1/2}\}$$ be very rare because $$p^{1/2}/p$$ is huge, or should it be not so rare because $$p^{1/2} - p$$ is tiny? If the former, are there any references out there for concentration inequalities that capture that?

• $NA_N$ is binomial, so roughly normal with mean $Np$ and variance $Np(1-p)$, and $A_N>\sqrt{p}$ is an event at $$\frac{N\sqrt{p}-Np}{\sqrt{Np(1-p)}}=\sqrt{N}\frac{1-\sqrt{p}}{\sqrt{1-p}}$$ standard deviations. This will be rare, and can be estimated using standard approximations for the normal distribution. – Matt F. Nov 13 '20 at 9:59
• @MattF. : The normal approximation to the binomial distribution works only if $npq$ is large, where $q:=1-p$. So, if $p=o(1/n)$ (say), then this approximation will not work. – Iosif Pinelis Nov 13 '20 at 14:38
• @IosifPinelis, agreed; since the question asks for information on the decay rate as $N\to\infty$, that seems the right place to start. – Matt F. Nov 13 '20 at 14:53
• There are a couple of inequalities for very large deviations stated in "Random Graphs" by Bollobás, Theorem 1.7. Maybe someone knows a more comprehensive reference. – Harry West Nov 14 '20 at 8:05

Let $$n:=N$$. Let us show that for all natural $$n$$ and all $$p\in(0,1)$$ $$P(A_n>\sqrt p)\le\frac{\sqrt p+p}{1+p},\tag{1}$$ so that $$P(A_n>\sqrt p)\to0$$ whenever $$p\downarrow0$$.
Consider first the case when $$n\ge1/\sqrt p$$, so that $$1/n\le\sqrt p$$. In view of Cantelli's inequality, \begin{aligned} P(A_n>\sqrt p)&\le\frac{p(1-p)/n}{p(1-p)/n+(\sqrt p-p)^2} \\ &\le\frac{p(1-p)\sqrt p}{p(1-p)\sqrt p+(\sqrt p-p)^2} \\ &=\frac{\sqrt p+p}{1+p}, \end{aligned} so that (1) holds if $$n\ge1/\sqrt p$$.
In the remaining case, when $$n<1/\sqrt p$$, we have $$\sqrt p<1/n$$ and hence $$P(A_n>\sqrt p)=P(A_n>0)=1-(1-p)^n\le np<\sqrt p<\frac{\sqrt p+p}{1+p},$$ so that (1) again holds.
Thus indeed, (1) holds for all natural $$n$$ and all $$p\in(0,1)$$. (It actually holds for all $$p\in[0,1]$$.)
• Thanks! So it looks like the answer is "less rare", in the sense that the exponential decay rate as $N \to \infty$ is very slow if $p$ is tiny. – Adam Nov 13 '20 at 17:31
• The condition $n \sqrt p\,\ln\frac1{\sqrt p}\to\infty$ can't be necessary for $P(A_n>\sqrt p)\to0,$ if $p$ is allowed to be $o(1/n).$ A union bound (or Markov inequality) gives $P(A_n>\sqrt{p})\leq P(A_n\geq 1/n)\leq pn.$ Plugging in $p=n^{-3}$ we get $pn\to 0$ and $n \sqrt p\,\ln\frac1{\sqrt p}=n^{-1/2}\ln n^{3/2}\not\to\infty.$ – Harry West Nov 14 '20 at 7:51