I have a set of independent Bernoulli trials $X_i$ (biased coins with probability $p$). How many coins do I need to throw to obtain at least $c$ successes with a-priori probability at least $\delta$?
Formally, I want $\mathbb{P}[\sum_{i=1}^n X_i \geq c] \geq \delta$ which is the Binomial tail distribution, however $n$ is the variable. I am looking for something that I can reasonably solve for $n$. All the expressions I found, including typical Chernoff / Hoeffding bounds, are quite impractical for this direction. I'm fine with a $O(....)$ estimation, maybe this allows for a lot of simplifications.
I also found that this is closely related to the negative binomial distribution, however I didn't find any estimations for its CDF either.
EDIT, to clarify: My main goal is to show that the $n$ is (at most) polynomial (or maybe it is exponential?) in the given constants. I want to prove the time complexity of an sampling-based algorithm.
The probability of at least $c$ successes in $n$ trials with probability $p$ of success in each can be expressed using a hypergeometric function $$ G(c,n,p) = {n\choose c}{p}^{c} \left( 1-p \right) ^{n-c} {\mbox{$_2$F$_1$}\left(1,c-n;\,c+1;\,{\frac {p}{p-1}}\right)} $$ In principle $G(c,n,p)=\delta$ can be solved for $n$ numerically.
Asymptotically, as $n$ and $c$ get large (with $p$ and $\delta$ fixed) we may use the de Moivre-Laplace theorem. A binomial($n,p$) random variable $X$ can be approximated by a normal random variable with the same mean $np$ and variance $np(1-p)$. If $\Phi$ is the CDF of the standard normal random variable, $$ \mathbb P(X \ge c) \approx 1 - \Phi\left( \frac{c-np}{\sqrt{np(1-p)}}\right)$$ This is $\delta$ if $$\frac{c-np}{\sqrt{np(1-p)}} \approx \Phi^{-1}(1-\delta) $$ i.e. $$ n \approx \frac{c}{p} - \frac{r}{2p} \sqrt{ (1-p)^2 r^2 + 4 c (1-p)} + \frac{(1-p) r^2}{2p}$$ where $r = \Phi^{-1}(1-\delta)$.