Skip to main content
5 of 5
added 408 characters in body

Partitioning the coupons collected in the classical coupon collector's problem

Suppose that there is an urn containing $n$ different coupons, from which $m$ coupons are being collected, equally likely, with replacement.

Let $C(m)$ be the whole set of the $m$ collected coupons. Let $\mathcal{P}_k(m)$ be the subset of all partitions of $C(m)$ where in all partitions $P \in \mathcal{P}_k(m)$, for each coupon subset $S \in P$, we have: (i) All coupon types in $S$ are distinct, and (ii) $|S| \le k$.

Questions: What is the mimimum cardinality of a partition in $\mathcal{P}_k(m)$ (in expectation)? What is the maximum number of coupon subsets having size equal to $k$ of a partition in $\mathcal{P}_k(m)$ (in expectation)?


Toy example: m=10, n=3, k=2. Multiset of coupon types collected after sampling $m$ coupons once: $C(m)=\{1, 1, 1, 1, 1, 1, 2, 2, 2, 3\}$. Mimimum cardinality of a partition in $\mathcal{P}_k(m)$: $6$. Maximum number of coupon subsets having size equal to $k$ of a partition in $\mathcal{P}_k(m)$: $4$. Partition example: $\{1, 2\}$, $\{1, 2\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1\}$, $\{1\}$.