My universe has M different items. I run m=10 independent samplings over M. In each sampling, n elements are picked without replacement (n<<M). What is the expected number of pair duplicates we shall get across the m independent samplings? I know that the universe has M(M-1)/2 distinct pairs, and in each sampling one combination among nCM is selected, still the exact probability formula does not seem straightforward.



Number of duplicate pairs in multiple samplings
The answer is
$$\binom M2(1-m p q^{m-1}-q^m),$$
where
$$p:=\frac{n(n-1)}{M(M-1)},\quad q:=1-p.\tag{0}$$




---


*Details:* Fix any "pair" -- that is, any subset $a\subseteq[M]:=\{1,\dots,M\}$ of cardinality $2$. For each $i\in[m]$, let $S\_i$ denote the $i$th random sampling, that is, the $i$th random set of size $|S\_i|=n$, selected uniformly at random from the set $[M]$. The random sets $S\_1,\dots,S\_m$ are independent and identically distributed (iid).


Consider now the $m$ iid trials with the success in the $j$th trial defined as $a\subseteq S\_j$, for $j\in[m]$, so that that the success probability in each trial is $p$, with $p$ as defined in (0).
Then the event -- say $B(a)$ -- that $a$ is contained in more than one of the random sets $S\_1,\dots,S\_m$ is the event of $\ge2$ successes in the $m$ trials, and hence
$$P(B(a))=P:=1-m p q^{m-1}-q^m,$$
with $q=1-p$, as defined in (0).


It remains to note that the number of the "pair duplicates", that is, the random number of subsets of cardinality $2$ of the set $[M]$ that are contained in more than one of the sets $S\_1,\dots,S\_m$ is
$$N:=\sum\_{a\in\binom{[M]}2}1\_{B(a)}$$
and hence
$$EN=\binom M2 E1\_{B(a)}=\binom M2 P,$$
as claimed.


