9
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ $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. $\endgroup$ – Matt F. Nov 13 '20 at 9:59
  • $\begingroup$ @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. $\endgroup$ – Iosif Pinelis Nov 13 '20 at 14:38
  • $\begingroup$ @IosifPinelis, agreed; since the question asks for information on the decay rate as $N\to\infty$, that seems the right place to start. $\endgroup$ – Matt F. Nov 13 '20 at 14:53
  • $\begingroup$ 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. $\endgroup$ – Harry West Nov 14 '20 at 8:05
7
$\begingroup$

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]$.)

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Adam Nov 13 '20 at 17:31
  • 1
    $\begingroup$ 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.$ $\endgroup$ – Harry West Nov 14 '20 at 7:51
  • $\begingroup$ @HarryWest : Thank you for your comment. This is now fixed. $\endgroup$ – Iosif Pinelis Nov 15 '20 at 4:30

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.