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?

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, www.jstor.org/stable/2691301.

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.

- Solution to rarity-generalized coupon-collector's problem?
- Expiring coupon collector's problem
- Probability distribution in the coupon collector's problem
- Coupon Collector's problem with unequal probabilities
- Expected Value - Uniform distribution over infinite interval
- Coupon Collector's Problem — Expected Value of each item
- Variation of Coupon Collector's Problem
- Variant of the Coupon Collector's Problem with Two Probabilities
- Coupon Collector's Problem with Partial Collections and Coupon Packages
- does it make sense to ask the expected value for discrete values in non-enumerable sets?

- Is there a reason to keep Windows' primary partition / drive C: small?
- Where are these floating eyeball creatures from?
- Explanation as to why Male/Female Wizards have sexy bodies
- Online radio logo feedback request (Part 2)
- Someone wants to send me cash by DHL. How's this scam supposed to work?
- What is the difference between anger and violence?
- Is it possible to get Extra Attack or equivalent without taking at least 5 levels in a class?
- Is there a noun for the general, solely negative, discrimination of any kind of group?
- Sort odd numbers first
- Is it really impossible to fix a seized engine?
- Bypass MAC address internet time filtering?
- Voltameter in TeX?
- How can someone profit from a horse as an investment?
- Find an "upper bound" for a given sequence.
- What is the name for the plastic piece on the end of a 5.25" optical drive tray?
- Why allow convicted criminals to vote?
- Function to test if exactly one of three parameters is truthy, without using equality operators
- Why would a healing factor superhero still be afraid of things?
- Setting the time
- Calculating probability of an event that has almost but not happened yet
- Would anything stop a technology company from shutting down in protest of government regulations?
- Before OOP, were data structure members left public?
- How do hot air balloons navigate?
- Convert a list of decimal values in a text file into hex format