Likelihood of errors based on a sample

Question

I frequently do something like: load a bunch of data, and then scan some fraction of it randomly to verify that no errors occurred. The more data I verify, the greater my certainty that no errors occurred anywhere.

I'm curious about how I can express this formally. My thought process is:

Suppose there are $n$ records, of which $k$ contain errors. The probability of a randomly selected one containing an error is $k/n$ and conversely, the probability of selecting one without an error is $1-k/n$. If I model this as a Bernoulli process, I believe the probability of $t$ samples all having no error is $\left(1-k/n\right)^t$. So given some information about the data, I can get the probability of finding no errors.

But what I really want is the reverse: given that I found no errors, what confidence do I have that there are less than $k_{act}$ errors in actuality? I think I could use Bayes' theorem here, but that would require me having some priors which seem difficult to estimate.

Can I just set my formula equal to, say, $.95$ and solve, and then claim I've found a 95% confidence interval?

By the way, I'm interested for curiosity's sake. I think a more realistic attempt would take into account that errors would tend to propagate, for example.

Answer 1

Your problem is called Laplace's succession rule, namely that if you have seen no error in a batch of $t$ independent draws from a Bernoulli $B(p)$, the (posterior) probability that the next draw will error-free is $$ \dfrac{t+1}{t+2}\,. $$ This is Bayesian in that you put a uniform prior on the probability of error, $p$. No need to "estimate" anything.

The way you presented the problem is slightly different in that you are working on an hypergeometric assumption, hence the probability of having $t$ draws with no error is $$ \dfrac{{t \choose n-k}\times 1}{{t \choose n}} $$ rather than the $(1=\frac{k}{n})^t$ you proposed. If $n$ is large compared with $t$, it does not make too much of a difference. Otherwise, if you put a uniform prior on $k$, you recover once again Laplace's rule, $$ P(k=0|X_t=0) = \dfrac{t+1}{t+2}\,. $$ (This is detailed in Section 4.3.1 on The Bayesian Choice. The Wikipedia entry is unnecessarily convoluted.)