Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm fixing a software defect that occurs 1 in n test runs. If I want to know that the probability of it being fixed is >= p for some 0 <= p < 1, how many times, m, do I need to run the test successfully (without the defect occurring)?

share|improve this question
    
This is a good question for somewhere else, but it's off-topic for MO. Try the other sites mentioned in the FAQ. –  Douglas Zare May 7 '10 at 19:21
    
I believe this is an ill-posed question, contrary to the implications of the previous comment and the 3 answers at the time of this writing. Regardless of the values of n, p, and m, there is no way to know, in any sense of the word, that the probability that the defect has been fixed is >= p. (Rather, in this situation statisticians make use of confidence intervals.) –  Daniel Asimov May 9 '10 at 19:54
    
Good point. No assumption was stated about the probability before any testing. That's fixable, or one could ask for a p-value. –  Douglas Zare May 10 '10 at 18:54
add comment

closed as off topic by Gerald Edgar, Harald Hanche-Olsen, Steve Huntsman, Noah Snyder, Douglas Zare May 7 '10 at 19:19

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

3 Answers

up vote 0 down vote accepted

According to my statistics final which I took yesterday, the answer should be
$m=\lceil 2\left(1-\frac{1}{n}\right)\text{InverseErf}^2[1-p]\rceil$ where InverseErf[x] is the Inverse Error Function.

share|improve this answer
    
I'm not sure you can state a definitive answer like that without making more assumptions than the original asker states. What were your additional assumptions? –  Dan Piponi May 7 '10 at 16:18
    
I was assuming that the number of times before the error occurs is roughly normally distributed - if the test is done enough times, a binomial distribution can be well-approximated by a normal distribution. $1-\text{Erf}\left[\sqrt{\frac{t\left(\frac{1}{n}-0\right)}{2 \frac{1}{n} \left(1-\frac{1}{n}\right)}}\right]$ is the equation for the probability of making a type-1 error (mistakenly assuming that we've fixed it). –  Gabriel Benamy May 7 '10 at 16:22
    
Yes, that's a reasonable assumption. –  Paul Reiners May 7 '10 at 16:30
    
The number of successes before first failure is given by a geometric distribution. It's nothing like a normal distribution. en.wikipedia.org/wiki/Geometric_distribution –  Dan Piponi May 7 '10 at 18:03
    
I agree that a normal approximation is likely to be bad. If you must use a normal approximation, use $(-\infty,\frac 12)$ instead of $(-\infty, 0)$ because the count takes values in the integers. –  Douglas Zare May 7 '10 at 19:12
add comment

I guess $m>\log(1-p)/\log(1-1/n)$ works since the probability of a faulty system running $m$ times without defect is $(1-1/n)^m$ and this should be smaller than $1-p$.

This seems to be a homework type question (and moreover an easy one) rather than a MO-question.

share|improve this answer
    
Well, it's not homework. I wish it were. It's a bug that only QA seems to be able to reproduce. And, yes, I probably should have just looked it up, since it's a rather simple question. –  Paul Reiners May 7 '10 at 16:07
add comment

If your problem was a little bit more difficult (roland-bacher already provided an easy, precise and correct solution) and your $n$ is big, you can also approximate the binomial distribution by a Poisson distribution. Repeating the test $m$ times gives then the parameter $\lambda = \frac{m}{n}$ and your goal is that $m$ is big enough that $e^{-\lambda}\ge 1-p$. So $m \ge -n\ln(1-p)$. The approximation by the Poisson distribution is pretty good, for $n = 500$ and $p = 0.99$ it yields $m > 2302.585$ instead of the correct $m > 2300.28$ given by roland-bacher's formula.

share|improve this answer
add comment

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