We face many places to find the collision probability of two sets (or more) in my case the cryptographic hash functions. We can formalize as;

Given two sets of random variables $\mathbf{A}$ and $\mathbf{B}$ compromised $m$ and $n$ elements, respectively. Consider $t$ discrete values where each variable $\{A_1, A_2,\ldots,A_m\}$ and $\{B_1, B_2,\ldots,B_n\}$ can assume any of the $t$ values with equally likely probability. Clearly, a collision is at least one element of $\mathbf{A}$ is also in $\mathbf{B}$.

The problem investigated in

- 2003, Collision probability between sets of random variables by Michael C. Wendl.

**The probability of no collision** $P_0(m,n,t)$ is given in the below theorem;

**Theorem 1**(Probability of success). The probability of no collisions between two sets of random variables $\{A_1, A_2,\ldots,A_m\}$ and $\{B_1, B_2,\ldots,B_n\}$, the elements of which can assume any of $t$ discrete values with equally likely probability is $$ P_0(m,n,t) = \frac{1}{t^{m+n}}\sum_{i=1}^{m}\sum_{j=1}^{n} S_2(m,i)S_2(n,j) \prod_{k=0}^{i+j-1} t-k$$where $S_2$ represents Stirling numbers of the second kind.

When $t$ becomes very large like $2^{64}$ we cannot use this theorem to calculate the probability. Therefore we need a good approximation as in the birthday problem.

Is there any good approximation for this theorem/problem that can be used easily to calculate large values assuming that $A_1,\dots,A_m,B_1,\dots,B_n$ are **independent and identically distributed random variables each uniformly distributed** over the set $[t]:=\{1,\dots,t\}$.

6more comments