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.
6
-
1$\begingroup$ What do you mean by a pair duplicate? $\endgroup$– Iosif PinelisCommented Aug 17, 2020 at 15:58
-
$\begingroup$ Any pair of items (i,j) that is found more than once across samplings. $\endgroup$– OmarRCommented Aug 17, 2020 at 16:58
-
$\begingroup$ Each of the 10 times, $(n^2-n)/2$ pairs are chosen. For each pair at one time, the probability of its matching with a pair from another time is roughly $9(n^2-n)/(M^2-M)$. So the expected number of duplicate pairs is roughly $$\frac{45(n^2-n)^2}{2(M^2-M)}.$$ Since $n << M$, it seems unnecessary to go further. $\endgroup$– user44143Commented Aug 17, 2020 at 18:10
-
$\begingroup$ Could you please explain how the probability $9(n^2-n)/(M^2-M)$ is obtained because this formula does not make a distinction between sampling with and without replacement (I guess). $\endgroup$– OmarRCommented Aug 17, 2020 at 19:49
-
$\begingroup$ @OmarR. : Does "any pair of items (i,j) that is found more than once across samplings" mean "any subset of cardinality $2$ of the set $\{1,\dots,M\}$ that is found in more than one sampling"? $\endgroup$– Iosif PinelisCommented Aug 17, 2020 at 19:51
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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.
answered Aug 17, 2020 at 20:05