What is the best (most reliable and robust) test to measure deviations from tiny expected proportions (e.g., p0 < 10^-6) in a huge sample?
Binomial? Poisson? Negative binomial? Something else?
How do these tests differ? What are their limitations?
And how to calculate power/sample size for each test?
I'm surely not the best one to answer this, but since the question has been unanswered for months, I'll try.
Since you are asking about proportions, I understand your process is a binomial. Then I would go for a binomial.
A Poisson variable would just be an approximation to binomial, and since proportions are tiny and sample is huge, we can expect a Poisson approximation to work well. Then, you could use a Poisson if it made your computations easier.
The other usual approximation to binomial is normal distribution, but with such a tiny proportion you would need an extremely big sample for the normal to be a good approximation - I mean a sample quite bigger than the inverse of the tiny probability.
Negative binomial is about time between successes, and if you are analysing proportion of successes I don't see how could negative binomial help.
In summary, I'd say use binomial, and approximate it by Poisson if (and only if) it makes your work easier.
