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](https://www.sciencedirect.com/science/article/abs/pii/S0167715203001688) 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](https://en.wikipedia.org/wiki/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\}$.



A good approximation for collision probability between (two) sets of random variables
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](https://en.wikipedia.org/wiki/Boole%27s_inequality#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$.


