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.

  • 2
    $\begingroup$ duplicate of: mathoverflow.net/questions/198857/… $\endgroup$ – kjetil b halvorsen Mar 5 '15 at 16:34
  • $\begingroup$ 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? $\endgroup$ – user2888219 Mar 5 '15 at 18:56
  • $\begingroup$ 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. $\endgroup$ – kjetil b halvorsen Mar 6 '15 at 1:39
  • $\begingroup$ 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 ; ) $\endgroup$ – user2888219 Mar 6 '15 at 6:34

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.

  • $\begingroup$ @user2888219 Just play with the data you are given and try to obtain the best bound you are able to. $\endgroup$ – Yuval Filmus Mar 13 '15 at 15:26
  • $\begingroup$ 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? $\endgroup$ – user2888219 Mar 13 '15 at 15:28
  • $\begingroup$ 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. $\endgroup$ – user2888219 Mar 13 '15 at 15:33
  • $\begingroup$ @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. $\endgroup$ – Yuval Filmus Mar 14 '15 at 15:28
  • $\begingroup$ "I suggest you give it a shot" - okay. thanks again, yuval. $\endgroup$ – user2888219 Mar 16 '15 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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