A good approximation for collision probability between (two) sets of random variables

Question

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\}$.

Answer 1

We are assuming that $A_1,\dots,A_m,B_1,\dots,B_n$ are iid random variables each uniformly distributed over the set $[t]:=\{1,\dots,t\}$.

By the Bonferroni inequalities, for the probability of at least one collision
\begin{equation} p:=P\Big(\bigcup_{(i,j)\in[m]\times[n]} \{A_i=B_j\}\Big), \end{equation} we have \begin{equation} p_1-p_2\le p\le p_1, \end{equation} where \begin{equation} p_1:=\sum_{(i,j)\in[m]\times[n]} P(A_i=B_j)=\frac{mn}t \end{equation} and \begin{equation} p_2:=\sum_{ \substack{(i_1,j_1)\in[m]\times[n], \\ (i_2,j_2)\in[m]\times[n]\setminus\{(i_1,j_1)\}} } P(A_{i_1}=B_{j_1},A_{i_2}=B_{j_2})=\frac{mn(mn-1)}{t^2} =o\Big(\frac{mn}t\Big) \end{equation} if $mn=o(t)$.

So, \begin{equation} p\sim\frac{mn}t \end{equation} if $mn=o(t)$.

Thus, the probability of no collisions is \begin{equation} 1-p=1-\frac{mn}t\,(1+o(1)) \end{equation} for very large $t$, that is, for $t$ much greater than $mn$.