# 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).

1. There exists $$M$$ unique coupons.
2. Coupons come in packets of size $$K$$.
3. Each packet contains $$K$$ unique units, sampled uniformly without replacement from the total set of $$M$$ units.
4. The contents of a packet is independent of all other packets.
5. All units in a packet are "compared" to all other units in the packet.
6. 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$$