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

Suppose $\mathcal B=\{1,2,\ldots,b\}$ is the set of all possible coupons, with $\mathbf p = ( p_1,p_2,\ldots,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.

• duplicate of: mathoverflow.net/questions/198857/… – kjetil b halvorsen Mar 5 '15 at 16:34
• i am a bit confused, is the audience of the math.stackexchange and mathoverflow the same? should i remove this post, as it's a doublicate? – user2888219 Mar 5 '15 at 18:56
• When you post a duplicate, at least you should up front say so! And, no, you should not now remove it. There is a certain intersection between the audiences, I dont know how large. – kjetil b halvorsen Mar 6 '15 at 1:39
• Sorry, as you can see, i am quite new to this community and not familiar with the etiquette and good practice, yet. But I try my very best with future posts. Thanks again, for pushing me in the right direction, again ; ) – user2888219 Mar 6 '15 at 6:34

## 1 Answer

It is easy to calculate $\mathbb{E}[G]$ using linearity of expectation. We have $\mathbb{E}[Y_i] = \Pr[X_i=0] = (1-p_i)^N$. Therefore $$\mathbb{E}[G] = \sum_{i=1}^b (1-p_i)^N.$$ Whether you can bound it in terms of any other functions of $\mathbf{p}$ is up to you.

• @user2888219 Just play with the data you are given and try to obtain the best bound you are able to. – Yuval Filmus Mar 13 '15 at 15:26
• okay. thanks for this precise answer. maybe you can give me some further hint. apparently we have $m (1-1/b)^N \leq \mathbb E[G]$ and further $\| \mathbf 1 - \mathbf p|_\infty \leq \mathbb E[G] \leq m \| \mathbf 1 - \mathbf p|_\infty$ as trivial bounds with $\mathbf 1$ as $m$-dimensional all-one vector. i need more structure in $\mathbf p$ to limit $\mathbb E[G]$ more specificly. what's about: a) $\| \mathbf 1/b - \mathbf p\|_1 < \rho_1$ or more strict with b) $| 1/b - p_i| < \rho_2$. would this help in tightening the limits? – user2888219 Mar 13 '15 at 15:28
• maybe you have some reference for me, as i don't know for what to search exactly. but, i am sure there are some results about the distance from uniform distribution, at least in textbooks. – user2888219 Mar 13 '15 at 15:33
• @user2888219 You may be right that somewhere some such bound can be found. But these bounds are usually not too difficult to obtain using standard techniques. I suggest you give it a shot. Usually the tricks are the Cauchy–Schwartz inequality and Jensen's inequality. – Yuval Filmus Mar 14 '15 at 15:28
• "I suggest you give it a shot" - okay. thanks again, yuval. – user2888219 Mar 16 '15 at 6:45