Determining smallest number of samples for 99% accuracy

Question

I'm trying to compare 100,000 records on a local database (L) with 100,000 records on a remote database (R).

Basically I want to know if an element in L exists in R. To determine that, I have to make a request against the R for each L, which takes a long time (I know, there should be a better way, there isn't, that's the API I've got).

So I would like to test a small sample of L against R, and then infer with some level of confidence how many are present in the whole R. How many do I have to test to have a 99% confidence level?

Answer 1

Is this a trick question? Its 99% right? After checking each one individually you'll know with 100% certainty whether or not its in the remote database, so if you want to check the whole database to 99% accuracy - you have to check 99% of the records (99,000).

Answer 2

If you test N records from your local database and all are in the remote database, you can estimate the probability of a local record not being in the remote database as being between 0 and 3/N. This is called the "rule of three" in statistics. I explain it here.

The only way to know that all records are in both databases is to test all of them. But if you test 100 records, for example, you can estimate that the proportion of records not in both databases is below 3%.

Answer 3

I would also suggest experimental design for estimating a proportion p.

Suppose that we are interested in estimating the proportion p of the elements in L that also exist in R and we would like to compute a 99% C.I. with a tolerance level (lvl) that is plus or minus 3%. A “conservative” estimate of the size of the random sample would be given by :

n = (Za/2)^2 / (4*lvl^2)

In R

CI<-.99
lvl<-.03    
qnorm(1-(1-CI)/2,0,1)^2/(4*lvl^2)
[1] 1843.027

Check here for details