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.

$$$$ $$$$ Old description:

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.

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:

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.

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.

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

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.

$$$$ $$$$ Old description:

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.

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 are functioncal relation $\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 a integrating $\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.

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.

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