Probability of N people choosing at least one of the same number when simultaneously choosing a set of X distinct numbers from a set of K numbers?

Question

I'm trying to optimize the batch size for concurrent insertion of random numbers into a SQL database table. If I allow concurrent threads to choose too many numbers at once, the chance of a collision occurs and the whole insert will fail with a primary key violation.

Suppose there are K = 2³² possible values to choose from (I'm actually working with 2⁶⁴, but find that even Wolfram Alpha cannot compute stats on numbers that high). If thread 1 chooses X distinct** numbers from K possible numbers, and thread 2 also chooses X distinct** numbers, then what is the probability that their sets chosen will have at least one number in common? I guess this is the same as 1 minus the probability that they will have no numbers in common. So, I suppose it could be that probability occurring X times in a row. Does that seem right?

**There's an assumption here that the set of X numbers each thread chooses at random are distinct numbers, although that's not actually the case in reality, as each thread will generate X numbers from K randomly; however, the probability of that happening is low enough for large sets K that we can assume the set is always X distinct numbers chosen from K.

I think this formula (https://math.stackexchange.com/a/765985/134968) does the trick of finding the probability that two people will pick the same number from K numbers, but I'm unsure how to interpret those same two people picking X numbers at once and having any one of them in common. Maybe, what I'm really interested in is the probability of any 2 of N threads choosing at least one of the same number when each thread chooses X numbers from K possible numbers. When choosing X numbers, there's a possibility they won't be distinct, so there are probabilities wrapped in probabilities here.

Using the basic formula an K=2³², I tried different values of N to get:

When N = 1,000,000 then p = 0.999999999999999999999999999999999999999999999999997260985...

When N = 100,000 then p = 0.687812281963697434920870498897447658960448745760794257150...

When N = 10,000 then p = 0.011572889986216787660266653043871226047288549345089430418...

When N = 1,000 then p = 0.000116292153069860696126800559888258906720144037603969093...

When N = 100 then p = 0.0000011525110308452509527041155734120601831426713154833485

All of these are probabilities of N people choosing two of the same number, but not N people choosing the two (or more) of the same number, when each person chooses X numbers at once. I have no idea how to approach that.

Answer 1

The complement of the event "at least one number is chosen twice" is "every number is chosen at most once".

How much such arrangements are there? Any such arrangement is uniquely represented by the choice of which numbers belong to thread 1, which to thread 2, and so on; all the remaining numbers (if any) are left unchosen. So, there are $$ \binom{K}{X}\binom{K-X}{X}\binom{K-2X}{X}\cdots\binom{K-(N-1)X}{X}=\frac{K!}{(X!)^N(K-NX)!} $$ in all. Since the total number of ALL possible arrangements (valid or invalid) is $\binom{K}{X}^N$, the probability of choosing a GOOD arrangement (under the assumption that $K-NX\geq 0$) is $$ \begin{align*} \frac{\frac{K!}{(X!)^N(K-NX)!}{}}{\binom{K}{X}^N}&=\frac{K!}{(X!)^N(K-NX)!}\cdot\frac{(X!)^N((K-X)!)^N}{(K!)^N}\\ &=\frac{((K-X)!)^N}{(K-NX)!\cdot(K!)^{N-1}} \end{align*} $$ So, the probability that at least one collision occurs is $$ 1-\frac{((K-X)!)^N}{(K-NX)!\cdot(K!)^{N-1}} $$