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
- 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?
- Expected Distribution of the Outcome Counts When Sampling from a Categorical Random Variable

- How to tell my possible employer about a technical showstopper in performing a task
- Four coins with reflip problem?
- How to help SO lose gracefully in games?
- Toddler being taught to cuss by older kids. How to deal with rude language at social gatherings?
- Why do some professors not recommend any text books for a course?
- "There's been a change in your itinerary" - Why are the flights now longer?
- What's the point of quivers?
- Did the wizarding world ever learn that Gilderoy Lockhart was a fraud?
- Is it unreasonable to expect Any() *not* to throw a null reference exception?
- Any rectangular shape on a calculator numpad when divided by 11 gives an integer. Why?
- Should I check if something exists in the db and fail fast or wait for db exception
- Why is the principle of explosion accepted in constructive mathematics?
- HR treating new hires like kids
- Intervals: Diminished unison?
- Pedal threads too big for crank?
- Is BX the Base Address Register, and if so why?
- Is it good to have slides that may be skipped during a presentation?
- Matchstick Puzzles
- How can we define Latitude and Longitude before defining a Datum?
- Why does it say, that a Switch can segregate the collision domain?
- Summing rows in a new column using sed, awk and perl?
- Why do European cities have so many homeless and beggars despite its high-tax welfare system?
- What game does this video from Twitter come from?
- Why were 3D games on the Amiga not faster than on similar 16 bit systems like the Atari ST