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
    In general, or if you are given $i$ and $s$?2012-11-07
  • 0
    You can assume constant $k$ and $s$. ($i$ is just for the sum.)2012-11-07
  • 0
    Try doing it numerically, or by trial and error.2012-11-07
  • 0
    Sure, it's easy enough to graph it, but what does that teach you? :-)2012-11-07
  • 0
    @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?2012-11-07
  • 0
    @Jean-Sébastien Suppose I want at least a 50% chance of getting $k$ or more successes. How many tries do I need so that the probability is 0.5?2012-11-07
  • 0
    In other words, I want to use some algebra to flip my equation from $P' = ...k...n...s...$ to $n = ...k...P'...s...$.2012-11-07
  • 0
    If you want exactly $k$ success that's easy, I'm writing it up right now2012-11-07
  • 0
    I've posted a partial solution, tell me if it helps you, 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! 
  • 0
    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.2012-11-08
  • 0
    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?2012-11-08
  • 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
0

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