Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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!
share|improve this answer
    
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
1  
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

This is a partial solution

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.