Probability of Invalid document in a large data set I am auditing a very large data set of documents. A document can either be Valid or Invalid.
Checking a document is computationally intensive. Its is not feasible to check the validity of all the documents.
I checked a set of randomly selected 10 million documents out of 10 billion, all of them where Valid.
What is the probability of all data set to be Valid, knowing that all the ones I already randomly selected where Valid? (i.e. how confident can I be about the data set validity?)
PS. I don't know any theoretical probability of a single Document to be Invalid or Valid. All I know is that every single document I checked was Valid.
 A: If you don't have any information about the distribution in the underlying population, I don't think this question is sufficiently well-defined to have a clear answer. In general, if you were to think of your large database as a "population" with infinitely many documents, and the "true" probability of being invalid is $p$, then on average you would need $1/p$ samples to discover a single such instance. When one studies "rare events" with very small $p$, it is quite common to have samples in which this event never happens.
Perhaps it would be better to take a more statistical approach to the problem. In statistics you first hypothesize what the true distribution is, and then you calculate the likelihood of observing your sample under the null hypothesis.

*

*Let's say that your population has size $N$ (that is the $10$ billion documents) and $0$ of those documents are defective. Then, obviously, the probability of getting a perfect sample is $1$.

*Now hypothesize that $1$ of the documents in the population is defective. You can calculate the probability of drawing a sample of $10$ million with exactly $0$ invalid documents from a population of $10$ billion that has exactly $1$ invalid document. That probability comes from a hypergeometric distribution; it will be very close to $1$.

*Now hypothesize that $k = 2,3,...$ of the documents in the population are defective, and calculate the hypergeometric probability where the population of $10$ billion has exactly $k$ invalid documents and the sample of $10$ million has none.

As $k$ increases, the probability will become smaller and smaller. As the statistician, you will have to set a threshold beyond which the probability is so small that you are willing to "reject" the hypothesis (in other words, you do not believe that $k$ can realistically be that large). If the probability is above that threshold, all you can say is that you are not able to reject the hypothesis. You will never be able to calculate the probability that any particular hypothesis is true; you will only be able to reject some of the hypotheses as being "too unlikely," but the decision to reject will also depend on the threshold that you set.
A: Interesting question. I'm not sure how to answer your precise question, but here's one way to think about it that you may find useful. Running a chi-squared test of proportions on zero observed invalid documents in 10 million samples, we find the upper bound of the 95% confidence interval of the true proportion is $4.7$ x $10^{-7}$ - despite never observing an invalid document, it's still feasible that one in every ~2 million documents is invalid. Since the remaining corpus is ~10 billion samples, you might expect as many as 5,000 invalid documents. A sample of 10 million is not sufficient to conclude with any kind of certainty that the entire dataset of 10 billion is valid.
Even checking 1 billion documents, the upper bound on the confidence interval is $4.7$ x $10^{-9}$, or roughly 1 in 200 million. You still might expect to find 45 invalid documents in the remaining 9 billion documents. A sample of 8 billion yields an upper bound of 1 in 1.7 billion, so you could reasonably expect to find 1 invalid document in the remaining 2 billion. You'd need to observe more than 8 billion valid documents to have confidence that the remainder are also all valid.
This doesn't quite answer the question of what's the probability of the whole dataset being valid given a certain sample size, but may still be a useful line of reasoning to estimate what sample size you need to be reasonably sure that the remaining samples are all valid. It also gives some insight as to how many invalid documents you might expect to find given a particular sample size.
