Without looking at all the data, how can I test whether a collection only contains unique objects? I have collection of data objects distributed across multiple machines. An O(n) lookup is not feasible, so I will need to sample. Is there an algorithm that I can use (preferably one that can relate sampling size to margin of error)?
Context: I am using Modin. The data is rows in pandas Dataframes and are just int types. Nothing is known about the underlying structure of these ints however (prior to sampling).
 A: To expand Stephan's comment about the probability of detecting the duplicate, suppose there are $N$ objects with exactly 1 pair of duplicate values and the rest are unique. We propose taking a sample of $n$ objects and checking if any of the $n$ objects are duplicates. How large does $n$ have to be to give a $X\%$ chance of detecting the duplicates in $N$?
There are $N\choose n$ possible samples of size $n$ we can take, and ${N-2}\choose{n-2}$ of those possible samples will contain the two duplicates. (First choose the 2 duplicates, then choose the other $n-2$ values from the remaining $N-2$ in the population.)
The probability that a randomly selected sample contains both duplicates is
$$
\frac{N-2\choose n-2}{N\choose n} = \frac{n(n-1)}{N(N-1)}
$$
For a given $N$ and desired probability $X$, we can find the value of $n$ such that
$$
\frac{n(n-1)}{N(N-1)} > X\%
$$
Eg, suppose $N = 100$ and we want the probability of detecting duplicates to be at least 95%. Then we find $n$ such that
$$
\frac{n(n-1)}{100*99} > 0.95
$$
Giving $n > 97.48$. Therefore to have at least a 95% chance of detecting the duplicates, we need to sample at least 98 out of the 100 objects.
For $N = 100000$, we find $n \geq 97468$.
This is such a small improvement over checking all objects that it's probably not worth doing, although if you're willing to tolerate a lower chance of detecting the duplicates the required sample size does decrease.
