Minimum number of Bernoulli trials until sum reaches threshold with high probability

Question

Let $X_1, X_2, \dots$ be i.i.d. $Bern(p)$ with $p\in (0, 1)$. Let $\delta \in (0,1)$ and $m \in \mathbb{N}$. What is the smallest integer $n \in \mathbb{N}$ such that $$P\left( \sum_{i=1}^n X_i \geq m \right) \geq 1- \delta \text{ ?} $$

Are there any bounds/approximations of $n$ in terms of $p$, $m$, and $\delta$?

(It very much reminds of the Chernoff bound, but this is in some sense the reverse direction I guess.)

Answer 1

If you use some kind of normal approximation, and if $q= \Phi^{-1}(1-\delta)$ you might use something like

$$\frac{np-m}{\sqrt{np(1-p)}} \approx q$$ to get (with rounding up)

$$n \approx \left\lceil\frac{2 m+q^2 ( 1-p) +q \sqrt{4 m ( 1-p) +q^2( 1-p)^2 }}{2 p}\right\rceil$$

Experimentation suggests this may give reasonably sharp results for large $p$ and large $m$, but less sharp for small $p$ and small $m$

   p      m      delta   best n   estimated n
   0.01   1      0.05       299      446
   0.2    1      0.05        14       20
   0.5    1      0.05         5        7
   0.8    1      0.05         2        3
   0.99   1      0.05         1        2
   0.01   1000   0.05    105231   105312 
   0.2    1000   0.05      5235     5239
   0.5    1000   0.05      2074     2075
   0.8    1000   0.05      1279     1280
   0.99   1000   0.05      1016     1016

As an example with R:

estn <- function(p, m, delta){
  k <- qnorm(1-delta)
  nhat <- (2*m+k^2*(1-p)+k*sqrt(4*m*(1-p)+k^2*(1-p)^2)) / (2*p)
  c(best_n=min(which(pbinom(m-1/2, 1:ceiling(nhat+m/p), p) <= delta)), 
    estimated_n=ceiling(nhat))
}

estn(p=0.01, m=1000, delta=0.05)
#  best_n estimated_n 
#  105231      105312