A Pairwise Coupon Collector Problem This is a modified version of the coupon collector problem, where we are interested in making comparisons between the "coupons". There are a number of constraints which have been placed in order to make this applicable to the application of interest (not relevant here, but related to clustering).


*

*There exists $M$ unique coupons.

*Coupons come in packets of size $K$.

*Each packet contains $K$ unique units, sampled uniformly without replacement from the total set of $M$ units.

*The contents of a packet is independent of all other packets.

*All units in a packet are "compared" to all other units in the packet.

*Units may not be compared across packets.

Question 1. Let $X$ be the number of unique comparisons that have been made after $T$ packets have been acquired. What is the expected value and variance of $X$?
Question 2: Let $T_\star$ be the smallest number of packets required to make all of the $\binom{M}{2}$ comparisons. What is the expected value and variance of $T_\star$?

A Solution for Question 1
\begin{align*}
E(X) &= \binom{M}{2}\left(1 - (1-p)^T\right) \\
V(X) &= \binom{M}{2}(1-p)^T\left(1 -\binom{M}{2}(1-p)^T\right)  + 6\binom{M}{3}(1-q)^T + 6\binom{M}{4}(1-r)^T
\end{align*}
where
\begin{align*}
p &= \frac{K(K-1)}{M(M-1)} \\
q &= \frac{2\binom{M-2}{K-2} - \binom{M-3}{K-3}}{\binom{M}{K}} \\
r &= \frac{2\binom{M-2}{K-2} - \binom{M-4}{K-4}}{\binom{M}{K}} 
\end{align*}
The following plot shows $E(X)$ and $E(X) - 2\sqrt{V(X)}$ as a function of $T$ for the case where $M=50$ and $K=10$.


