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?

Improve this question
$\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$
    – user44143
    Commented Nov 13, 2020 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
    Commented Nov 13, 2020 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$
    – user44143
    Commented Nov 13, 2020 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
    Commented Nov 14, 2020 at 8:05

1 Answer 1

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

Improve this answer
$\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
    Commented Nov 13, 2020 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
    Commented Nov 14, 2020 at 7:51
  • $\begingroup$ @HarryWest : Thank you for your comment. This is now fixed. $\endgroup$
    – Iosif Pinelis
    Commented Nov 15, 2020 at 4:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .