Let $n$ be a large integer, $p$ be a small number (say, $p=C/n$ for some constant $C \ll n$), and consider the tail of the binomial distribution $B(n,p)$, after $T$:


$$
\delta = \sum\_{s=T}^{n} p^s (1-p)^{n-s} \binom{n}{s}
$$


I'd like to find a $T$ large enough that $\delta$ is on the order of $1/n$. [Berry-Esseen](https://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem) doesn't work, as the error term in $O(1/\sqrt{n})$. I found a better approximation of these trucated binomial sum in [this paper](http://users.cecs.anu.edu.au/~bdm/papers/littlewood2.pdf) (Theorem 2), but it's pretty complicated, and I'm having trouble extracting any kind of asymptotic from it, let alone an analytical formula.


Surely, such a $T$ exists: if $T$ is close to $n$, $\delta$ is really tiny (inversely exponential in $n$); and if $T$ is close to $C$, then $\delta=O(1)$. I have no intuition, however, whether choosing e.g. $T=2C$ is enough to get to $\delta=O(1/n)$ or if requires a much larger $T$. Importantly, I'm not only interested in asymptotics; but I'd like to be able to give a reasonably small $T$ such that $\delta<1/n$.



How far do I have to go for the tail of a binomial distribution with small $p$ to be $O(1/n)$?
$\newcommand{\de}{\delta}$
We have 
\begin{equation}
 \de=\sum\_{j=k}^n a\_j, 
\end{equation}
where $k:=T$, 
\begin{equation}
 a\_j:=a\_{n,j;p}:=\binom nj p^j q^{n-j}, 
\end{equation}
$p=c/n$, $c:=C\in(0,\infty)$ (a constant), and $q:=1-p=1-c/n$. 


Suppose now that $n\to\infty$, $b\in(0,\infty)$ (a constant), and 
\begin{equation}
 k=k\_n\sim b\frac{\ln n}{\ln\ln n}. 
\end{equation}
Then 
\begin{align\*}
 a\_k&=\frac{n(n-1)\cdots(n-(k-1))}{k!}\,p^k q^{n-k} \\ 
 &=\frac{(np)^k}{k!}\,e^{O(k^2/n)} (1-c/n)^{n-k} \\ 
 &=\frac{c^k}{k!}\,e^{O(1)}
 =\exp\{-(1+o(1))k\ln k\} \\ 
 &=\exp\{-(b+o(1))\ln n\}
 =n^{-b+o(1)}. 
\end{align\*}
Also, for $j=k,k+1,\dots,n-1$
\begin{equation}
 \frac{a\_{j+1}}{a\_j}=\frac{n-j}{j+1}\,\frac pq\le\frac c{(j+1)(1-c/n)}=o(1). 
\end{equation}
So, by a geometric progression bound, 
\begin{equation}
 \de=\sum\_{j=k}^n a\_j\sim a\_k=n^{-b+o(1)}. 
\end{equation}


We conclude that, to get $\de\asymp1/n$, we need exactly $b=1$, so that 
\begin{equation}
 k\sim\frac{\ln n}{\ln\ln n}. 
\end{equation}


