This question is related to one of my question:
Probability that two random sets have at least one element in common
Assume we have a field $\mathbb{F}_p$, where $p$ is a large prime number i.e. $p$ is a $2^{128}$ number)
I have two sets $S_1$ and $S_2$ whose elements are drawn uniformly at random from the field, and $|S_1|=|S_2|=d$.
Question: What should the sets cardinality, $d$, be to make the probability that the sets have any element in common negligible?
The probability that $S_2$ is disjoint from $S_1$ is $\frac{\binom{p-d}{d}}{\binom{p}{d}} = \prod_{j=0}^{d-1} \frac{p-d-j}{p-j}$.
This product is at least $\left( 1 - \frac{d}{p-d} \right)^d \ge 1 - \frac{d^2}{p-d}$. If $d = o( \sqrt{p})$, this is $1 - o(1)$, and hence the sets are almost surely disjoint.
On the other hand, the product is at most $\left( 1 - \frac{d}{p} \right)^d \le e^{ - \frac{d^2}{p}} = o(1)$ when $d = \omega(\sqrt{p})$. Hence the sets will almost surely intersect when the set size is large compared to $\sqrt{p}$.
For a heuristic argument, suppose $S_1$ and $S_2$ are formed by choosing each element independently with probability $q = \frac{d}{p}$. The probability that an element is in both sets is $q^2$. Hence the expected size of the intersection is $p q^2 = \frac{d^2}{p}$, which suggests that the threshold should be when $d = \sqrt{p}$.