Does the uniform distribution minimize the expected value in the coupon collector's problem?

Stanley Yu 07/11/2018. 3 answers, 164 views
probability optimization coupon-collector

Given a discrete probability distribution with $n$ possible outcomes and the task of repeatedly sampling until getting each outcome at least once, does the uniform distribution give the smallest expected value for the total number of samples?

3 Answers

Clement C. 07/11/2018.

Yes. This is shown e.g. in [1], under the name Collector's inequality:

The result we wish to point out is that $A(\mathbf{p})$ is a Schur-convex function of the probability vector $\mathbf{p}$. That is, if $\mathbf{p} \gg \mathbf{q}$, then $A(\mathbf{p}) > A(\mathbf{q})$. Thus, the minimum value of $A(\mathbf{p})$ occurs when $\mathbf{p}$ is the uniform distribution $\mathbf{u} = (1/n,\dots,1/n)$.

[1] Clevenson, M. Lawrence, and William Watkins. Majorization and the Birthday Inequality. Mathematics Magazine, vol. 64, no. 3, 1991, pp. 183–188. JSTOR, JSTOR,

saulspatz 07/11/2018.

In the paper "Birthday paradox, coupon collectors, caching algorithms and self-organizing search" equation $(13b)$ gives the expected number of draws to get a complete collection of $m$ coupons, where coupon $i$ has probability $p_i$ as $$\int_0^{\infty}\left(1-\prod_{i=1}^m(1-e^{-p_it})\right)\mathrm{dt}$$ Clearly it is enough to show that for every $t\ge0,$the maximum value of $\prod_{i=1}^m(1-e^{-p_it}),$ subject to $0\le p_i,\ i=1,\dots,m$ and $\sum_{i=1}^mp_i=1,$ occurs when all the $p_i=1/m.$ This is easy; take the logarithm of the product and use Lagrange multipliers.

joriki 07/11/2018.

Ignore all but two of the coupon types. Conditional on the combined number $n$ of coupons of these two types having been drawn, the probability that both types have been drawn is $1-p^n-(1-p)^n$, where $p$ is the probability that a coupon of one of these two types is of the first type. This is maximal for $p=\frac12$. Thus a distribution is only optimal if $p=\frac12$ for all pairs of types, that is, if it is uniform.

Related questions

Hot questions


Popular Tags