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.

I'm writing a test for a probabilistic data structure that I've implemented. Since its probabilistic, its performance is different every time, and in particular, the performance varies much more widely (as a percentage) when the number of items is small. I want the test to fail if the performance is so bad that it's unlikely to have been that bad by chance. Basically, I want a significance test.

In the test, I check the structure n times. Each check may fail with probability p. If the total number of failures is more than twice the standard deviation greater than the mean (n*p), I want to fail the test. Now, I know n and I can calculate p. How can I use n and p to get the standard deviation?

I know it can be easily estimated by simulation, but there are about a hundred combinations of n and p, so I would prefer a way to just calculate it. Unfortunately, I haven't found an answer, or if I have it was too complex for this layman to notice.

share|improve this question
1  
When you say "the total number of failures is greater than twice the standard deviation..." you should probably add "...more than the expected number of failures $np$..." –  Henry Jun 10 '11 at 22:23
    
Good question! I hope it's okay that I removed the "probability-theory" tag. –  Elliott Jun 10 '11 at 22:30
    
Thanks, Henry. It was poorly phrased. –  Adam M. Jun 10 '11 at 22:32

1 Answer 1

up vote 3 down vote accepted

This is the binomial distribution.

If you know $p$ before the test and the checks are independent then the standard deviation is $\sqrt{ n p (1-p)}$

share|improve this answer
    
Excellent. This does indeed agree with my simulations. Thank you! –  Adam M. Jun 10 '11 at 22:27
    
Similarly to calculate mean we simply multiply p and n. –  user75917 May 4 '13 at 10:43

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.