Skip to main content
5 of 13
added 75 characters in body
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

$\newcommand\hp{\hat p}\newcommand\hq{\hat q}$Let $n:=N$. Assume $n\ge2$. We have to estimate $$P(A_n>\sqrt p)=\sum_{j=k}^n a_j$$ assuming $p\downarrow0$, where $k:=k_{n,p}:=1+\lfloor n\sqrt p\rfloor$, $$a_j:=\binom nj p^jq^{n-j},$$ and $q:=1-p$. For $j\in\{k,\dots,n-1\}$, $$\frac{a_{j+1}}{a_j}=\frac{n-j}{j+1}\frac pq\le\frac{n-k}{k+1}\frac pq\le\frac{np}{n\sqrt p}\frac1q =\frac{\sqrt p}q\to0.$$ Therefore and by Stirling's formula, $$P(A_n>\sqrt p)\sim a_k\asymp\sqrt{\frac n{k(n-k)}}\exp\{-n D(\hp||p)\}$$ where $$D(\hp||p):=\hp\,\ln\frac{\hp}p+(1-\hp)\ln\frac{1-\hp}{1-p},$$ and
$$\hp:=\frac kn.$$

Suppose now that $n\sqrt p\ge1$. Then $\sqrt p<\hp\le2\sqrt p$, so that $\hp\asymp\sqrt p$ and $\ln\frac{\hp}p\sim\ln\frac1{\sqrt p}$, whence $$D(\hp||p)\ge\sqrt p\,\ln\frac1{\sqrt p}-O(\sqrt p)\ge\frac{\sqrt p}2\,\ln\frac1{\sqrt p}$$ eventually (for all small enough $p>0$).

Also, eventually
$$\sqrt{\frac n{k(n-k)}}\le\sqrt{\frac n{n-1}}\le\sqrt2,$$ since $n\ge2$, $k\ge1$, and eventually $k\le n-1$.

Collecting pieces, in the case when $n\sqrt p\ge1$ eventually we get $$P(A_n>\sqrt p)\ll\exp\{-n \frac{\sqrt p}2\,\ln\frac1{\sqrt p}\} \le\exp\{-\frac12\,\ln\frac1{\sqrt p}\}\to0.$$

In the remaining case, when $n\sqrt p<1$, we have $P(A_n>\sqrt p)=P(A_n>0)=1-(1-p)^n\le np\to0$.

Thus, $P(A_n>\sqrt p)\to0$ whenever $p\downarrow0$.

Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229