1
$\begingroup$

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.

  • 0
    I've posted a partial solution, tell me if it helps $y$ou, I'll be back later2012-11-07

2 Answers 2

1

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) { # 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! 
  • 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.2012-11-09
1

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.

  • 0
    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?2012-11-08