Skip to main content
1 of 2
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Large deviation inequalities for number of coupon types collected by a coupon collector with fixed budget

In the generalized Coupon Collector's Problem, there are $N$ types of coupon, and for any $i \in [N] := \{1,2,\ldots,N\}$, $p_i \ge 0$ is the probability of obtaining a type-i coupon on any trial. Thus, $\sum_{i=1}^N p_i = 1$. Let $T_N$ be the number of (independent) trials required to collect all $N$ types of coupons. Note that $T_N$ is a random integer. Under general regularity conditions on the $p_i$'s (e.g uniformity $p_i = 1/N$ for all $i$; etc.), there exists large-deviation inequalities (LDIs) of the form $$ \mathbb P(T_N \le b_N + zk_N) = e^{-e^{-z}} + o_N(1), $$ for some appropriate $b_N$ and $k_N$ with $k_N/b_N = o(1)$. see the paper "The Coupon Collector's Problem Revisited: Generalizing the Double Dixie Cup Problem of Newman and Shepp " https://arxiv.org/abs/1412.3626 for details.

For example, in the uniform case where $p_i = 1/N$ for all $i$, it is well-known that $b_N = N\log N$ and $k_N = N$.

I'm interested in another quantity. Define $N_T$ to be the number of coupon types collected after $T$ trials. It is clear that $N_T = N$ iff $T_N \le T$.

Question. Are the large deviation inequalities for $N_T$ (perhaps for appropriately scaled $T$) ?

N.B.: I'm particularly interested in the case where the $p_i$'s a rapidly decreasing, e.g $p_i \propto i^{-b}$ for some constant $b \gt 1$.

dohmatob
  • 6.9k
  • 1
  • 18
  • 76