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$?


1 Answer 1


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$.

enter image description here

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 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.