2
$\begingroup$

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.


$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – kjetil b halvorsen Mar 3 '15 at 16:19
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Mar 5 '15 at 17:27
  • $\begingroup$ finally i added some lines to my original post. $\endgroup$ – user2888219 Mar 5 '15 at 18:48
  • $\begingroup$ The expected count of uncollected coupons is a simple calculation by the linearity of expectation. $\endgroup$ – Douglas Zare Mar 5 '15 at 21:46
1
$\begingroup$

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/

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user2888219 Mar 5 '15 at 7:13

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.