The Probability of Non-Intersection of Two Equi-Size Random Sets

Consider two sets of equal length k , each element of which is sampled from a uniformly-distributed set of integers in the range [1, M] with 2 k ≤ M . This paper derives an exact expression for the probability that there will be no ele- ments in common between the two sets, and compares this to what is obtained from the familiar binomial distribution. It is shown that the binomial solution is accurate to the order of 1/M ² , which is expected to be adequate for practical purposes.