# Coupon Collector Problem for Non-Uniform Coupons: Bound on the number of missed Coupons

Suppose $\mathcal B=\{1,2,..,b\}$ is the set of all possible coupons, with $\mathbf p = ( p_1,p_2,...,p_b)$ assigning the probability of occurrence for all coupons in $\mathcal B$.

1. The "traditional coupon collecting problem" can be summarized as follows: Assume we have a variable numbers $n$ of draws from a non-depleting set of coupons (urn with coupons distributed as $\mathbf p$). We can count the drawn numbers of coupons according the different kinds of coupons in $\mathcal B$ with a occupancy vector $(X_1,X_2,..X_b)$, with $X_i$ is the number of coupons from type $i$, and $\sum_i X_i=n$. A prominent problem investigate in $\mathbb E[n]$, i.e. expected number of needed to fulfill a constraint on minimal quotas $X_i \geq q_i$, with predefined quotas $\mathbf q = ( q_1,q_2,...,q_b)$. Investigated, e.g. in [1,2].

2. A kind twisted problem I am interested in is the following: Assume we have a fixed number of $N$ draws from the urn of coupons with non-uniform distribution $\mathbf p$, can estimate or bound the number of coupon-types, which we will not observe in our $N$ draws? To be more formal, let $Y_i$ be an indicator variable with $Y_i=1$ for $X_i=0$ otherwise $Y_i=0$, and we are interested in $\mathbb E[G]$, where $G=\sum_i Y_i$.Evidently, for uniform distribution the expected number of vacancies in the occupancy vector will be minimal.

In fact I am interested in bounding $\mathbb E[G]$ incorporating an information theoretic measure on $\mathbf p$, e.g. the entropy of the distribution $\mathbf p$, the total variation distance of $\mathbf p$ to uniform distribution or maybe some useful f-divergence. At least some bound dependend on maybe $\max_i p_i$ and $\min_i p_i$ would be helpful.

 If you have any idea how to tackle my problem, I am glad to hear your advice or answer. Thanks in advance.

P.s. Thanks @kjetil-b-halvorsen for your comment. Indeed, you are right. Your comment helped to formulate my question more precisely. Thanks.   Old description:

Topic: Multinomial proxy variables: Bound on probability of their sums

Suppose $(X_1,X_2,..X_i,..,X_b)$ as multinomial vector of random variables with $N=\sum_{i=1}^b X_i$ and probabilities $p_i$ to parametrize the $X_i$.

Let us take the following imagination to describe my problem: Assume there is an array of $b$ tubes that can hold maximal $N$ balls. All $N$ balls are randomly thrown towards the tubes and with probability $p_i$ a ball enters the tube labeled with index $i$. Ideally, we want to have the balls equally distributed among the tubes. Therefore let us define a non-negative penalty function (a truncated proxy random variable) for each tube as follows: $$y(X_i) = \begin{cases} X_i-1 &,~for~ X_i \geq 2\\ 0 &,~else\\ \end{cases}$$ Finally, I am interested in the summation of the tubes overhang $\hat N=\sum_{i}~y(X_i)$ and the distribution of $\hat N$.

As the number of tubes $b$ and the number of balls $N$ are in the order of $10^5..10^6$ I see no way to calculate the distribution of $\hat N$ analytically.

In fact I am interested in showing a probabilistic bound on the maximal overhang like ${\rm Pr}(\hat N \leq k) \geq \mathcal F(k,b,N,I(\mathbf p))$, as a function expression $\mathcal F$, which incorporate an information theoretic measure $\mathcal I(\mathbf p)$, e.g. the entropy of the distribution $\mathbf p$, the total variation distance of $\mathbf p$ to uniform distribution or maybe some useful f-divergence. At least some bound dependend on maybe $\max_i p_i$ and $\min_i p_i$ would be helpful.

• Note that if $g$ is the number of zeros in your multinomial vector $X$, then ovarhang is simply $\hat{N}=N-b+g$, so you want the distribution of the number of zeros $G$ in an multinomial vector. Could there be an poisson approximation for that? – kjetil b halvorsen Mar 3 '15 at 16:19
• Etiquette (and good practice in general) is to have such edits accompanied by a brief acknowledgment, e.g. "thanks to kjetil b halvorsen..." or "I learned from kjetil b halvorsen that...", even if the insight is not original with the person who helped inspire it. Gerhard "Plenty Of Space For Acknowledgment" Paseman, 2015.03.05 – Gerhard Paseman Mar 5 '15 at 17:27
• finally i added some lines to my original post. – user2888219 Mar 5 '15 at 18:48
• The expected count of uncollected coupons is a simple calculation by the linearity of expectation. – Douglas Zare Mar 5 '15 at 21:46

This is really an extended comment, to large for a comment. The overhang is simply $\hat{N} = N - b + g$, where $g$ is the number of multinomial components equal to zero. So the only random part of that is $G$, the random variable defined as the number of $X_i=0$.
Consider the following game. You have $b$ boxes, throwing balls at them, independently. Box $i$ have hit probability $p_i$. Then we can think about varios scenarios, as example:
1) How large must $N$ (number throws) be to hit all the boxes, that is , to get $G=0$? That is the coupons collector problem.
2) How large must $N$ be to have al least one box with two (or more)balls? That is the birthday problem.
You want the complete distribution of $G$, or some approximation. That is a question about the number of occupied boxes, which is known as the occupancy problem, closely related to coupons collector problem. See for example https://probabilityandstats.wordpress.com/2010/03/27/the-occupancy-problem/
• Thanks @kjetil-b-halvorsen for your comment. Indeed, you are right: my problem is equivalent to the Coupon Collector Problem for non-uniform coupons and quotas, but with slightly changed focus. As you pointed out, I focus on the expected number of coupon-types, for which no coupon is collected in $N$ trials. It's equal to $\mathbb E[G]$, where $G$ is the random variable assigning the emtpy bins. I edit my question regarding the new perspective I got from you. – user2888219 Mar 5 '15 at 7:13