# How many tries to get at least k successes?

The probability $P'$ of getting at least $k$ successes in $n$ independent tries, given probability of a single success $s$, equals one minus the summed probabilities of getting only $0$ to $k-1$ successes:

$P'(k, n, s) = 1 - \sum\limits_{i=0}^{k-1} P(i, n, s)$

where the probability $P$ of getting exactly $k$ successes is:

$P(k, n, s) = \,_nC_k \cdot s^k \cdot (1 - s)^{n - k}$

Now suppose I want to know how many tries I need to achieve a given probability $P'$. How do I solve for $n$?

This question is a lot like the question here:

On the Total Number of Tries Required to have $n$ Successes

But in that question each trial is not independent, since it's about selecting stones from a bag without replacement. In my question, each trial is independent.

-
In general, or if you are given $i$ and $s$? –  glebovg Nov 7 '12 at 22:49
You can assume constant $k$ and $s$. ($i$ is just for the sum.) –  Paul A Jungwirth Nov 7 '12 at 22:50
Try doing it numerically, or by trial and error. –  glebovg Nov 7 '12 at 22:54
Sure, it's easy enough to graph it, but what does that teach you? :-) –  Paul A Jungwirth Nov 7 '12 at 23:03
@PaulAJungwirth Could you clarify what you mean by "Now suppose I want to know how many tries I need to achieve a given probability P′. How do I solve for n?" Do you want to know the probability that it takes $n$ trials to get $k$ succes? –  Jean-Sébastien Nov 7 '12 at 23:06

There is no exact closed form solution. If $k$ is moderately large, the normal approximation to the binomial will give you an approximate answer, and you can then do a numerical search around there for the exact answer. For the normal approximation we want $$\Phi\left(\frac{k-ns}{\sqrt{ns(1-s)}}\right) \geq .9,$$ where $\Phi$ is the normal cdf. You can take the inverse cdf, simplify this to a quadratic in $\sqrt n$, and find a value for $n$. Since this is not exact, you can then check other nearby values of $n$ to find the exact solution.

Here's an R function that solves it for you using this approach, though not particularly efficiently:

binomial.size <- function(k,s,p) {
# Find the smallest sample size n such that a binomial(n,s) has
# probability at least p of having k sucesses.

# our first approximation comes from solving the quadratic:
n <- ceiling(((-qnorm(p)+sqrt(qnorm(p)^2+4*k/(1-s)))/(2*sqrt(s/(1-s))))^2)

while(pbinom(k-1,n,s,lower.tail=FALSE)<p) { # our n might be too small...
n <- n+1
}

while(pbinom(k-1,n-1,s,lower.tail=FALSE)>p) { # or too large...
n <- n-1
}

return(n)
}

binomial.size(15,0.4,0.5)
## 37
pbinom(14,37,0.4,lower.tail=FALSE)
## 0.54
pbinom(14,36,0.4,lower.tail=FALSE)
## 0.48--too small!

-
Thank you! I'll need to digest the math a bit more, but the R function gives correct results for a few examples I tried. –  Paul A Jungwirth Nov 8 '12 at 18:39
If I want to read more about the mathematics of binomial distributions, where is a good place to look? I've encountered them in statistics, but what would be the math course that introduces them? Probability? –  Paul A Jungwirth Nov 8 '12 at 18:45
A probability class will probably use the binomial for examples, but you won't spend a lot of time on it. A combinatorics class will probably give you more exposure to its use in various types of problems. I'm not sure what exactly you're looking for, though. –  Jonathan Christensen Nov 9 '12 at 2:35
For the case exactly $k$ success:
The probability that a sequence of independant Bernoulli trials takes $n$ steps before getting the $k^{th}$ success is given by (an adaptation of) the binomial negative distribution. Think of it this way:
You need your $n^{th}$ trial to be a success. You also need $k-1$ successes in the $n-1$ remaining spots. The rest are failures. Let $X$ be the number of trials it takes to get $k$ success. The probability of $X$ being $n$ is then given by $$\Pr(X=n)={n-1\choose k-1}s^{k}(1-s)^{n-k}$$ Its median seems to be somewhat complicated, see for example this.
Thank you for your help! I can't tell how this differs from what I wrote about finding $P$ for exactly $k$ successes, so how does it get me closer to a solution for at least $k$ successes? Perhaps you could expand on it a bit to help me understand? –  Paul A Jungwirth Nov 8 '12 at 18:38