Derivation of Results
Notation and Preliminaries
Let $A_{ij,t}$ be the event that units $i$ and $j$ are compared in packet $t$. It is easy to see that $P(A_{ij, t}) = \frac{K(K-1)}{M(M-1)}$. Now let $B_{ij} = \cap_{t=1}^TA^c_{ij,t}$ be the event that units $i$ and $j$ are not compared in any packet.
\begin{align*}
P(A_{ij}) &= P\left(\bigcap_{t=1}^TA^c_{ij,t}\right) \\ 
&= P(A^c_{ij,t})^T \\
&= \left(1 - \frac{K(K-1)}{M(M-1)}\right)^T
\end{align*}
Finally, let $X_{ij}$ be an indicator variable which equals $1$ when $B_{ij}^c$ holds and $0$ otherwise. Note that $$X_{ij} \sim \text{Bern}\left(1 -\left(1 - \frac{K(K-1)}{M(M-1)}\right)^T\right).$$ Then the total number of comparisons made can be denoted
$$X = \sum_{i < j}X_{ij}$$
Expected Value of $X$
By linearity of expectation we have
$$E(X) = E\left(\sum_{i < j}X_{ij}\right) = \sum_{i < j}E\left(X_{ij}\right) = \binom{M}{2}\left(1 -\left(1 - \frac{K(K-1)}{M(M-1)}\right)^T\right)$$
Variance of $X$
The variance is slightly tricker. We begin by finding $E(X^2)$. First note that
\begin{align*}
X^2 &= \left(\sum_{i < j}X_{ij}\right)^2 \\
&= \underbrace{\sum X_{ij}^2}_{\binom{M}{2} \text{ terms}} + \underbrace{\sum X_{ij}X_{kl}}_{\binom{M}{4}\binom{4}{2} \text{ terms}} + \underbrace{\sum X_{ij}X_{ik} + \sum X_{ij}X_{jk} + \sum X_{ik}X_{jk}}_{\binom{M}{3}\cdot 3 \cdot 2 \text{ terms}}
\end{align*}
We group the sum in this way so that the terms in each group have the same expected value. Note that the total number of terms is $\binom{M}{2} + 6\binom{M}{3} + 6\binom{M}{4} = \binom{M}{2}^2$, as expected. We will now look at each of the three cases individually.
Case One: $E(X_{ij}^2)$
Since $X_{ij}$ is binary, we have that $X_{ij}^2 = X_{ij}$, thus
$$E\left(\sum X_{ij}^2\right) = E(X) = \binom{M}{2}\left(1 -\left(1 - \frac{K(K-1)}{M(M-1)}\right)^T\right)$$
Case Two: $E\left(X_{ij}X_{kl}\right)$
Using standard facts about products of Bernoulli random variables, we have $E\left(X_{ij}X_{kl}\right) = P(X_{ij} = 1, X_{kl} = 1)$ where $i$, $j$, $k$ and $l$ are all distinct units. There are $\binom{M}{4}$ ways to choose these distinct units, and then $\binom{4}{2} = 6$ ways to choose a valid index assignment.
The event $\{X_{ij} = 1, X_{kl} = 1\}$ is equivalent to the event $B_{ij}^c \cap B_{kl}^c$.
\begin{align*}
E(X_{ij}X_{kl}) &= P(B_{ij}^c \cap B_{kl}^c) \\
&= 1 - P(B_{ij} \cup B_{kl}) && \text{DeMorgans Law} \\
&= 1 - \left[P(B_{ij} + P(B_{kl}) - P(B_{ij} \cap P(B_{kl})\right] \\
&= 1 - \left[2\left(1-\frac{K(K-1)}{M(M-1)}\right) - P\left(\bigcap_{t=1}^T\{B_{ij,t}\cap B_{kl,t}\}\right)\right] \\
&= 1 - 2\left(1-\frac{K(K-1)}{M(M-1)}\right) +  P(B_{ij,1} \cap B_{kl, 1})^T && \text{independence across packets} \\
&= 1 - 2\left(1-\frac{K(K-1)}{M(M-1)}\right) +  \left(1 - \frac{2\binom{M-2}{K-2} - \binom{M-4}{K-4}}{\binom{M}{K}} \right)^T
\end{align*}
Case Three: $E\left(X_{ij}X_{ik}\right)$
This case is very similar to the the previous case. There are $6\binom{M}{3}$ terms with this expected value because there are $\binom{M}{3}$ ways to choose three distinct units, $3$ ways to choose which unit is shared between both indicators and $2$ ways to assign the remaining indices. The probability calculation proceeds in the exact same way as case two, up until the last line which becomes.
$$E(X_{ij}X_{ik}) = 1 - 2\left(1-\frac{K(K-1)}{M(M-1)}\right) +  \left(1 - \frac{2\binom{M-2}{K-2} - \binom{M-3}{K-3}}{\binom{M}{K}} \right)^T$$
Putting Everything Together
To simplify notation, lets define
\begin{align*}
p &= \frac{K(K-1)}{M(M-1)} \\
q &= \frac{2\binom{M-2}{K-2} - \binom{M-3}{K-3}}{\binom{M}{K}} \\
r &= \frac{2\binom{M-2}{K-2} - \binom{M-4}{K-4}}{\binom{M}{K}} 
\end{align*}
Then we have
\begin{align*}
E(X^2) &= \binom{M}{2}\left(1 -(1 -p)^T\right) + \\
&\quad\quad 6\binom{M}{3}\left(1 - 2(1-p)^T + (1-q)^T\right) + \\
&\quad\quad 6\binom{M}{4}\left(1 - 2(1-p)^T + (1-r)^T\right) \\
&= \binom{M}{2}^2 - \left(\binom{M}{2} + 12\binom{M}{3} + 12\binom{M}{4}\right)(1-p)^T + \\
&\quad\quad 6\binom{M}{3}(1-q)^T + 6\binom{M}{4}(1-r)^T
\end{align*}
And the variance can be calculated using the identity $\text{Var}(X) = E(X^2) - E(X)^2$ which gives (after simplification)
$$\text{Var}(X) = \binom{M}{2}(1-p)^T\left(1 -\binom{M}{2}(1-p)^T\right)  + 6\binom{M}{3}(1-q)^T + 6\binom{M}{4}(1-r)^T $$
