I have read through existing answers on CrossValidated (plus elsewhere online) and can't find what I'm looking for, but do please point me to existing sources if I've missed them.

Let's say I have a data set of N=1000 records, each of which can be manually sampled and labelled as either 'Valid' or 'Invalid' (or True/False, Right/Wrong, etc).

I want to achieve a given level of confidence that all records in the data set are Valid. As I sample records, if I find a single Invalid one I would go back and amend how the data set is created to rectify that and similar problems.

So, after some iterations of spotting Invalids, fixing and recreating the data set, I do some sampling that only includes Valid records. If I want to be (say) 99% or 95% sure that all records are Valid, how big does my sample have to be? (Ideally as a function of N.)

I've tried playing around with Hypergeometric tests (http://en.wikipedia.org/wiki/Hypergeometric_distribution#Hypergeometric_test) - in that context I want to know what k should be, but I don't have a fixed value of K. Rather I want to choose k such that K is likely to be equal to N - but setting K=N obviously works out to a Probability of 1! I'm also wondering if I need to use a Bayesian approach but I don't understand Bayesian stats enough.


1 Answer 1


This can be framed as testing the null hypothesis that there are some invalid records in the data set ($K>0$) vs the alternative that there are none ($K=0$), given that there are no invalid records found in the sample ($k=0$). The proximal null, the toughest to reject, is that there's a single invalid record ($K=1$). Substitute these into the hypergeometric probability mass function for a sample of size $n$ from a data-set of size $N$ to get the p-value (there are no possible smaller values of $k$ to be considered):

$$f(k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$$ $$ = \frac{\binom{1}{0}\binom{N-1}{n-0}}{\binom{N}{n}}$$ $$ =\frac{N-n}{N}=p$$

So the minimum sample size $n^*$ required to be able to reject the null hypothesis at a significance level $p$ (or equivalently to obtain a one-sided $\alpha=1-p$ confidence interval of $K=0$) is simply

$$n^*=\lceil (1-p) N \rceil$$ $$n^*=\lceil \alpha N \rceil$$

With $N=1000$, and $\alpha=0.95$, $n^*=950$. If that seems a lot, consider that all of a thousand records' being valid is a strict criterion; if you consider relaxing it the same approach can be used to test say $K>9$.

  • $\begingroup$ That's a different approach to what I'd concluded from reading the linked articles (i.e. applying the Rule of Three). It makes good sense though and is actually less conservative than the Rule of 3 (which if I did my sums right, recommends sampling 3000 records for N=1000). The general conclusion of "statistics says you might as well check basically everything if you need to be this certain" applies to either approach. $\endgroup$ Feb 28, 2015 at 19:14
  • $\begingroup$ Well note that the Rule of Three only approximately applies to sampling without replacement from a finite population; when $n \ll N$. $\endgroup$ Mar 1, 2015 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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